复杂网络中的邻域重叠社团结构探测

Overlapping community structure detection in complex networks

网络,数学家们称其为图,它为许多复杂系统的结构提供了一个很好的抽象,从社会网络、计算机网络,到生物网络以及物理系统的状态空间。在过去的几十年里出现了许多确定网络系统拓扑结构的改进实验,但对实验产生的数据进行科学的分析,仍然存在本质的挑战。目前的社团检测中主要存在两个问题:一是不知道网络中有几个社团;二是网络中的顶点可能属于不同的社团,也就是社团中存在重叠结构。为了了解各种重叠社团检测算法的思想、实现步骤、优缺点比较、算法应用,文中对邻域重叠社团检测算法进行了深入的分析,以k-means算法分析了经济网络,同时采用Silhouette指标解决了最佳聚类数的问题,并通过仿真实验证明了此算法的可能性。

Networks, also called graphs by mathematicians, provide a useful abstraction of the structure of many complex systems, rang- ing from social systems and computer networks to biological networks and the state spaces of physical systems. In the past decades, there have been significant advances in experiments to determine the topological structure of networked systems, but there remain substantial challenges in extracting scientific understanding from the large quantities of data produced by the experiments. There are two main difficulties in detecting community structure. The first is that it is not known that how many communities there are in a given network. Secondly, it is a common case that some nodes in a network can belong to more than one community. This means the overlapping community structure in complex networks. A new method for determining optimal number of clusters in K-means clustering algorithm is presented to analyze the economical network, select- ing the Silhouette validity index and setting initial clustering centers based on maximum and minimum distance algorithm. Simulation experi- ment and analysis demonstrate the feasibility of the above-mentioned algorithm.