A Review of Community Detection in Hybrid Networks with Multiple Nodes and Multiple Relationships

  • Jiang Lu ,
  • Chen Yunwei
Expand
  • 1 Scientometrics&Evaluation Research Center(SERC), Chengdu Library and Information Center of Chinese Academy of Sciences, Chengdu 610041;
    2 Department of Library Information and Archives Management, School of Economics and Management, University of Chinese Academy of Sciences, Beijing 100190

Received date: 2021-04-06

  Revised date: 2021-08-02

  Online published: 2021-10-09

Abstract

[Purpose/significance] By sorting out the community detection methods of multi-node and multi-relationship hybrid network, we can analyze the problems and difficulties existing in the community detection methods, and predict the development trend in the future.[Method/process] In this paper, the methods of multi-node type and multi-relation type hybrid network community detection were systematically reviewed, and were described from five aspects:based on probabilistic generation model, meta-path, seed node, expansion modularity and isomorphism of hybrid networks. This paper summarized the commonly used evaluation indicators for community detection in hybrid networks:Standardized Mutual Information(NMI), Adjusted Rand Index(ARI) and Modularity Q, and pointed out three application scenarios of social media, academic network and fraud detection.[Result/conclusion] This paper summarizes the applicability, advantages and disadvantages of the community detection methods of multi-node and multi-relationship hybrid network, reveals the challenges faced by the current development, provides a new perspective for the subsequent hybrid network analysis and research, and looks forward to the related research directions that may be further expanded in the future.

Cite this article

Jiang Lu , Chen Yunwei . A Review of Community Detection in Hybrid Networks with Multiple Nodes and Multiple Relationships[J]. Library and Information Service, 2021 , 65(19) : 142 -150 . DOI: 10.13266/j.issn.0252-3116.2021.19.014

References

