首页 | 本学科首页   官方微博 | 高级检索  
     检索      

检测网络社团结构的基于最短路径的$k$-均值算法
引用本文:高景璐.检测网络社团结构的基于最短路径的$k$-均值算法[J].数学研究及应用,2013,33(3):288-296.
作者姓名:高景璐
作者单位:吉林大学数学学院, 吉林 长春 130012
基金项目:国家自然科学基金(Grant No.10771085).
摘    要:我们考虑复杂网络社团结构的检测问题,即检测出那些具有高于平均密度的边所连接的节点的集合.本文我们利用模拟退火策略来极大化可表示为稳定效益函数的模量(modularity),并结合基于最短路径的$k$-均值迭代过程来对网络进行分区.该算法不仅能检测出社团,而且能够识别出在最短路径度量下,该社团中位于中心位置的节点.社团的最优数目可以在无需任何关于网络结构的先验信息下自动确定.对人工生成网络和真实世界中的网络的成功应用表明了算法的有效性.

关 键 词:社团结构    最短路径    $k$-均值.
收稿时间:2011/12/8 0:00:00
修稿时间:2011/12/20 0:00:00

Finding Community Structure in Networks Using a Shortest-Path-Based $k$-Means Algorithm
Jinglu GAO.Finding Community Structure in Networks Using a Shortest-Path-Based $k$-Means Algorithm[J].Journal of Mathematical Research with Applications,2013,33(3):288-296.
Authors:Jinglu GAO
Institution:School of Mathematics, Jilin University, Jilin 130012, P. R. China
Abstract: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.
Keywords:community structure  modularity  shortest path  $K$-means  simulated annealing  
点击此处可从《数学研究及应用》浏览原始摘要信息
点击此处可从《数学研究及应用》下载免费的PDF全文
设为首页 | 免责声明 | 关于勤云 | 加入收藏

Copyright©北京勤云科技发展有限公司  京ICP备09084417号