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

文档介绍：ISSN 1000-9825, CODEN RUXUEW E-mail: ******@iscas.
Journal of Software, , , August 2009, −2254
doi: . Tel/Fax: [phone]
© by Institute of Software, the Chinese Academy of Sciences. All rights reserved.

∗
一种基于拓扑势的网络社区发现方法
淦文燕 1, 赫南 2+, 李德毅 3, 王建民 1
1(清华大学软件学院,北京 100084)
2(北京航空航天大学计算机科学与技术系,北京 100191)
3(电子系统工程研究所,北京 100039)
Community Discovery Method works Based on Topological Potential
GAN Wen-Yan1, HE Nan2+, LI De-Yi3, WANG Jian-Min1
1(School of Software, Tsinghua University, Beijing 100084, China)
2(Department puter Science, Beijing University of Aeronautics and Astronautics, Beijing 100191, China)
3(Institute of Electronic System Engineering, Beijing 100039, China)
+ Corresponding author: E-mail: @
Gan WY, He N, Li DY, Wang JM. Community discovery method works based on topological potential.
Journal of Software, 2009,20(8):2241−2254. /1000-9825/
Abstract: Inspired from the idea of data fields, munity 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 work and, by regarding munity as a local high potential area, the
community structure in work can be uncovered by detecting all local high potential areas margined by low
potential nodes. The experiments on some real-works show that the algorithm requires no input parameters
and can discover the intrinsic or even munity structure works. The plexity of the
algorithm is O(m+n3/γ)~O(n2), where n is the number of nodes to be explored, m is the number of edges, and 2<γ<3
is a constant.
Key words: topological potential; data field; community discovery; work
摘要: 从数据场思想出发,
作用,将每个社区视为拓扑势场的局部高势区,
论分析与实验结果表明,该方法无须用户指定社区个数等算法参数,能够揭示网络内在的社区结构及社区间具有不
O(m+n3/γ)~O(n2),n 为网络节点数,m