基于Monte-Carlo迭代求解策略的局部社区发现算法

doi:10.11772/j.issn.1001-9081.2021111942

《计算机应用》唯一官方网站 ›› 2023, Vol. 43 ›› Issue (1): 104-110.DOI: 10.11772/j.issn.1001-9081.2021111942

所属专题：数据科学与技术

基于Monte-Carlo迭代求解策略的局部社区发现算法

李占利, 李颖, 罗香玉, 罗颖骁

西安科技大学计算机科学与技术学院，西安 710600

收稿日期:2021-11-14 修回日期:2022-05-06 发布日期:2022-05-16
作者简介:李占利（1964—），男，陕西周至人，教授，博士，CCF会员，主要研究方向：机器学习、数据挖掘；李颖（1997—），女，山西临汾人，硕士研究生，主要研究方向：复杂网络、图计算；罗香玉（1984—），女，河北宁晋人，副教授，博士，CCF会员，主要研究方向：分布式存储、图计算 email：luoxiangyu@xust.edu.cn；罗颖骁（1998—），男，四川攀枝花人，硕士研究生，主要研究方向：时空数据分析、大规模图存储；
基金资助:
国家重点研发计划项目（2019YFB1405000）；陕西省自然科学基金资助项目（2020JM?526）。

Local community detection algorithm based on Monte-Carlo iterative solving strategy

LI Zhanli, LI Ying, LUO Xiangyu, LUO Yingxiao

College of Computer Science and Technology， Xi’an University of Science and Technology， Xi’an Shaanxi 710600， China

Received:2021-11-14 Revised:2022-05-06 Online:2022-05-16
Contact: LUO Xiangyu， born in 1984， Ph. D.， associate professor. Her research interests include distributed storage， graph computing.
About author:LI Zhanli， born in 1964， Ph. D.， professor. His research interests include machine learning， data mining；LI Ying， born in 1997， M. S. candidate. Her research interests include complex network， graph computing；LUO Yingxiao， born in 1998， M. S. candidate. His research interests include spatio-temporal data analysis， large-scale graph storage；
Supported by:
This work is partially supported by National Key Research and Development Program of China （2019YFB1405000）， Shaanxi Natural Science Foundation （2020JM-526）.

摘要/Abstract

摘要： 针对现有的局部社区发现算法因采用贪心策略进行社区扩张而导致的过早收敛和查全率低的问题，提出一种基于Monte-Carlo迭代求解策略的局部社区发现算法。首先，在每轮迭代的社区扩张阶段，根据节点对社区紧密度增益的贡献比例为所有邻接候选节点赋予选择概率，并结合此概率，再随机选择一个节点加入社区。然后，为避免随机选择导致扩张方向偏离目标社区，根据社区质量变化情况判断本轮迭代中是否触发节点淘汰机制。若触发，计算各个已加入社区节点与社区内其他节点的相似度和，根据相似度和的倒数赋予淘汰概率，并结合此概率，再随机淘汰一个节点。最后，在给定数量的最近迭代轮次中，根据社区规模是否增加判断是否继续迭代。在三个真实的网络数据集上进行实验，相较于局部紧密度扩展（LTE）算法、Clauset算法、加权共同邻居节点（CNWNN）算法和模糊相似关系（FSR）算法，所提算法的局部社区发现结果的F-score值分别提升了32.75、17.31、20.66和25.51个百分点，且能够有效避免查询节点在社区中所处位置对局部社区发现结果的影响。

关键词: 复杂网络, 社区结构, 局部社区发现, Monte-Carlo迭代求解策略

