高景璐.检测网络社团结构的基于最短路径的$k$-均值算法[J].数学研究及应用,2013,33(3):288~296
检测网络社团结构的基于最短路径的$k$-均值算法
Finding Community Structure in Networks Using a Shortest-Path-Based $k$-Means Algorithm
投稿时间:2011-12-08  最后修改时间:2011-12-20
DOI:10.3770/j.issn:2095-2651.2013.03.003
中文关键词:  社团结构  最短路径  $k$-均值.
英文关键词:community structure  modularity  shortest path  $K$-means  simulated annealing.
基金项目:国家自然科学基金(Grant No.10771085).
作者单位
高景璐 吉林大学数学学院, 吉林 长春 130012 
摘要点击次数: 1784
全文下载次数: 3018
中文摘要:
      我们考虑复杂网络社团结构的检测问题,即检测出那些具有高于平均密度的边所连接的节点的集合.本文我们利用模拟退火策略来极大化可表示为稳定效益函数的模量(modularity),并结合基于最短路径的$k$-均值迭代过程来对网络进行分区.该算法不仅能检测出社团,而且能够识别出在最短路径度量下,该社团中位于中心位置的节点.社团的最优数目可以在无需任何关于网络结构的先验信息下自动确定.对人工生成网络和真实世界中的网络的成功应用表明了算法的有效性.
英文摘要:
      We consider the problem of detecting the community structure in a complex network, groups of nodes with a higher-than-average density of edges connecting them. In this paper we use the simulated annealing strategy to maximize the modularity, which has been indicated as a robust benefit function, associating with a shortest-path-based $k$-means iterative procedure for network partition. The proposed algorithm can not only find the communities, but also identify the nodes which occupy central positions under the metric of the shortest path within the communities to which they belong. The optimal number of communities can be automatically determined without any prior knowledge about the network structure. The applications to both artificial and real-world networks demonstrate the effectiveness of our algorithm.
查看全文  查看/发表评论  下载PDF阅读器