Journal of Computer Applications ›› 2023, Vol. 43 ›› Issue (1): 104-110.DOI: 10.11772/j.issn.1001-9081.2021111942

Special Issue: 数据科学与技术

• Data science and technology • Previous Articles     Next Articles

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

LI Zhanli, LI Ying, LUO Xiangyu, LUO Yingxiao   

  1. 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).


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

  1. 西安科技大学 计算机科学与技术学院,西安 710600
  • 作者简介:李占利(1964—),男,陕西周至人,教授,博士,CCF会员,主要研究方向:机器学习、数据挖掘;李颖(1997—),女,山西临汾人,硕士研究生,主要研究方向:复杂网络、图计算;罗香玉(1984—),女,河北宁晋人,副教授,博士,CCF会员,主要研究方向:分布式存储、图计算;罗颖骁(1998—),男,四川攀枝花人,硕士研究生,主要研究方向:时空数据分析、大规模图存储;
  • 基金资助:

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

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

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

CLC Number: