基于类原型的复杂网络重叠社区发现方法

Overlapping Community Detection in Complex Networks Based on Cluster Prototypes

社区结构是复杂网络的重要拓扑特性之一.在现实世界中,网络的社区结构常具有重叠性.如何从网络中发掘出可靠的重叠社区是目前复杂网络社区发现研究的难点之一.直接优化Qov评价函数是一种解决重叠社区发现问题的方法,然而该方法易产生局部最优解.为解决该问题,利用类原型聚类算法的思想和概念,通过计算网络节点的类原型归属度信息,设计一个基于类原型的复杂网络重叠社区发现方法的框架,并将该框架应用于几种常见的聚类算法.实验结果表明,相比其它网络重叠社区发现算法,该方法不仅避免产生局部最优解,且具有适用性好、精度高的优点.

Community structure is one of the important topological characteristics in complex networks. In real world, community structures in networks are often overlapped. And it is difficult to efficiently detect overlapping communities in a network. Optimizing Qoo function directly is a solution for overlapping community detection, however, it is easy to generate a local optimal solution. To solve this problem, the concept of vertex central membership measure is introduced, and based on cluster prototypes of nodes in a network, an efficient framework is proposed to identify overlapping communities. Then the framework is applied to some classic clustering algorithms. The experimental results show that the proposed method avoids generating local optimal solution, and it is more efficient than the other algorithms on synthetic and real-world networks.