基于核心节点影响力的社区发现方法

doi:10.11896/jsjkx.211100002

摘要/Abstract

摘要： 社区发现是复杂网络研究领域的一个热点问题,目前已经有许多局部社区发现算法被提出用于快速发现高质量的社区,不过它们往往存在种子节点依赖或是稳定性问题。因此,部分算法试图根据核心节点被邻居高度包围且相互之间距离较远的拓扑特性来精确地锁定种子节点以避免上述问题,但距离的计算使得其时间复杂度较高。文中提出了一种基于核心节点影响力的社区发现方法CDIC,该方法首先根据核心节点的拓扑特性和网络邻接信息寻找所有可能是核心的节点,之后利用真正核心节点影响力较高的性质和标签传播的思想来扩张社区,并淘汰被误选为核心的节点以避免种子依赖问题,同时不涉及最短距离的计算也保证了较低的时间复杂度,最后依据相似度理论提出了一种社区对节点的吸引力来合并特异节点,以保证算法结果的稳定性。将CDIC与6种经典算法以及2种近年来提出的算法在64个人工网络和4个真实网络上进行仿真实验,并对其社区划分结果对应的标准化互信息值和纯度进行了比较,结果表明了CDIC的有效性。

关键词: 复杂网络, 社区发现, 核心节点, 影响力, 社区吸引力

Abstract: Community discovery is a hot topic in the field of complex networks.Many local community detection algorithms have been proposed to quickly discover high-quality communities,but most of them have seed-dependent or stability problems.Some algorithms try to accurately find the seed nodes according to the topology characteristics of the core nodes that they are highly surrounded by neighbors and far away from each other to avoid the above problems.But the calculation of distance makes its time complexity is high.In this paper,a community detection method based on influence of core nodes(CDIC) is proposed.This me-thod first searches for all possible core nodes according to the topological characteristics of core nodes and network adjacency information.Then it uses the higher influential of true core nodes and the idea of label propagation to expand the communities and eliminate nodes wrongly selected as the core to avoid the seed-dependent problems.Besides,the calculation without distance also ensures low time complexity.Finally,a community attraction to nodes based on the similarity theory is proposed to merge specific nodes to ensure the stability of the results.The normalized mutual information and purity of the proposed method,6 classic algorithms and 2 algorithms proposed in recent years are compared on 64 artificial networks and 4 real networks.The results show the effectiveness of CDIC.

Key words: Complex network, Community discovery, Core node, Influence, Community attraction

中图分类号:

TP311

原慧琳, 韩真, 冯宠, 黄碧, 刘军涛. 基于核心节点影响力的社区发现方法[J]. 计算机科学, 2022, 49(11A): 211100002-7. https://doi.org/10.11896/jsjkx.211100002

YUAN Hui-lin, HAN Zhen, FENG Chong, HUANG Bi, LIU Jun-tao. Community Discovery Method Based on Influence of Core Nodes[J]. Computer Science, 2022, 49(11A): 211100002-7. https://doi.org/10.11896/jsjkx.211100002

参考文献

