多节点多关系的混合网络社团划分研究综述

doi:10.13266/j.issn.0252-3116.2021.19.014

图书情报工作 ›› 2021, Vol. 65 ›› Issue (19): 142-150.DOI: 10.13266/j.issn.0252-3116.2021.19.014

• 综述述评 • 上一篇

多节点多关系的混合网络社团划分研究综述

蒋璐^1,2, 陈云伟^1,2

1 中国科学院成都文献情报中心科学计量与科技评价研究中心(SERC) 成都 610041;
2 中国科学院大学经济与管理学院图书情报与档案管理系北京 100190

收稿日期:2021-04-06 修回日期:2021-08-02 出版日期:2021-10-05 发布日期:2021-10-09
通讯作者: 陈云伟(ORCID:0000-0002-6597-7416)),研究员,硕士生导师,通讯作者,E-mail:chenyw@clas.ac.cn
作者简介:蒋璐(ORCID:0000-0002-5514-9860),硕士研究生。
基金资助:
本文系国家社会科学基金项目"用于科学结构分析的混合网络的社团研究"（项目编号：19XTQ012）研究成果之一。

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

Jiang Lu^1,2, Chen Yunwei^1,2

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:2021-04-06 Revised:2021-08-02 Online:2021-10-05 Published:2021-10-09

摘要/Abstract

摘要： [目的/意义] 旨在对多节点多关系混合网络社团划分方法进行梳理，探析现有社团划分方法存在的问题及面临的困难，预见未来的发展趋势。[方法/过程] 对近年来有关多节点类型、多关系类型混合网络的社团划分方法研究工作进行系统梳理，从基于概率生成模型、元路径、种子节点、扩展模块度以及混合网络同构5个方面对划分方法进行阐述，归纳混合网络社团划分常用的评估指标：标准化互信息NMI、调整兰德指数ARI和模块度Q，指出社交媒体、学术网络、欺诈检测3个应用场景。[结果/结论] 归纳出多节点多关系混合网络社团划分方法的适用性及优缺点，揭示了当前发展面临的挑战，为后续的混合网络分析研究提供新的视角，并展望今后可能进一步拓展的相关研究方向。

关键词: 多节点, 多关系, 混合网络, 社团, 评估

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.

Key words: multi-node and multi-relation, hybrid network, community, evaluation

中图分类号:

G250

蒋璐, 陈云伟. 多节点多关系的混合网络社团划分研究综述[J]. 图书情报工作, 2021, 65(19): 142-150.

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.

参考文献

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

多节点多关系的混合网络社团划分研究综述

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

PDF

可视化

摘要/Abstract

引用本文

使用本文

参考文献

相关文章 15

编辑推荐

Metrics

[1]	宋凯, 冉从敬. 基于主题挖掘与专利评估的技术机会识别研究——以智慧农业为例[J]. 图书情报工作, 2023, 67(3): 61-71.
[2]	吴建华, 林晓晴. 小学图书馆阅读服务问题与对策研究——以福建省福州市为例[J]. 图书情报工作, 2022, 66(3): 19-25.
[3]	李春秋, 杜博雅, 耿骞, 宋宁远, 李子璇, 原顺梅. 医学科学数据开放平台FAIR原则的应用评估与调查分析[J]. 图书情报工作, 2022, 66(3): 72-82.
[4]	马海群, 邹纯龙, 王今. 总体国家安全观下国家情报评估制度的基本逻辑研究[J]. 图书情报工作, 2022, 66(2): 4-12.
[5]	邹纯龙, 马海群, 王今. 美国国家情报评估的影响因素与模式概化研究[J]. 图书情报工作, 2022, 66(2): 13-21.
[6]	王今, 马海群, 邹纯龙. 国家情报评估与决策的关系——基于多源流理论和认知心理学双重视角[J]. 图书情报工作, 2022, 66(2): 22-31.
[7]	王伟, 梁继文, 杨建林. 基于引文网络的领域主题层次结构识别方法研究[J]. 图书情报工作, 2022, 66(17): 81-92.
[8]	张吉玉, 张均胜. 考虑时序的单篇科技文献新颖性评估方法[J]. 图书情报工作, 2022, 66(17): 93-105.
[9]	周丹燕, 唐琼. 变化理论视角下公共图书馆服务项目成效评估研究[J]. 图书情报工作, 2022, 66(16): 48-56.
[10]	刘妍. 专利价值评估研究综述与趋势展望[J]. 图书情报工作, 2022, 66(15): 127-139.
[11]	罗祺姗, 王梦圆. 图书馆新冠专题资源应急保障成效评估研究——以中国科学院文献情报中心为例[J]. 图书情报工作, 2022, 66(14): 29-36.
[12]	安璐, 陈苗苗, 李纲. 社交媒体环境下突发事件严重性评估和预警机制研究[J]. 图书情报工作, 2021, 65(5): 98-109.
[13]	陈美, 梁乙凯. 加拿大隐私影响评估政策：历程、内容、分析与启示[J]. 图书情报工作, 2021, 65(17): 142-151.
[14]	叶兰. FAIR数据评估模型与工具研究[J]. 图书情报工作, 2021, 65(16): 138-147.
[15]	臧国全, 张凯亮, 闫励. 个人数据价值计量研究——基于改造的BDM机制[J]. 图书情报工作, 2020, 64(7): 103-109.