复杂网络簇结构探测——基于随机游走的蚁群算法

网络簇结构是复杂网络最普遍和最重要的拓扑属性之一,网络聚类问题就是要找出给定网络中的所有类簇.有很多实际应用问题可被建模成网络聚类问题.尽管目前已有许多网络聚类方法被提出,但如何进一步提高聚类精度,特别是在没有先验知识(如网络簇个数)的情况下如何发现合理的网络簇结构,仍是一个未能很好解决的难题.针对该问题,在马尔可夫随机游走思想的启发下,从仿生角度出发提出一种全新的网络聚类算法——基于随机游走的蚁群算法RWACO.该算法将蚁群算法的框架作为RWACO的基本框架,对于每一代,以马尔可夫随机游走模型作为启发式规则；基于集成学习思想,将蚂蚁的局部解融合为全局解,并用其更新信息素矩阵.通过“强化簇内连接,弱化簇间连接”这一进化策略,使网络簇结构逐渐地呈现出来.实验结果表明,对一些典型的计算机生成网络和真实网络,该算法能够较准确地探测出网络的真实类簇数与一些有代表性的算法相比,具有较高的聚类精度.

Ant Colony Optimization Based on Random Walk for Community Detection in Complex Networks

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.