基于矩阵分解的二分网络社区挖掘算法

计算机科学 ›› 2014, Vol. 41 ›› Issue (2): 55-58.

基于矩阵分解的二分网络社区挖掘算法

陈伯伦,陈崚,邹盛荣,徐秀莲

南京航空航天大学计算机科学与技术学院南京210016;扬州大学信息学院计算机系扬州225009;扬州大学信息学院计算机系扬州225009;扬州大学物理科学与技术学院扬州225009

出版日期:2018-11-14 发布日期:2018-11-14
基金资助:
本文受国家自然科学基金项目(61070047,61070133,61003180),国家重点基础研究发展规划(973)项目(2012CB316003),江苏省自然科学基金项目(BK21010134),江苏省研究生创新基金(CXZZ13_0172)资助

Detecting Community Structure in Bipartite Networks Based on Matrix Factorization

CHEN Bo-lun,CHEN Ling,ZOU Sheng-rong and XU Xiu-lian

Online:2018-11-14 Published:2018-11-14

摘要/Abstract

摘要： 二分网络社区挖掘对复杂网络有重要的理论意义和应用价值。提出了一个基于矩阵分解的二分网络社区挖掘算法。该算法首先将二分网络分为两个部分,每个部分尽可能保存完整的社区信息,然后分别对两个部分进行递归的拆分,直至不能拆分为止。在拆分的过程中,应用矩阵分解,使得到的分解能与网络的相关矩阵的行空间尽可能接近,即尽可能保持原图的社区信息。实验结果表明,该算法在不需任何额外参数的情况下,不但能较准确地识别实际网络的社区个数,而且可以获得很好的划分效果。

关键词: 二分网络,矩阵分解,社区检测中图法分类号TP301.6文献标识码A

Abstract: Community detection in bipartite network is very important in the reseach on the theory and applications of complex network analysis．An algorithm for detecting community structure in bipartite networks based on matrix factorization was presented．The algorithm first partitions the network into two parts,each of which can reserve the community information as much as possible,and then the two parts are further recursively partitioned until they can not be partitioned．When partitioning the network,we used the approach of matrix decomposition so that the row space of the associated matrix of the networks can be approximated as close as possible and the community information can be reserved the as much as possible.Experimental results show that our algorithm can not only accurately identify the number of communities of a network,but also obtain higher quality of community partitioning without previously known parameters．

Key words: Bipartite network,Matrix factorization,Detecting community structure

陈伯伦,陈崚,邹盛荣,徐秀莲. 基于矩阵分解的二分网络社区挖掘算法[J]. 计算机科学, 2014, 41(2): 55-58. https://doi.org/

CHEN Bo-lun,CHEN Ling,ZOU Sheng-rong and XU Xiu-lian. Detecting Community Structure in Bipartite Networks Based on Matrix Factorization[J]. Computer Science, 2014, 41(2): 55-58. https://doi.org/

参考文献

[1] Newman M E J．The structure and function of complex networks[J]．SIAM Rev．,2003(45):16-256
[2] Strogatz S H．Exploring complex networks[J]．Nature,2001(410):268-276
[3] Newman M E J．Scientific collaboration networks．I．networkconstruction and fundamental results[J]．Physical Review E,2001,64:016131
[4] Newman M E J．Scientific collaboration networks．II．shortestpaths,weighted networks,and centrality[J]．Physical Review E,2001,64:016132
[5] Le Blond S,Guillaume J L,LatapyM．C lustering in P2P exchanges and consequences on performances[C]∥Castro M,Renesse R．Peer- to-Peer Systems IV．Berlin:Heidelberg,2005:193-204
[6] Watts D J,Strogatz S H．Collective dynamics of small world networks[J].Nature,1998,3:440-442
[7] 刘爱芬,付春花,张增平,等.中国大陆电影网络的实证统计研究[J].复杂系统与复杂性科学,2007,4(3):10-16
[8] Robins G,Alexander M．Small worlds among interlocking directors:network structure and distance in bipartite graphs[J]．Computational & Mathematical organization Theory,2004,0:69-94
[9] Battiston S,Catanzaro M．Statistical properties of corporateboard and director networks[J]．European Physics Journal B,2004,8:345-352
[10] Ergun G．Human sexual contact network as a bipartite graph[J]．Physica A,2002,8:483-488
[11] Lambiotte R,Ausloos M．Uncovering collective listening habits and music genres in bipartite networks[J]．Physical Review E,2005,72:066107
[12] 陈文琴,陆君安,梁佳．疾病基因网络的二分图投影分析[J]．复杂系统与复杂性科学,2009,6(1):13-19
[13] Lind P G,Gonzalez M C,Herrmann H J．Cycles and clustering in bipartite networks[J]．Physical Review E,2005,2:056127
[14] Zhang P,Wang J L,Li X J,et al．Clustering coefficient and community structure of bipartite networks[J]．Physica A,2008,7:6869-6875
[15] 吴亚晶,狄增如,等.基于资源分布矩阵的二分网聚类方法[J].北京师范大学学报:自然科学版,2010,46(5):643-646
[16] Michael J．Barber,Modularity and community detection in bipartite networks[J]．Phys．Rev．E 76,066102,2007
[17] Lehmann S,Schwartz M,Hansen L K．Biclique communities[J]．Phys．Rev．E,2008,78(1):016108
[18] Raghavan U N,Albert R,Kumara S．Near linear time algorithm to detect community structures in large-scale networks[J]．Phys．Rev．E,2007,76(3):036106
[19] Liu X,Murata T．How does label propagation algorithm work in bipartite networks?[C]∥ Proceedings of the 2009IEEE/WIC/ACM International Joint Conference on Web Intelligence and Intelligent Agent Technology,WI-IAT ’09．Washington,DC,USA,2009
[20] Du N,Wang B,Wu B,et al．Overlapping Community Detection in Bipartite Networks[C]∥WI．2008:176-179
[21] 王洋,狄增如,樊琪.二分网络社团结构的比较性定义[J].复杂系统与复杂性科学,2009,6(4):40-44
[22] Newman M E J．Modularity and Community Structure in Networks [J]．Proc Natl Acad Sci USA,2006,103(23):8577-8582
[23] Guimera R,Sales-Pardo M,Amaral L A．Module identification in bipartite and directed networks[J]．Physical Review E,2007,6:036102
[24] Davis A,Gardner B B,Gardner M R．Deep South [M]．Chicago:The University of Chicago Press,1941
[25] Scott J,Hughes M．The Anatomy of Scottish Capital:Scottish Companies and Scottish Capital[C]∥ CroomHelm．London,1980:1900-1979

Metrics

Viewed

Full text

Abstract

Cited

Shared

Discussed