基于模块度增量的二分网络社区挖掘算法

计算机科学 ›› 2018, Vol. 45 ›› Issue (6A): 442-446.

基于模块度增量的二分网络社区挖掘算法

戴彩艳¹,陈崚^2,3,胡孔法¹

南京中医药大学信息技术学院南京210016¹
扬州大学信息工程学院江苏扬州225009²
南京大学计算机软件新技术国家重点实验室南京210093³

出版日期:2018-06-20 发布日期:2018-08-03
作者简介:戴彩艳(1985-),女,博士,讲师,主要研究方向为社区挖掘,E-mail:daicaiyan@163.com;陈崚(1956-),男,教授,博士生导师,主要研究方向为数据挖掘、人工智能;胡孔法(1970-),男,教授,博士生导师,主要研究方向为数据挖掘。
基金资助:
国家自然科学基金(81674099,81503499),江苏省“青蓝工程”资助项目(2016),国家重点研发计划项目(2017YFC1703501,2017YFC1703503,2017YFC1703506),江苏省高校优势学科建设工程项目,江苏省教育信息化研究立项课题(20172097),江苏省现代教育技术研究重点课题(2017-R-54927)资助

Algorithm for Mining Bipartite Network Based on Incremental Modularity

DAI Cai-yan¹,CHEN Ling^2,3,HU Kong-fa¹

College of Information Technology,Nanjing University of Chinese Medicine,Nanjing 210016,China¹
College of Information Engineering,Yangzhou University,Yangzhou,Jiangsu 225009,China²
State Key Lab of Novel Software Technology,Nanjing University,Nanjing 210093,China³

Online:2018-06-20 Published:2018-08-03

摘要/Abstract

摘要： 针对二分网络的社区挖掘问题,提出了一种基于模块度增量的二分网络社区挖掘算法。该算法假设每个顶点独自构成一个社区,并具有自己的标号。其中,一部分顶点将自己的标号复制并传递到另一部分中的某个顶点上,使之与其位于同一个社区;另一部分的顶点实施同样的操作。如此反复迭代,直至收敛。标号传播时,选择模块度增量最大的边进行传送,使整体模块度不断提高。在真实数据集上进行的测试表明,所提算法能对二分网络进行高质量的社区划分。

关键词: 标号传播, 二分网络, 模块度增量, 社区挖掘

Abstract: Aiming at mining communities from bipartite network,an algorithm based on incremental modularity was proposed.The algorithm assumes that each vertex constitutes a community by itself with its own label.A part of the vertex copies its own label and passes it to a vertex on another part,so that it is located in the same community,and then it performs the same operation on the vertices of another part,and repeats iterations until convergence.In label propagation,the algorithm chooses the edge with the largest incremental modularity,so that the overall modularity is constantly improving.The experimental results on real datasets show that the proposed algorithm can mine high quality communities from bipartite network.

Key words: Bipartite network, Incremental modularity, Label propagation, Mining communities

中图分类号:

TP301.6

戴彩艳, 陈崚, 胡孔法. 基于模块度增量的二分网络社区挖掘算法[J]. 计算机科学, 2018, 45(6A): 442-446. https://doi.org/

DAI Cai-yan, CHEN Ling, HU Kong-fa. Algorithm for Mining Bipartite Network Based on Incremental Modularity[J]. Computer Science, 2018, 45(6A): 442-446. https://doi.org/

参考文献

