Computer Science ›› 2017, Vol. 44 ›› Issue (7): 221-226.doi: 10.11896/j.issn.1002-137X.2017.07.039

Previous Articles     Next Articles

Detecting Community from Bipartite Network Based on Generalized Suffix Tree

ZOU Ling-jun, CHEN Ling and DAI Cai-yan   

  • Online:2018-11-13 Published:2018-11-13

Abstract: In recent years,the problem of detecting communities from bipartite network has drawn much attention of researchers.This paper presented an algorithm based on generalized suffix tree for detecting communities from bipartite networks.The algorithm firstly extracts the adjacent node sequence for each node from the adjacency matrix of the bipartite network,and constructs a generalized suffix tree.Each node in the generalized suffix tree represents a complete bipartite clique.Then the algorithm extracts and adjusts those cliques.The closeness of two cliques is introduced to form initial communities.Finally,isolated nodes are processed to get the final community partition.The proposed algorithm can detect overlapping communities,and is able to get one-to-many correspondence between communities.Experimental results on the artificial networks and real-world networks show that,our algorithm can not only accurately identify the number of communities from bipartite networks,but also obtain high quality of community partitioning.

Key words: Bipartite network,Community division,Generalized suffix tree,Overlapping communities

[1] NEWMAN M E J.The Structure and Function of Complex Networks[J].Siam Review,2003,45(2):167-256.
[2] ADAMIC L A,ADAR E.Friends and neighbors on the Web[J].Social Networks,2003,25(3):211-230.
[3] RAGHAVAN U N,ALBERT R,KUMARA S.Near linear time algorithm to detect community structures in large-scale networks[J].Physical Review E Statistical Nonlinear & Soft Matter Physics,2007,76(3 pt 2):036106.
[4] LIU D Y,JIN D,HE D X,et al.Community Mining in Complex Networks[J].Journal of Computer Research and Development,2013,50(10):2140-2154.(in Chinese) 刘大有,金弟,何东晓,等.复杂网络社区挖掘综述[J].计算机研究与发展,2013,50(10):2140-2154.
[5] HUANG F L,ZHANG S C,ZHU X F.Discovering Network Community Based on Multi-Objective Optimization[J].Journal of Software,2013,4(9):2062-2077.(in Chinese) 黄发良,张师超,朱晓峰.基于多目标优化的网络社区发现方法[J].软件学报,2013,24(9):2062-2077.
[6] YU H,ZHAO Y L,CUI K,et al.Community Detection Algorithm Based on Cross-Entropy Method[J].Chinese Journal of Computers,2015(8):1574-1581.(in Chinese) 于海,赵玉丽,崔坤,等.一种基于交叉熵的社区发现算法[J].计算机学报,2015(8):1574-1581.
[7] JIANG S Y,YANG B H,WANG L X.An Adaptive Dynamic Community Detection Algorithm Based on Incremental Spectral Clustering[J].Acta Automatica Sinica,2015,41(12):2017-2025.(in Chinese) 蒋盛益,杨博泓,王连喜.一种基于增量式谱聚类的动态社区自适应发现算法[J].自动化学报,2015,41(12):2017-2025.
[8] LIU S C,ZHU F X,GAN L.A label-propagation-probability-based algorithm for overlapping community detection[J].Chinese Journal of Computers,2016,39(4):717-729.(in Chinese) 刘世超,朱福喜,甘琳.基于标签传播概率的重叠社区发现算法[J].计算机学报,2016,39(4):717-729.
[9] XIN Y,YANG J,XIE Z Q.Link-Block Method for the SemanticOverlapping Community Detection[J].Journal of Software,2016,27(2):363-380.(in Chinese) 辛宇,杨静,谢志强.一种面向语义重叠社区发现的Link-Block算法[J].软件学报,2016,27(2):363-380.
[10] NEWMAN M E J.Scientific collaboration networks.I.Network construction and fundamental results[J].Physical Review E Statistical Nonlinear & Soft Matter Physics,2001,64(2):016131.
[11] LIU A F,FU C H,ZHANG Z P,et al.An empirical statistical investigation on Chinese mainland movie network[J].Complex Systems and Complexity Science,2007,4(3):10-16.(in Chinese) 刘爱芬,付春花,张增平,等.中国大陆电影网络的实证统计研究[J].复杂系统与复杂性科学,2007,4(3):10-16.
[12] LAMBIOTTE R,AUSLOOS M.Uncovering collective listening habits and music genres in bipartite networks[J].Physical Review E Statistical Nonlinear & Soft Matter Physics,2005,72(2):066107.
[13] CHEN W Q,LU J A,LIANG J.Research in disease-gene network based on bipartite network projection[J].Complex System and Complexity Science,2009,6(1):13-19.(in Chinese) 陈文琴,陆君安,梁佳.疾病基因网络的二分图投影分析[J].复杂系统与复杂性科学,2009,6(1):13-19.
[14] MUKHERJEE A,CHOUDHURY M,GANGULY N.Under-standing how both the partitions of a bipartite network affect its one-mode projection[J].Physica A Statistical Mechanics & Its Applications,2011,390(20):3602-3607.
[15] HORVAT E ,ZWEIG K A.A fixed degree sequence model for the one-mode projection of multiplex bipartite graphs[J].Social Network Analysis and Mining,2013,3(4):1209-1224.
[16] NEWMAN M E.Modularity and community structure in net-works[J].Proceedings of the National Academy of Sciences of the United States of America,2006,103(23):8577-8582.
[17] GUIMERA R,SALESPARDO M,AMARAL L A.Module iden-tification in bipartite and directed networks.[J].Physical Review E Statistical Nonlinear & Soft Matter Physics,2007,76(3):036102.
[18] BARBER M J.Modularity and community detection in bipartite networks[J].Physical Review E,2007,76(6):066102.
[19] MURATA T.Detecting Communities from Bipartite Networks Based on Bipartite Modularities[C]∥Proceedings of the 2009 International Conference on Computational Science and Engineering(CSE’09).Piscataway,NJ,USA:IEEE,2009:50-57.
[20] LIU X,MURATA T.Community detection in large-scale bipartite networks[C]∥Proceedings of the 2009 IEEE/WIC/ACM International Joint Conference on Web Intelligence and Intelligent Agent Technology(WI-IAT’09).Washington,DC,USA:IEEE Computer Society,2009:50-57.
[21] XU Y C,CHEN L.Community Detection on Bipartite Networks Based on Ant Colony Optimization[J].Journal of Frontiers of Computer Science and Technology,2014,8(3):296-304.(in Chinese) 徐永成,陈崚.基于蚁群优化的二分网络社区挖掘[J].计算机科学与探索,2014,8(3):296-304.
[22] WANG T,LIU Y,XI Y Y.Identifying Community in Bipartite Networks Using Graph Regularized-based on-negative Matrix Factorization[J].Journal of Electronics & Information Techno-logy,2015,7(9):2238-2245.(in Chinese) 汪涛,刘阳,席耀一.基于图正则化非负矩阵分解的二分网络社区发现算法[J].电子与信息学报,2015,7(9):2238-2245.
[23] CHEN B L,CHEN L,ZOU S R,et al.Detecting community structure in bipartite networks based on matrix factorization[J].Computer Science,2014,1(2):55-58,1.(in Chinese) 陈伯伦,陈崚,邹盛荣,等.基于矩阵分解的二分网络社区挖掘算法[J].计算机科学,2014,1(2):55-58,1.
[24] CUI Y Z,WANG X Y.Uncovering overlapping community stru-ctures by the key bi-community and intimate degree in bipartite networks[J].Physica A:Statistical Mechanics and Its Applications,2014,407(407):7-14.
[25] BECKETT S J.Improved community detection in weighted bipartite networks[J].Royal Society Open Science,2016,3(1):140536.
[26] UKKONEN E.On-line construction of suffix trees[J].Algorithmica,1995,14(3):249-260.

No related articles found!
Viewed
Full text


Abstract

Cited

  Shared   
  Discussed   
No Suggested Reading articles found!