Algorithm of Detecting Community in Bipartite Network with Autonomous Determination of the Number of Communities
GUO Gai-Gai1, QIAN Yu-Hua2,3, ZHANG Xiao-Qin1,3, LI Ye-Bin2
1.School of Mathematics Sciences, Shanxi University, Taiyuan 030006 2.Key Laboratory of Computational Intelligence and Chinese Information Processing of Ministry of Education, Shanxi University, Taiyuan 030006 3.Institute of Intelligent Information Processing, Shanxi University, Taiyuan 030006
Abstract:The existing algorithms can find the community structure in bipartite network. However, they can not predict the number of communities and the relevant information and discover the real community structure accurately due to the variety and the complexity of the real network. In this paper, an algorithm of detecting community structure in bipartite network-cluster assign algorithm (CAA) is proposed and it determines the number of communities autonomously. In this algorithm, the interaction information between two types of nodes is used effectively and the problem of determining the number of communities is solved. The T-type nodes of the network are clustered, then the B-type nodes are assigned to the existing classes according to the allocation mechanism. Experiments show CAA obtains a higher quality community and has a higher accuracy than the algorithms based on resource distribution matrix and edge cluster coefficient.
郭改改,钱宇华,张晓琴,李烨斌. 自主确定社区个数的二模网络社区发现算法*[J]. 模式识别与人工智能, 2015, 28(11): 969-975.
GUO Gai-Gai, QIAN Yu-Hua, ZHANG Xiao-Qin, LI Ye-Bin. Algorithm of Detecting Community in Bipartite Network with Autonomous Determination of the Number of Communities. , 2015, 28(11): 969-975.
[1] Newman M E J. Scientific Collaboration Networks. I. Network Construction and Fundamental Results. Physical Review E, 2001. DOI: 10.1103/PhysRevE.64.016131 [2] Newman M E J. Scientific Collaboration Networks. II. Shortest Paths, Weighted Networks, and Centrality. Physical Review E, 2001. DOI: 10.1103/PhysRevE.64.016132 [3] Watts D J, Strogatz S H. Collective Dynamics of ′Small-World′ Networks. Nature, 1998, 393: 440-442 [4] Liu A F, Fu C H, Zhang Z P, et al. An Empirical Statistical Investigation on Chinese Mainland Movie Network. Complex Systems and Complexity Science, 2007, 4(3): 10-16 (in Chinese) (刘爱芬,付春花,张增平,等.中国大陆电影网络的实证统计研究.复杂系统与复杂性科学, 2007, 4(3): 10-16) [5] Chen W Q, Lu J A, Liang J. Research in Disease-Gene Network Based on Bipartite Network Projection. Complex Systems and Complexity Science, 2009, 6(1): 13-19 (in Chinese) (陈文琴,陆君安,梁 佳.疾病基因网络的二分图投影分析.复杂系统与复杂性科学, 2009, 6(1): 13-19) [6] Lambiotte R, Ausloos M. Uncovering Collective Listening Habits and Music Genres in Bipartite Networks. Physical Review E, 2005. DOI: 10.1103/PhysRevE.72.066107 [7] Zhang D P, Dai M F, Li L, et al. Distribution Characteristics of Weighted Bipartite Evolving Networks. Physica A: Statistical Mechanics and Its Applications, 2015, 428: 340-350 [8] Cui Y Z, Wang X Y. Uncovering Overlapping Community Structures by the Key Bi-community and Intimate Degree in Bipartite Networks. Physica A: Statistical Mechanics and Its Applications, 2014, 407: 7-14 [9] Tang L, Liu H. Community Detection and Mining in Social Media. San Rafael, USA: Morgan & Claypool Publishers, 2010 [10] Barber M J. Modularity and Community Detection in Bipartite Networks. Physical Review E, 2007. DOI: 10.1103/PhysRevE.76.066102 [11] Zhang P, Wang J L, Li X J, et al. Clustering Coefficient and Community Structure of Bipartite Networks. Physica A: Statistical Mechanics and Its Applications, 2008, 387(27): 6869-6875 [12] Wu Y J, Di Z R, Fan Y. A Clustering Algorithm for Bipartite Network Based on Distribution Matrix of Resources. Journal of Beijing Normal University: Natural Science, 2010, 46(5): 643-646 (in Chinese) (吴亚晶,狄增如,樊 瑛.基于资源分布矩阵的二分网聚类方法.北京师范大学学报:自然科学版, 2010, 46(5): 643-646) [13] Xu Y C, Chen L, Zou S R. Community Detection from Bipartite Networks // Proc of the 10th Web Information System and Application Conference. Yangzhou, China, 2013: 249-254 [14] Alzahrani T, Horadam K J, Boztas S. Community Detection in Bipartite Networks Using Random Walks // Proc of the 5th Workshop on Complex Networks CompleNet. Bologna, Italy, 2014: 157-166 [15] Larremore D B, Clauset A, Jacobs A Z. Efficiently Inferring Community Structure in Bipartite Networks. Physical Review E, 2014. DOI: 10.1103/PhysRevE.90.012805 [16] Guimerà R, Sales-Pardo M, Amaral L A N. Module Identification in Bipartite and Directed Networks. Physical Review E, 2007. DOI: 10.1103/PhysRevE.76.036102 [17] Wasserman S, Faust K. Social Network Analysis: Methods and Applications. Cambridge, UK: Cambridge University Press, 1994 [18] Scott J, Hughes M, Mackenzie J. The Anatomy of Scottish Capital: Scottish Companies and Scottish Capital, 1900-1979. Montreal, Canada: McGill-Queen′s University Press, 1980