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

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

CLC Number:

TP301.6

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.

References

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

Related Articles 15

[1]	HE Xi, HE Ke-tai, WANG Jin-shan, LIN Shen-wen, YANG Jing-lin, FENG Yu-chao. Analysis of Bitcoin Entity Transaction Patterns [J]. Computer Science, 2022, 49(6A): 502-507.
[2]	CHU Jie, ZHANG Zheng-jun, TANG Xin-yao, HUANG Zhen-sheng. Label Propagation Algorithm Based on Weighted Samples and Consensus-rate [J]. Computer Science, 2021, 48(3): 214-219.
[3]	ZHOU Bo. Bipartite Network Recommendation Algorithm Based on Semantic Model [J]. Computer Science, 2020, 47(11A): 482-485.
[4]	ZHANG Xiao-qin, AN Xiao-dan, CAO Fu-yuan. Detecting Community from Bipartite Network Based on Spectral Clustering [J]. Computer Science, 2019, 46(4): 216-221.
[5]	ZHOU Bo. Research on Relationship Between Bipartite Network Recommendation Algorithm and Collaborative Filtering Algorithm [J]. Computer Science, 2019, 46(11A): 163-166.
[6]	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.
[7]	LI Zhen-dong, LUO Qi and SHI Li-li. Weighted Bipartite Network Recommendation Algorithm Based on Increasing Similarity Coefficient [J]. Computer Science, 2016, 43(7): 259-264.
[8]	LIU Su-qi, BAI Guang-wei and SHEN Hang. Taxonomy Construction Based on User Self-describing Tags [J]. Computer Science, 2016, 43(7): 224-229.
[9]	YAO Fei-ya and CHEN Ling. Similarity Propagation Based Link Prediction in Bipartite Networks [J]. Computer Science, 2016, 43(4): 86-91.
[10]	GAO Man, CHEN Ling and XU Yong-cheng. Projection Based Algorithm for Link Prediction in Bipartite Network [J]. Computer Science, 2016, 43(2): 118-123.
[11]	XU Wei, LIN Bo-gang, LIN Si-juan and YANG Yang. Assessment of User Influence in Social Networks Based on Multi-label Propagation [J]. Computer Science, 2016, 43(10): 135-140.
[12]	LENG Ya-jun, LU Qing and ZHANG Jun-ling. Using Bipartite Network for Enhancement of Collaborative Filtering [J]. Computer Science, 2015, 42(3): 256-260.
[13]	MA Jie-liang, HAN Lu, PAN Zhen-zhen and SONG Yan. Label Propagation Algorithm Based on Community Core for Community Detection [J]. Computer Science, 2015, 42(1): 119-121.
[14]	YANG Ge-lan,JIN Hui-xia,MENG Ling-zhong and ZHU Xing-hui. Graph-based Semi-supervised Dimensionality Reduction Algorithm [J]. Computer Science, 2014, 41(4): 280-282.
[15]	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.

Metrics

Viewed

Full text

Abstract

Cited

Shared

Discussed

Comments

Recommended 0

No Suggested Reading articles found!

Algorithm for Mining Bipartite Network Based on Incremental Modularity

PDF (PC)