[1]BECKETT S J.Improved community detection in weighted bi partite networks[J].Royal Society Open Science,2016,3(1):140536.
[2]CUI Y Z,WANG X Y.Uncovering overlapping community structures by the key bi-community and intimate degree in bipartite networks[J].Physica A:Statistical Mechanics and Its Applications,2014,407(407):7-14.
[3]陈伯伦,陈峻,邹盛荣,等.基于矩阵分解的二分网络社区挖掘算法[J].计算机科学,2014,41(2):55-58,101.
[4]辛宇,杨静,谢志强.一种面向语义重叠社区发现的 Link-Block 算法[J].软件学报,2016,27(2):363-380.
[5]HORVAT E A,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.
[6]刘大有,金弟,何东晓,等.复杂网络社区挖掘综述[J].计算机研究与发展,2013,50(10):2140-2154.
[7]BECKETT S J.Improved community detection in weighted bi partite networks[J].Royal Society Open Science,2016,3(1):140536.
[8]LI J,WANG X,CUI Y. Uncovering the overlapping community structure of complex networks by maximal cliques.Physica A Statistical Mechanics & Its Applications,2014,415:398-406.
[9]HIMMELSTEIN D S,BARANZINI S E.Heterogeneous Net- work Edge Prediction:A Data Integration Approach to Prioritize Disease-Associated GenesJ].Plos Computational Biology,2015,11(7):e1004259.
[10]IBRAHIM N M A,CHEN L.Link prediction in dynamic social networks by integrating different types of information[J].Applied Intelligence,2015,42(4):738-750.
[11]王祯骏,王树徽,张维刚,等.基于社交内容的潜在影响力传播模型[J].计算机学报,2016,39(8):1528-1539.
[12]GAO F,MUSIAL K,COOPER C,et al.Link prediction methods and their accuracy for different social networks and network metrics[J].Scientific Programming,2015,2015:1-13.
[13]CHEN G,WANG Y.Community detection in complex networks using extremal optimization modularity density[J].Journal of Huazhong University of Science & Technology,2011,39(4):82-85.
[14]LI Z,ZHANG S,ZHANG X.Modularity and community detection in bipartite networks[J].American Journal of Operations Research,2015,5(5):421-434.
[15]BAKER A.Complexity,Networks,and Non-Uniqueness [J]. Foundations of Science,2013,18(4):687-705.
[16]KAYA B,POYRAZ M.Age-series based link prediction in evolving disease networks[J].Computers in Biology and Medicine,2015,63:1-10.
[17]GUIMERA R,SALES-PARDO M,AMARAL L A.Module identification in bipartite and directed networks[J].Physical Review E,2007,76(2):066102.
[18]MICHAEL J.BARBER.Modularity and community detection in bipartite networks[J].Physical Review E,2007,76(2):066102.
[19]EWMAN M E J.The Structure and Function of Complex Networks [J].Siam Review,2003,45(2):167-256.
[20]MURATA T.Detecting communities from bipartite networks based on bipartite modularities[C]∥2009 InternationalCon-ference on Computational Science and Engineering.2009:50-57.
[21]LIU X,MURATA T.How does label propagation algorithm work in bipartite networks[C]∥2009 IEEE/WIC/ACM International Joint Conference on Web Intelligence and Intelligent Agent Technology(WI-IAT’09).2009:5-8.
[22]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(32):036106.
[23]FUJITA S,FUJINO A.Word Sense Disambiguation by Combining Labeled Data Expansion and Semi-Supervised Learning Method[J].Acm Transactions on Asian Language Information Processing,2013,12(2):1-26.
[24]LIU X,MURATA T.Community Detection in Large-scale Bi- partite Networks[C]∥ IEEE/WIC/ACM International Confe-rence on Web Intelligence and Intelligent Agent Technology.2009:50-57.
[25]DAVIS A,GARDNER B B,GARDNER M R.Deep South[M].University of Chicago Press,1941.
[26]ERGUN G.Human sexual contact network as a bipartite graph[J].Physica A,2002,308:483-488.
[27]ZHANG P,WANG D,XIAO J.Improving the recommender algorithms with the detectedcommunities in bipartite networks[J].Physica A,2017,471:147-153.
[28]SCOTT J,HUGHES M.The Anatomy of Scottish Capital:Scottish Companies and Scottish Capital.Economic History Review,1980,3(4):1900-1979.
[29]KARUMUR R P,NGUYEN T T,KONSTAN J A.Exploring the Value of Personality in Predicting Rating Behaviors:A Studyof Category Preferences on MovieLens∥ACM Conference on Recommender Systems.2016:139-142.

Metrics

Viewed

Full text

Abstract

Cited

Shared

Discussed