主页期刊介绍编委会编辑部服务介绍道德声明在线审稿编委办公编辑办公English
     
在线出版
各期目录
纸质出版
分辑系列
论文检索
论文排行
综述文章
专刊文章
美文分享
各期封面
E-mail Alerts
RSS
旧版入口
中国科学院软件研究所
  
投稿指南 问题解答 下载区 收费标准 在线投稿
金弟,杨博,刘杰,刘大有,何东晓.复杂网络簇结构探测——基于随机游走的蚁群算法.软件学报,2012,23(3):451-464
复杂网络簇结构探测——基于随机游走的蚁群算法
Ant Colony Optimization Based on Random Walk for Community Detection in Complex Networks
投稿时间:2009-10-23  修订日期:2010-07-06
DOI:10.3724/SP.J.1001.2012.03996
中文关键词:  复杂网络  网络聚类  簇结构  随机游走  集成学习  蚁群算法
英文关键词:complex network  network clustering  community structure  random walk  ensemble learning  ant colony optimization
基金项目:国家自然科学基金(60873149, 60973088, 61133011); 教育部博士研究生学术新人奖(450060454018)
作者单位E-mail
金弟 吉林大学 计算机科学与技术学院,吉林 长春 130012
吉林大学 符号计算与知识工程教育部重点实验室,吉林 长春 130012 
 
杨博 吉林大学 计算机科学与技术学院,吉林 长春 130012
吉林大学 符号计算与知识工程教育部重点实验室,吉林 长春 130012 
 
刘杰 吉林大学 计算机科学与技术学院,吉林 长春 130012
吉林大学 符号计算与知识工程教育部重点实验室,吉林 长春 130012 
 
刘大有 吉林大学 计算机科学与技术学院,吉林 长春 130012
吉林大学 符号计算与知识工程教育部重点实验室,吉林 长春 130012 
dyliu@jlu.edu.cn 
何东晓 吉林大学 计算机科学与技术学院,吉林 长春 130012
吉林大学 符号计算与知识工程教育部重点实验室,吉林 长春 130012 
 
摘要点击次数: 3871
全文下载次数: 7237
中文摘要:
      网络簇结构是复杂网络最普遍和最重要的拓扑属性之一,网络聚类问题就是要找出给定网络中的所有类簇.有很多实际应用问题可被建模成网络聚类问题.尽管目前已有许多网络聚类方法被提出,但如何进一步提高聚类精度,特别是在没有先验知识(如网络簇个数)的情况下如何发现合理的网络簇结构,仍是一个未能很好解决的难题. 针对该问题,在马尔可夫随机游走思想的启发下,从仿生角度出发提出一种全新的网络聚类算法——基于随机游走的蚁群算法RWACO.该算法将蚁群算法的框架作为RWACO 的基本框架,对于每一代,以马尔可夫随机游走模型作为启发式规则;基于集成学习思想,将蚂蚁的局部解融合为全局解,并用其更新信息素矩阵.通过“强化簇内连接,弱化簇间连接”这一进化策略,使网络簇结构逐渐地呈现出来.实验结果表明,对一些典型的计算机生成网络和真实网络, 该算法能够较准确地探测出网络的真实类簇数,与一些有代表性的算法相比,具有较高的聚类精度.
英文摘要:
      Community structure is one of the most important topological properties in complex networks. The network clustering problem (NCP) refers to the detection of network community structures, and many practical problems can be modeled as NCPs. So far, lots of network clustering algorithms have been proposed. However, further improvements in the clustering accuracy, especially when discovering reasonable community structure without prior knowledge, still constitute an open problem. Building on Markov random walks, the paper addresses this problem with a novel ant colony optimization strategy, named as RWACO, which improves prior results on the NCPs and does not require knowledge of the number of communities present on a given network. The framework of ant colony optimization is taken as the basic framework in the RWACO algorithm. In each iteration, a Markov random walk model is taken as heuristic rule. All of the ants’ local solutions are aggregated to a global one through clustering ensemble, which then will be used to update a pheromone matrix. The strategy relies on the progressive strengthening of within-community links and the weakening of between-community links. Gradually, this converges to a solution where the underlying community structure of the complex network will become clearly visible. The performance of algorithm RWACO was tested against a set of benchmark computer-generated networks, and as well on real-world network data sets. Experimental results confirm the validity and improvements of this approach.
HTML  下载PDF全文  查看/发表评论  下载PDF阅读器
 

京公网安备 11040202500064号

主办单位:中国科学院软件研究所 中国计算机学会 京ICP备05046678号-4
编辑部电话:+86-10-62562563 E-mail: jos@iscas.ac.cn
Copyright 中国科学院软件研究所《软件学报》版权所有 All Rights Reserved
本刊全文数据库版权所有,未经许可,不得转载,本刊保留追究法律责任的权利