Abstract: Aiming at the problems of premature convergence and low recall caused by using greedy strategy for community expansion in the existing local community detection algorithms， a local community detection algorithm based on Monte-Carlo iterative solving strategy was proposed. Firstly， in the community expansion stage of each iteration， the selection probabilities were given to all adjacent candidate nodes according to the contribution ratio of each node to the community tightness gain， and one node was randomly selected to join the community according to these probabilities. Then， in order to avoid random selection causing the expansion direction to deviate from the target community， it was determined whether the node elimination mechanism was triggered in this round of iteration according to the changes in community quality. If it was triggered， the similarity sum of each node joining the community and other nodes in the community was calculated， the elimination probabilities were assigned according to the reciprocal of the similarity sum， a node was randomly eliminated according to these probabilities. Finally， whether to continue the iteration was judged on the basis of whether the community size increased in a given number of recent iteration rounds. Experimental results show that， on three real network datasets， compared to Local Tightness Expansion （LTE） algorithm， Clauset algorithm， Common Neighbors with Weighted Neighbor Nodes （CNWNN） algorithm and Fuzzy Similarity Relation （FSR） algorithm， the proposed algorithm has the F-score value of local community detection results increased by 32.75 percentage points， 17.31 percentage points， 20.66 percentage points and 25.51 percentage points respectively， and can effectively avoid the influence of the location of the query node in the community on the local community detection results.

Key words: complex network, community structure, local community detection, Monte-Carlo iterative solving strategy

中图分类号:

TP393.027

李占利, 李颖, 罗香玉, 罗颖骁. 基于Monte-Carlo迭代求解策略的局部社区发现算法[J]. 计算机应用, 2023, 43(1): 104-110.

LI Zhanli, LI Ying, LUO Xiangyu, LUO Yingxiao. Local community detection algorithm based on Monte-Carlo iterative solving strategy[J]. Journal of Computer Applications, 2023, 43(1): 104-110.

参考文献

