基于节点连接强度的社区发现算法

Community Discovery Algorithms Based on Node Connection Strength

摘要: 人们对网络中社区发现的算法越来越感兴趣。在复杂网络中，节点并不是独立地存在，从结构上看，如果两个节点的连接情况很相似，那么这两个节点很可能处于同一个社区内。在本文中，我们提出了一种基于节点连接强度的社区发现算法(BNCSA)，该算法基于节点之间的直接连接数与间接连接数，度量节点之间的连接强度，然后用参数控制网络的社区结构的粒度，可以有效避免现有经典算法中无法发现粒度小于一定量的小型社区的弊端。最后，我们进行了一些实验来验证新算法的划分结果。实验结果表明，该算法能够有效地发现真实网络中的社区结构。

Abstract: People are becoming more and more interested in the algorithm of community discovery in the network. In complex networks, nodes do not exist independently. From a structural point of view, if the connections of two nodes are similar, then the two nodes are likely to be in the same community. In this paper, we propose a new community discovery algorithm based on node connection strength (BNCSA), which is based on the connection strength between the number of direct connections and the number of indirect connections between nodes. Then, parameters are used to control the community structure granularity of the network, so as to avoid the disadvantage that the existing classical algorithms cannot find small communities whose granularity is less than a certain amount. Finally, we conducted some experiments to verify the partitioning results of the new algorithm. Experimental results show that the algorithm can effectively discover the community structure in real networks.