基于广义后缀树的二分网络社区挖掘算法

doi:10.11896/j.issn.1002-137X.2017.07.039

摘要/Abstract

摘要： 近年来,二分网络的社区挖掘问题得到了极大的关注。提出了一种基于广义后缀树的二分网络社区挖掘算法。首先从二分网络的邻接矩阵中提取网络中每个节点的链接节点序列,然后构建广义后缀树。广义后缀树的每个节点表示二分网络的一个完全二分团,由此获取并调整完全二分团。通过引入二分团的紧密度得到初始的社区划分,最后再对孤立点进行处理以得到最终的社区划分。所提算法不仅能发现重叠社区,而且能得到一对多关系的社区。在人工数据集和真实数据集上的实验表明,所提算法能准确地识别二分网络中的社区个数,获得很好的划分效果。

关键词: 二分网络,社区划分,广义后缀树,重叠社区

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

邹凌君,陈崚,戴彩艳. 基于广义后缀树的二分网络社区挖掘算法[J]. 计算机科学, 2017, 44(7): 221-226. https://doi.org/10.11896/j.issn.1002-137X.2017.07.039

ZOU Ling-jun, CHEN Ling and DAI Cai-yan. Detecting Community from Bipartite Network Based on Generalized Suffix Tree[J]. Computer Science, 2017, 44(7): 221-226. https://doi.org/10.11896/j.issn.1002-137X.2017.07.039

参考文献

[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.

Metrics

Viewed

Full text

Abstract

Cited

Shared

Discussed