1 STROGATZ S H. Exploring complex networks［J］. Nature， 2001， 410（6825）： 268-276. 10.1038/35065725
2 FANG Y X， HUANG X， QIN L， et al. A survey of community search over big graphs［J］. The VLDB Journal， 2020， 29（1）： 353-392. 10.1007/s00778-019-00556-x
3 GUO K， HUANG X T， WU L， et al. Local community detection algorithm based on local modularity density［J］. Applied Intelligence， 2022， 52（2）： 1238-1253. 10.1007/s10489-020-02052-0
4 RADICCHI F， CASTELLANO C， CECCONI F， et al. Defining and identifying communities in networks［J］. Proceedings of the National Academy of Sciences of the United States of America， 2004， 101（9）： 2658-2663. 10.1073/pnas.0400054101
5 NEWMAN M E J， GIRVAN M. Finding and evaluating community structure in networks［J］. Physical Review E， Statistical， Nonlinear， and Soft Matter Physics， 2004， 69（2）： No.026113. 10.1103/physreve.69.026113
6 CUI W Y， XIAO Y H， WANG H X， et al. Local search of communities in large graphs［C］// Proceedings of the 2014 ACM SIGMOD International Conference on Management of Data. New York： ACM， 2014： 991-1002. 10.1145/2588555.2612179
7 CHEN L， LIU C F， ZHOU R， et al. Maximum co-located community search in large scale social networks［J］. Proceedings of the VLDB Endowment， 2018， 11（10）： 1233-1246. 10.14778/3231751.3231755
8 竺俊超，王朝坤. 复杂条件下的社区搜索方法［J］. 软件学报， 2019， 30（3）： 552-572. ZHU J C， WANG C K. Approaches to community search under complex conditions［J］. Journal of Software， 2019， 30（3）： 552-572.
9 HE K， SHI P， BINDEL D， et al. Krylov subspace approximation for local community detection in large networks［J］. ACM Transactions on Knowledge Discovery from Data， 2019， 13（5）： No.52. 10.1145/3340708
10 LYU C， SHI Y H， SUN L J. A novel local community detection method using evolutionary computation［J］. IEEE Transactions on Cybernetics， 2021， 51（6）： 3348-3360. 10.1109/tcyb.2019.2933041
11 LIU J X SHAO Y X， SU S. Multiple local community detection via high-quality seed identification over both static and dynamic networks［J］. Data Science and Engineering， 2021， 6（3）： 249-264. 10.1007/s41019-021-00160-6
12 E W N， HAN J Q， JENTZEN A. Algorithms for solving high dimensional PDEs： from nonlinear Monte Carlo to machine learning ［J］. Nonlinearity， 2021， 35（1）： No.278. 10.1088/1361-6544/ac337f
13 ZACHARY W W. An information flow model for conflict and fission in small groups［J］. Journal of Anthropological Research， 1977， 33（4）： 452-473. 10.1086/jar.33.4.3629752
14 LUSSEAU D， SCHNEIDER K， BOISSEAU O J， et al. The bottlenose dolphin community of doubtful sound features a large proportion of long-lasting associations： can geographic isolation explain this unique trait？［J］. Behavioral Ecology and Sociobiology， 2003， 54（4）： 396-405. 10.1007/s00265-003-0651-y
15 LESKOVEC J， KLEINBERG J， FALOUTSOS C. Graphs over time： densification laws， shrinking diameters and possible explanations［C］// Proceedings of the 11th ACM SIGKDD International Conference on Knowledge Discovery and Data Mining. New York： ACM， 2005： 177-187. 10.1145/1081870.1081893
16 HUANG J B， SUN H L， LIU Y G， et al. Towards online multiresolution community detection in large-scale networks［J］. PLoS ONE， 2011， 6（8）： No.e23829. 10.1371/journal.pone.0023829
17 CLAUSET A. Finding local community structure in networks［J］. Physical Review E， Statistical， Nonlinear， and Soft Matter Physics， 2005， 72（2）： No.026132. 10.1103/physreve.72.026132
18 赵卫绩，张凤斌，刘井莲. 一种基于加权共同邻居相似度的局部社区发现算法［J］. 南京大学学报（自然科学）， 2018， 54（4）： 751-757. 10.13232/j.cnki.jnju.2018.04.010 ZHAO W J， ZHANG F B， LIU J L. A novel local community detection algorithm based on common neighbors similarity measurement with weighted neighbor nodes［J］. Journal of Nanjing University （Natural Science）， 2018， 54（4）： 751-757. 10.13232/j.cnki.jnju.2018.04.010
19 刘井莲，王大玲，冯时，等. 一种基于模糊相似关系的局部社区发现方法［J］. 软件学报， 2020， 31（11）： 3481-3491. LIU J L， WANG D L， FENG S， et al. Local community discovery approach based on fuzzy similarity relation［J］. Journal of Software， 2020， 31（11）：3481-3491.
20 LUO F， WANG J Z， PROMISLOW E. Exploring local community structures in large networks［J］. Web Intelligence and Agent Systems， 2008， 6（4）： 387-400. 10.3233/wia-2008-0147
21 LUO W J， ZHANG D F， JIANG H， et al. Local community detection with the dynamic membership function［J］. IEEE Transactions on Fuzzy Systems， 2018， 26（5）： 3136-3150. 10.1109/tfuzz.2018.2812148
22 SOZIO M， GIONIS A. The community-search problem and how to plan a successful cocktail party ［C］// Proceedings of the 16th ACM SIGKDD International Conference on Knowledge Discovery and Data Mining. New York： ACM， 2010： 939-948. 10.1145/1835804.1835923
23 FANG Y X， WANG Z R， CHENG R， et al. Effective and efficient community search over large directed graphs［J］. IEEE Transactions on Knowledge and Data Engineering， 2019， 31（11）： 2093-2107. 10.1109/tkde.2018.2872982
24 HUANG X， CHENG H， QIN L， et al. Querying k-truss community in large and dynamic graphs［C］// Proceedings of the 2014 ACM SIGMOD International Conference on Management of Data. New York： ACM， 2014： 1311-1322. 10.1145/2588555.2610495
25 AKBAS E， ZHAO P X. Truss-based community search： a truss-equivalence based indexing approach［J］. Proceedings of the VLDB Endowment， 2017， 10（11）： 1298-1309. 10.14778/3137628.3137640
26 YUAN L， QIN L， ZHANG W J， et al. Index-based densest clique percolation community search in networks［J］. IEEE Transactions on Knowledge and Data Engineering， 2018， 30（5）： 922-935. 10.1109/tkde.2017.2783933
27 TANG Z K， TANG Y， LI C Y， et al. A fast local community detection algorithm in complex networks［J］. World Wide Web， 2021， 24（6）： 1929-1955. 10.1007/s11280-021-00931-1
28 WU Y B， JIN R M， LI J， et al. Robust local community detection： on free rider effect and its elimination［J］. Proceedings of the VLDB Endowment， 2015， 8（7）： 798-809. 10.14778/2752939.2752948
29 BIAN Y C， NI J C， CHENG W， et al. Many heads are better than one： local community detection by the multi-walker chain［C］// Proceedings of the 2017 IEEE International Conference on Data Mining. Piscataway： IEEE， 2017： 21-30. 10.1109/icdm.2017.11
30 LUO D S， BIAN Y C， YAN Y W， et al. Local community detection in multiple networks ［C］// Proceedings of the 26th ACM SIGKDD International Conference on Knowledge Discovery and Data Mining. New York： ACM， 2020： 266-274. 10.1145/3394486.3403069
31 LUO W J， LU N N， NI L， et al. Local community detection by the nearest nodes with greater centrality［J］. Information Sciences， 2020， 517： 377-392. 10.1016/j.ins.2020.01.001
32 AGHAALIZADEH S， TAGHAVI AFSHORD S， BOUYER A， et al. A three-stage algorithm for local community detection based on the high node importance ranking in social networks［J］. Physica A： Statistical Mechanics and its Applications， 2021， 563： No.125420. 10.1016/j.physa.2020.125420

