均衡相似程度和紧密程度的局部社区发现算法

Local Community Detection Algorithm for Balancing Similarity and Tightness

基于局部扩展优化的社区发现方法因能有效揭示网络的社区结构、划分结果稳定等,备受关注.然而在这类方法中,如果种子节点选择不当、社区扩展过程中节点合并不当都会降低划分结果的合理性.此外,由于采用贪婪的扩展策略,其收敛速度受到了制约.针对以上问题,提出了均衡相似程度和紧密程度的局部社区发现算法.该算法利用节点间的相似程度和连接紧密程度构建种子社区,从种子社区出发以迭代的方式进行扩展直至收敛;在社区扩展过程中引入了一种两级筛选机制,利用该机制将在相似程度和连接紧密程度两方面优势均衡的多个节点合并到当前社区.通过构建种子社区和引入两级筛选机制提高社区划分结果的合理性.在社区扩展过程中引入合并策略,以优化算法收敛速度.在多个数据集上的对比实验证明了本文方法的正确性和有效性.

Community detection methods based on local extension optimization have attracted much attention because they can effectively reveal the community structure of the network and the partition results are stable.However,in this kind of method,if the seed node is not selected properly and the node is not merged properly in the process of community expansion,the rationality of the partition result will be reduced.In addition,the convergence rate is limited by the greedy expansion strategy.Aiming at the above problems,this paper proposes a local community detection algorithm that balances the similarity and closeness of nodes.It uses the similarity and closeness of nodes to construct the seed community,and expands from the seed community in an iterative way until convergence.In the process of community expansion,a two-level screening mechanism is introduced,which is used to merge multiple nodes with balanced advantages in similarity degree and closeness degree into the current community.The rationality of community division results is improved by constructing seed community and introducing two-level screening mechanism.The merging strategy is introduced in the process of community expansion to optimize the convergence speed of the algorithm.Comparative experiments on several datasets demonstrate the correctness and effectiveness of the proposed method.