[1] NEWMAN M E J. Networks[M]. Oxford:Oxford University Press, 2018.
[2] WASSERMAN S, GALASKIEWICZ J. Advances in social network analysis:research in the social and behavioral sciences[M]. Los Angeles:Sage, 1994.
[3] BADER G D, HOGUE C W. An automated method for finding molecular complexes in large protein interaction networks[J]. BMC bioinform, 2003, 4(2):1-27.
[4] SPORNS O. Networks of the brain[M]. Cambridge:MIT Press, 2010.
[5] FORTUNATO S. Community detection in graphs[J]. Physics reports, 2009, 486(3):75-174.
[6] NEWMAN M E J, GIRVAN M. Finding and evaluating community structure in networks[J]. Physical review e, 2004, 69(2):026113.
[7] DUCH J, ARENAS A. Community detection in complex networks using extremal optimization[J]. Physical review e statistical nonlinear & soft matter physics, 2005, 72(2):027104.
[8] SCHLITT T, BRAZMA A. Current approaches to gene regulatory network modelling[J]. BMC bioinform, 2007, 8(6):1-22.
[9] 郑玉艳, 王明省, 石川, 等. 异质信息网络中基于元路径的社团发现算法研究[J]. 中文信息学报, 2018, 32(9):132-142.
[10] PORTER M A, ONNELA J P, MUCHA P J. Communities in networks[J]. Notices of the American Mathematical Society, 2009, 56(9):4294-4303.
[11] JAVED M A, YOUNIS M S, LATIF S, et al. Community detection in networks:a multidisciplinary review[J]. Journal of network and computer applications, 2018, 108(4):87-111.
[12] KARATAS A, SAHIN S. Application areas of community detection:a review[C]//2018 International congress on big data, deep learning and fighting cyber terrorism.Ankara:IEEE. 2018, 65-70.
[13] 李辉, 陈福才, 张建朋, 等. 复杂网络中的社团发现算法综述[J]. 计算机应用研究, 2021, 38(6):1611-1618.
[14] 张瑞红, 陈云伟, 邓勇. 用于科学结构分析的混合网络社团划分方法述评[J]. 图书情报工作, 2019, 63(4):135-141.
[15] 钱学森, 于景元, 戴汝为. 一个科学新领域——开放的复杂巨系统及其方法论[J]. 自然杂志, 1990, 13(1):3-10.
[16] MCCORD M R. Urban transportation networks:equilibrium analysis with mathematical programming methods[J]. Transportation research part a general, 1987, 21(6):481-484.
[17] 孙艺洲, 韩家炜. 异构信息网络挖掘:原理与方法[M]. 北京:机械工业出版社, 2016.
[18] 霍朝光, 张斌, 董克. 复杂网络视域下的学术行为预测研究述评:选题、合作与引用[J].情报理论与实践, 2021, 44(6):180-188,27.
[19] RAN W, SHI C, YU P S, et al. Integrating clustering and ranking on hybrid heterogeneous information network[C]//Pacific-Asia conference on knowledge discovery and data mining. Berlin:Springer, 2013:583-594.
[20] VAN DEN BESSELAAR P, HEIMERIKS G. Mapping research topics using word-reference co-occurrences:a method and an exploratory case study[J]. Scientometrics, 2006, 68(3):377-393.
[21] HAN J W. Mining heterogeneous information networks:principles and methodologies[J]. ACM sigkdd explorations newsletter. 2012, 3(2):1-159.
[22] 康宇航. 基于"耦合-共引"混合网络的技术机会分析[J]. 情报学报, 2017(2):170-179.
[23] BERLINGERIO M, COSCIA M, GIANNOTTI F. Finding and characterizing communities in multidimensional networks[J]. 2011 international conference on advance in social networks analysis and mining, 2011(8):490-494.
[24] SUTHERS D, FUSCO J, SCHANK P, et al. Discovery of community structures in a heterogeneous professional online network[J]. 2013 46th Hawaii international conference on system sciences, 2013(3):3262-3271.
[25] TANG L, LIU H. Community detection and mining in social media[J]. Community detection and mining in social media, 2010, 2(1):1-137.
[26] 张正林. 大规模异构信息网络社区发现算法与社区特征研究[D]. 北京:北京邮电大学, 2017.
[27] SUN Y Z, HAN J W, ZHAO P X, et al. RankClus:integrating clustering with ranking for heterogeneous information network analysis[C]//ACM sigkdd international conference on knowledge discovery & data mining. New York:ACM Press, 2009:565-576.
[28] SUN Y Z, HAN J W. Ranking-based clustering of heterogeneous information networks with star network schema[C]//ACM sigkdd international conference on knowledge discovery & data mining. New York:ACM Press, 2009:797-806.
[29] JI M, HAN J W, DANILEVSKY M. Ranking-based classification of heterogeneous information networks[C]//ACM sigkdd international conference on knowledge discovery & data mining. New York:ACM Press, 2011:1298-1306.
[30] 赵焕. 基于异构网络聚类的Web服务推荐系统研究[D]. 重庆:重庆大学,2015.
[31] GUPTA M, AGGARWAL C C, HAN J, et al. Evolutionary clustering and analysis of bibliographic networks[C]//International conference on advances in social networks analysis and mining. Taiwan:IEEE, 2011:63-70.
[32] QIU C H, CHEN W, WANG T J, et al. Overlapping community detection in directed heterogeneous social network[J]. Web-age information management, 2015(6):490-493.
[33] 陈毅. 基于统计推理的复杂网络社区结构分析[D]. 哈尔滨:哈尔滨工业大学, 2016.
[34] 殷浩潇, 李川. 异构信息网络概率模型研究及社区发现算法[J]. 现代计算机(专业版), 2016(3):3-6.
[35] SENGUPTA S, CHEN Y. Spectral clustering in heterogeneous networks[J]. Statistica sinica, 2015, 25(3):1081-1106.
[36] 童浩,余春艳. 基于排名分布的异构信息网络协同聚类算法[J]. 小型微型计算机系统, 2014, 35(11):2445-2449.
[37] WANG R, SHI C, YU P S, et al. Integrating clustering and ranking on hybrid heterogeneous information network[C]//Pacific-Asia conference on knowledge discovery and data mining. Berlin:Springer, 2013:583-594.
[38] 薛维佳. 异构信息网络中基于聚类的社区发现方法研究[D]. 包头:内蒙古科技大学, 2020.
[39] SUN Y Z, HAN J W, YAN X F, et al. Pathsim:meta path-based top-k similarity search in heterogeneous information networks[J]. Proceedings of the VLDB endowment, 2011, 4(11):992-1003.
[40] SHI C, LI Y T, ZHANG J W, et al. A survey of heterogeneous information network analysis[J]. IEEE transactions on knowledge and data engineering, 2017, 29(1):17-37.
[41] SHI C, YU P S. Heterogeneous information network analysis and applications[M]. Switzerland:Springer International Publishing, 2017:.
[42] LI J, SUN P Y, MAO Q R, et al. Path-Graph fusion based community detection over heterogeneous information network[C]//2018 IEEE 20th international conference on high performance computing and communications.New Jersey:IEEE, 2018:274-281.
[43] SHI C, KONG X N, YU P S, et al. Relevance search in heterogeneous networks[C]//Proceedings of the 15th international conference on extending database technology. New York:ACM Press, 2012:180-191.
[44] 丁平尖. 基于元路径的异构信息网络挖掘方法研究[D]. 长沙:湖南大学, 2015.
[45] MENG X F, SHI C, LI Y T, et al. Relevance measure in large-scale heterogeneous networks[C]//Asia-Pacific Web conference. Berlin:Springer, 2014:636-643.
[46] SUN Y Z,NORICK B,HAN J W, et al. Pathselclus:integrating meta-path selection with user-guided object clustering in heterogeneous information networks[J]. ACM transactions on knowledge discovery from data, 2013, 7(3):1-23.
[47] 吴瑶, 申德荣, 寇月, 等. 多元图融合的异构信息网嵌入[J]. 计算机研究与发展, 2020, 57(9):1928-1938.
[48] HMIMIDA M, KANAWATI R. Community detection in multiplex networks:a seed-centric approach[J]. Networks & heterogeneous media, 2015, 10(1):71-85.
[49] KANAWATI R. LICOD:leaders identification for community detection in complex networks[C]//2011 IEEE third international conference on privacy, security, risk and trust and 2011 IEEE third international conference on social computing. New Jersey:IEEE, 2011:577-582.
[50] PAPADOPOULOS S, KOMPATSIARIS Y, VAKALI A. A graph-based clustering scheme for identifying related tags in folksonomies[C]//Proceedings of the 12th international conference on data warehousing and knowledge discovery. Berlin:Springer, 2010:65-76.
[51] SHAH D, ZAMAN T. Community detection in networks:the leader-follower algorithm[J]. Workshop on networks across disciplines in theory and applications, 2010, 1050(2):1-8.
[52] YAKOUBI Z, KANAWATI R. LICOD:a Leader-driven algorithm for community detection in complex networks[J]. Vietnam journal of computer science, 2014, 1(4):241-256.
[53] TANG L, WANG X F, LIU H. Uncoverning groups via heterogeneous interaction analysis[C]//Ninth IEEE international conference on data mining. New Jersey:IEEE Computer Society, 2009:503-512.
[54] NICOSIA V, MANGIONI G, CARCHIOLO V, et al. Extending the definition of modularity to directed graphs with overlapping communities[J]. Journal of statistical mechanics:theory and experiment, 2009(3):3166-3168.
[55] GUIMERÀ R, MARTA S P, AMARAL L A. Module identification in bipartite and directed networks[J]. Physical review e statistical nonlinear & soft matter physics, 2007, 76(2):036102.
[56] MURATA T, IKEYA T. A new modularity for defecting one-to-many correspondence of communities in bipartite networks[J]. Advances in complex systems, 2010, 13(1):19-31.
[57] LIU X, LIU W C, MURATA T, et al. A framework for community detection in heterogeneous multi-relational networks[J]. Advances in complex systems, 2014, 17(6):1450018.
[58] LANCICHINETTI A, FORTUNATO S. Limits of modularity maximization in community detection[J]. Physical review e statistical nonlinear & soft matter physics, 2011, 84(6):066122.
[59] FORTUNATO S, BARTHÉLEMY M. Resolution limit in community detection[J]. Proceedings of the National Academy of Sciences of the United States of America, 2007, 104(1):36-41.
[60] LEE D D, SEUNG H S. Learning the parts of objects by non-negative matrix factorization[J]. Nature, 1999, 401(6755):788-791.
[61] JOLLIFFE I T. Principal component analysis[M]. Berlin:Springer-Verlag, 2002.
[62] SCHOLKOPFT B, MULLERT K-R. Fisher discriminant analysis with kernels[J]. Neural neworks for signal processing ix, 1999, 1(1):41-48.
[63] LIU T L, GONG M M, TAO D C. Large-cone nonnegative matrix factorization[J]. IEEE transactions on neural networks and learning systems, 2016, 28(9):2129-2142.
[64] TAFAVOGH S. Community detection on heterogeneous networks by multiple semantic-path clustering[C]//IEEE international conference on computational aspects of social networks. New Jersey:IEEE, 2014:7-12.
[65] ZHANG X C, LI H X, LIANG W X, et al. Multi-type co-clustering of general heterogeneous information networks via nonnegative matrix tri-factorization[C]//2016 IEEE 16th international conference on data mining. New Jersey:IEEE, 2016:1353-1358.
[66] 黄瑞阳, 吴奇, 朱宇航. 基于联合矩阵分解的动态异质网络社区发现方法[J]. 计算机应用研究, 2017, 34(10):2989-2992.
[67] LIU J, WANG J Z, LIU B H. Community detection of multi-layer attributed networks via penalized alternating factorization[J]. Mathematics, 2020, 8(2):239-258.
[68] 刘培奇, 孙捷焓. 基于LDA主题模型的标签传递算法[J]. 计算机应用, 2012, 2(2):403-406.
[69] MEI Q Z, CAI D, ZHANG D, et al. Topic modeling with network regularization[C]//Proceeding of the 17th international conference on World Wide Web. New York:ACM Press, 2008:101-110.
[70] 王婷. 异构社交网络中社区发现算法研究[D]. 北京:中国矿业大学, 2016.
[71] 保丽红. 主成分分析与线性判别分析降维比较[J]. 统计学与应用, 2020, 9(1):47-52.
[72] LIN L, XIA Z M, LI S H, et al. Detecting overlapping community structure via an improved spread algorithm based on pca[C]//International conference on computer science and software engineering. Lancaster:DEStec, 2014:115-121.
[73] LI L, FAN K F, ZHANG Z Y, et al. Community detection algorithm based on local expansion K-means[J]. Neural network world, 2016, 26(6):589-605.
[74] YUAN P Y, WANG W, SONG M Y. Detecting overlapping community structures with pca technology and member index[C]//Proceedings of the 9th EAI international conference on mobile multimedia communications. New York:ACM Press, 2016:121-125.
[75] LIU W, CHEN L. Community detection in disease-gene network based on principal component analysis[J]. Tsinghua science and technology, 2013, 18(5):454-461.
[76] 陈长赓. 异构信息网络下基于元路径的节点重要性度量和社区发现[D]. 昆明:云南大学, 2019.
[77] 高苌婕, 彭敦陆. 面向DBWorld数据挖掘的学术社区发现算法[J]. 计算机应用研究, 2017(7):2059-2062.
[78] SANTOS J M, EMBRECHTS M. On the use of the adjusted rand index as a metric for evaluating supervised classification[M]. Berlin:Springer, 2009.
[79] 王益文. 复杂网络节点影响力模型及其应用[D]. 杭州:浙江大学, 2015.
[80] KARATAS A, SAHIN S. Application areas of community detection:a review[J]. 2018 international congress on big data, deep learning and fighting cyber terrorism (ibigdelft), 2019(1):65-70.
[81] 张海涛, 周红磊, 张鑫蕊, 等. 在线社交网络的社区发现研究进展[J]. 图书情报工作, 2020, 64(9):142-152.
[82] QIAO Y Q, NIU K, DU S, et al. Community detection analysis of heterogeneous network[J]. 2015 international conference on cyber-enabled distributed computing and knowledge discovery, 2015(10):509-512.
[83] HUANG W H, LIU Y, CHEN Y G. Mixed membership stochastic blockmodels for heterogeneous networks[J]. Bayesian analysis, 2019, 15(3):711-736.
[84] 栾婷婷. 基于异构网络社区划分的医疗滥用检测研究[D]. 济南:山东大学, 2019.
[85] 刘殿中. 动态金融复杂数据的欺诈检测[D]. 青岛:青岛大学, 2020.
Outlines

/