[1]	杜明, 顾万里, 周军锋, 王志军. 基于motif连通性的社区搜索方法[J]. 《计算机应用》唯一官方网站, 2023, 43(7): 2190-2199.
[2]	刘震宇, 王朝坤, 郭高扬. 面向动态网络的介数中心度并行算法[J]. 《计算机应用》唯一官方网站, 2023, 43(7): 1987-1993.
[3]	周琳, 肖玉芝, 刘鹏, 秦有鹏. 基于节点多关系的社团挖掘算法及其应用[J]. 《计算机应用》唯一官方网站, 2023, 43(5): 1489-1496.
[4]	李鹏, 王世林, 陈光武, 闫光辉. 基于改进的局部结构熵复杂网络重要节点挖掘[J]. 《计算机应用》唯一官方网站, 2023, 43(4): 1109-1114.
[5]	孟昱煜, 郭静. 信息熵改进主成分分析模型的链路预测算法[J]. 《计算机应用》唯一官方网站, 2022, 42(9): 2823-2829.
[6]	孙焕良, 彭程, 刘俊岭, 许景科. 面向“15分钟生活圈”社区结构的表示学习[J]. 《计算机应用》唯一官方网站, 2022, 42(6): 1782-1788.
[7]	郝志刚, 秦丽. 基于多属性综合评价的食品安全标准引用网络重要节点发现方法[J]. 《计算机应用》唯一官方网站, 2022, 42(4): 1178-1185.
[8]	胡军, 许正康, 刘立, 钟福金. 融合多粒度社区信息的网络嵌入方法[J]. 《计算机应用》唯一官方网站, 2022, 42(3): 663-670.
[9]	陈广福, 王海波, 连雁平. 基于高阶自包含协同过滤的有向网络链路预测[J]. 《计算机应用》唯一官方网站, 2022, 42(10): 3060-3068.
[10]	蔡彪, 李蕊岑, 吴媛媛. 相似性特征对链路预测的影响与增强[J]. 计算机应用, 2021, 41(9): 2569-2577.
[11]	李亚芳, 梁烨, 冯韦玮, 祖宝开, 康玉健. 基于社区优化的深度网络嵌入方法[J]. 计算机应用, 2021, 41(7): 1956-1963.
[12]	李萍, 汪芬, 陈祺东, 孙俊. 求解多目标社区发现问题的离散化随机漂移粒子群优化算法[J]. 计算机应用, 2021, 41(3): 803-811.
[13]	罗香玉, 李嘉楠, 罗晓霞, 王佳. 改进的动态图社区演化关系分析方法[J]. 计算机应用, 2020, 40(8): 2313-2318.
[14]	郑文萍, 岳香豆, 杨贵. 基于随机游走的改进标签传播算法[J]. 计算机应用, 2020, 40(12): 3423-3429.
[15]	成其伟, 陈启买, 贺超波, 刘海. 基于改进对称二值非负矩阵分解的重叠社区发现方法[J]. 计算机应用, 2020, 40(11): 3203-3210.

基于Monte-Carlo迭代求解策略的局部社区发现算法

Local community detection algorithm based on Monte-Carlo iterative solving strategy

RichHTML

PDF

可视化

摘要/Abstract

引用本文

使用本文

参考文献

相关文章 15

编辑推荐

Metrics