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

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

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

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 Fscore value of local community detection results increased by 32. 75 percentage points, 17. 31 percentage points, 20. 66percentage 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.