[1]SUN Z,SUN Y,CHANG X,et al.Community detection based on the Matthew effect[J].Knowledge-Based Systems,2020,205:106256.
[2]GIRVAN M,NEWMAN M E J.Community structure in social and biological networks[J].Proceedings of the National Academy of Sciences,2002,99(12):7821-7826.
[3]ZHANG Y,LIU Y,LI Q,et al.Lilpa:A label importance based label propagation algorithm for community detection with application to core drug discovery[J].Neurocomputing,2020,413:107-133.
[4]CHEN Z,XIE Z,ZHANG Q.Community detection based on local topological information and its application in power grid[J].Neurocomputing,2015,170:384-392.
[5]BAHULKAR A,SZYMANSKI B K,BAYCIK N O,et al.Community detection with edge augmentation in criminal networks[C]//2018 IEEE/ACM International Conference on Advances in Social Networks Analysis and Mining(ASONAM).IEEE,2018:1168-1175.
[6]ALSINI A,DATTA A,HUYNH D Q,et al.Community aware personalized hashtag recommendation in social networks[C]//Australasian Conference on Data Mining.Singapore:Springer,2018:216-227.
[7]ZHAO W J,ZHANG F B,LIU J L,Research progress of complex network community discovery[J].Computer Science,2020,47(2):10-20.
[8]NEWMAN M E J.Fast algorithm for detecting communitystructure in networks[J].Physical Review E,2004,69(6):066133.
[9]YUAN Q,LIU B.Community detection via an efficient nonconvex optimization approach based on modularity[J].Computational Statistics & Data Analysis,2021,157:107163.
[10]GUIMERA R,AMARAL L A N.Functional cartography ofcomplex metabolic networks[J].Nature,2005,433(7028):895-900.
[11]SHANG R,BAI J,JIAO L,et al.Community detection based on modularity and an improved genetic algorithm[J].Physica A,2013,392(5):1215-1231.
[12]FORTUNATO S.Community detection in graphs[J].Physics Reports,2010,486(3/4/5):75-174.
[13]NEWMAN M E J.Finding community structure in networksusing the eigenvectors of matrices[J].Physical Review E,2006,74(3):036104.
[14]NEWMAN M E J,LEICHT E A.Mixture models and exploratory analysis in networks[J].Proceedings of the National Aca-demy of Sciences,2007,104(23):9564-9569.
[15]PONS P,LATAPY M.Computing communities in large net-works using random walks[C]//International Symposium on Computer and Information Sciences.Berlin:Springer,2005:284-293.
[16]FANRONG M,MU Z,YONG Z,et al.Local Community Detection in Complex Networks Based on Maximum Cliques Extension [J].Mathematical Problems in Engineering,2014(2014):1-12.
[17]QI X,TANG W,WU Y,et al.Optimal local community detection in social networks based on density drop of subgraphs[J].Pattern Recognition Letters,2014,36:46-53.
[18]BERAHMAND K,BOUYER A,VASIGHI M.Community detection in complex networks by detecting and expanding core nodes through extended local similarity of nodes[J].IEEE Transactions on Computational Social Systems,2018,5(4):1021-1033.
[19]LIU S,XIA Z.A two-stage BFS local community detection algorithm based on node transfer similarity and Local Clustering Coefficient[J].Physica A:Statistical Mechanics and its Applications,2020,537:122717.
[20]RAGHAVAN U N,ALBERT R,KUMARA S.Near linear time algorithm to detect community structures in large-scale networks[J].Physical Review E,2007,76(3):036106.
[21]BAGROW J P,BOLLT E M.Local method for detecting communities[J].Physical Review E,2005,72(4):046108.
[22]RODRIGUEZ A,LAIO A.Clustering by fast search and find of density peaks[J].Science,2014,344(6191):1492-1496.
[23]YOU X,MA Y,LIU Z.A three-stage algorithm on community detection in social networks[J].Knowledge-Based Systems,2020,187:104822.
[24]DENG Z H,QIAO H H,GAO M Y,et al.Complex networkcommunity detection method by improved density peaks model[J].Physica A:Statistical Mechanics and its Applications,2019,526:121070.
[25]HENNIG C,HAUSDORF B.Design of dissimilarity measures:A new dissimilarity between species distribution areas[M]//Data Science and Classification.Berlin:Springer,2006:29-37.
[26]CLAUSET A,NEWMAN M E J,MOORE C.Finding community structure in very large networks[J].Physical Review E,2004,70(6):066111.
[27]BLONDEL V D,GUILLAUME J L,LAMBIOTTE R,et al.Fast unfolding of communities in large networks[J].Journal of Statistical Mechanics:Theory and Experiment,2008,2008(10):P10008.
[28]PAN X,XU G,WANG B,et al.A novel community detection algorithm based on local similarity of clustering coefficient in social networks[J].IEEE Access,2019,7:121586-121598.
[29]PARÉS F,GASULLA D G,VILALTAA,et al.Fluid communities:A competitive,scalable and diverse community detection algorithm[C]//International Conference on Complex Networks and Their Applications.Cham:Springer,2017:229-240.
[30]SHANG R,ZHANG W,JIAO L.Circularly searching corenodes based label propagation algorithm for community detection[J].International Journal of Pattern Recognition and Artificial Intelligence,2016,30(8):1659024.
[31]BERAHMAND K,BOUYER A.LP-LPA:A link influence-based label propagation algorithm for discovering community structures in networks[J].International Journal of Modern Physics B,2018,32(6):1850062.
[32]YAKOUBI Z,KANAWATI R.LICOD:A Leader-driven algo-rithm for community detection in complex networks[J].Vietnam Journal of Computer Science,2014,1(4):241-256.
[33]YIN C,ZHU S,CHEN H,et al.A method for community detection of complex networks based on hierarchical clustering[J].International Journal of Distributed Sensor Networks,2015,11(6):849140.
[34]WANG X,LIU G,LI J,et al.Locating structural centers:A density-based clustering method for community detection[J].PloS One,2017,12(1):e0169355.
[35]STREHL A,GHOSH J.Cluster ensembles-a knowledge reuseframework for combining multiple partitions[J].Journal of Machine Learning Research,2002,3(Dec):583-617.
[36]ZHAO Y,KARYPIS G.Empirical and theoretical comparisons of selected criterion functions for document clustering[J].Machine Learning,2004,55(3):311-331.
[37]LANCICHINETTI A,FORTUNATO S,RADICCHI F.Benchmark graphs for testing community detection algorithms[J].Physical Review E,2008,78(4):046110.
[38]ZACHARY W W.An Information Flow Model for Conflict and Fission in Small Groups[J].Journal of Anthropological Research,1977,33(4):452-473.
[39]LUSSEAU D,SCHNEIDER K,BOISSEAU O J,et al.The bottlenose dolphin community of Doubtful Sound features a large proportion of long-lasting associations[J].Behavioral Ecology and Sociobiology,2003,54(4):396-405.
[40]ADAMIC L A,GLANCE N.The political blogosphere and the 2004 US election:divided they blog[C]//Proceedings of the 3rd International Workshop on Link Discovery.2005:36-43.

