一种基于拓扑势的网络社区发现方法

Community Discovery Method in Networks Based on Topological Potential

从数据场思想出发，提出了一种基于拓扑势的社区发现算法．该方法引入拓扑势描述网络节点间的相互作用，将每个社区视为拓扑势场的局部高势区，通过寻找被低势区域所分割的连通高势区域实现网络的社区划分．理论分析与实验结果表明，该方法无须用户指定社区个数等算法参数，能够揭示网络内在的社区结构及社区间具有不确定性的重叠节点现象．算法的时间复杂度为O（m＋n^3／r）～O（n^2），n为网络节点数，m为边数，2〈γ〈3为一个常数．

Inspired from the idea of data fields, a community discovery algorithm based on topological potential is proposed. The basic idea is that a topological potential function is introduced to analytically model the virtual interaction among all nodes in a network and, by regarding each community as a local high potential area, the community structure in the network can be uncovered by detecting all local high potential areas margined by low potential nodes. The experiments on some real-world networks show that the algorithm requires no input parameters and can discover the intrinsic or even overlapping community structure in networks. The time complexity of the algorithm is O（m＋n^3/r）-O（n^2）, where n is the number of nodes to be explored, m is the number of edges, and 2〈γ〈3 is a constant.