相关文章 15

[1]	郑文萍, 刘美麟, 杨贵. 一种基于节点稳定性和邻域相似性的社区发现算法 Community Detection Algorithm Based on Node Stability and Neighbor Similarity 计算机科学, 2022, 49(9): 83-91. https://doi.org/10.11896/jsjkx.220400146
[2]	孔世明, 冯永, 张嘉云. 融合知识图谱的多层次传承影响力计算与泛化研究 Multi-level Inheritance Influence Calculation and Generalization Based on Knowledge Graph 计算机科学, 2022, 49(9): 221-227. https://doi.org/10.11896/jsjkx.210700144
[3]	何强, 尹震宇, 黄敏, 王兴伟, 王源田, 崔硕, 赵勇. 基于大数据的进化网络影响力分析研究综述 Survey of Influence Analysis of Evolutionary Network Based on Big Data 计算机科学, 2022, 49(8): 1-11. https://doi.org/10.11896/jsjkx.210700240
[4]	何亦琛, 毛宜军, 谢贤芬, 古万荣. 基于点割集图分割的矩阵变换与分解的推荐算法 Matrix Transformation and Factorization Based on Graph Partitioning by Vertex Separator for Recommendation 计算机科学, 2022, 49(6A): 272-279. https://doi.org/10.11896/jsjkx.210600159
[5]	何茜, 贺可太, 王金山, 林绅文, 杨菁林, 冯玉超. 比特币实体交易模式分析 Analysis of Bitcoin Entity Transaction Patterns 计算机科学, 2022, 49(6A): 502-507. https://doi.org/10.11896/jsjkx.210600178
[6]	杨波, 李远彪. 数据科学与大数据技术课程体系的复杂网络分析 Complex Network Analysis on Curriculum System of Data Science and Big Data Technology 计算机科学, 2022, 49(6A): 680-685. https://doi.org/10.11896/jsjkx.210800123
[7]	魏鹏, 马玉亮, 袁野, 吴安彪. 用户行为驱动的时序影响力最大化问题研究 Study on Temporal Influence Maximization Driven by User Behavior 计算机科学, 2022, 49(6): 119-126. https://doi.org/10.11896/jsjkx.210700145
[8]	王本钰, 顾益军, 彭舒凡, 郑棣文. 融合动态距离和随机竞争学习的社区发现算法 Community Detection Algorithm Based on Dynamic Distance and Stochastic Competitive Learning 计算机科学, 2022, 49(5): 170-178. https://doi.org/10.11896/jsjkx.210300206
[9]	唐春阳, 肖玉芝, 赵海兴, 冶忠林, 张娜. 面向双层网络的EWCC社区发现算法 EWCC Community Discovery Algorithm for Two-Layer Network 计算机科学, 2022, 49(4): 49-55. https://doi.org/10.11896/jsjkx.210800275
[10]	陈世聪, 袁得嵛, 黄淑华, 杨明. 基于结构深度网络嵌入模型的节点标签分类算法 Node Label Classification Algorithm Based on Structural Depth Network Embedding Model 计算机科学, 2022, 49(3): 105-112. https://doi.org/10.11896/jsjkx.201000177
[11]	杨旭华, 王磊, 叶蕾, 张端, 周艳波, 龙海霞. 基于节点相似性和网络嵌入的复杂网络社区发现算法 Complex Network Community Detection Algorithm Based on Node Similarity and Network Embedding 计算机科学, 2022, 49(3): 121-128. https://doi.org/10.11896/jsjkx.210200009
[12]	邵玉, 陈崚, 刘维. 独立级联模型下基于最大似然的负影响力源定位方法 Maximum Likelihood-based Method for Locating Source of Negative Influence Spreading Under Independent Cascade Model 计算机科学, 2022, 49(2): 204-215. https://doi.org/10.11896/jsjkx.201100190
[13]	赵学磊, 季新生, 刘树新, 李英乐, 李海涛. 基于路径连接强度的有向网络链路预测方法 Link Prediction Method for Directed Networks Based on Path Connection Strength 计算机科学, 2022, 49(2): 216-222. https://doi.org/10.11896/jsjkx.210100107
[14]	潘雨, 王帅辉, 张磊, 胡谷雨, 邹军华, 王田丰, 潘志松. 复杂网络社团发现综述 Survey of Community Detection in Complex Network 计算机科学, 2022, 49(11A): 210800144-11. https://doi.org/10.11896/jsjkx.210800144
[15]	原慧琳, 冯宠. 基于k-shell熵的影响力节点的排序与识别 Ranking and Recognition of Influential Nodes Based on k-shell Entropy 计算机科学, 2022, 49(11A): 210800177-5. https://doi.org/10.11896/jsjkx.210800177

Metrics

Viewed

Full text

Abstract

Cited

Shared

Discussed