基于随机重连的复杂网络社团结构特性分析

Analysis of Community Structure in Complex Networks Based on Random Rewiring

复杂网络的社团结构特性本质上是由网络的几阶度分布决定一直是网络科学领域悬而未决的问题之一。在保持网络一阶、二阶和三阶度相关特性不变的情形下,利用随机重连方法和社团检测算法研究了复杂网络的社团结构。通过对四种现实网络进行多次不同阶数的随机重连,发现一阶、二阶重连后,社团结构特性均随着重连次数的增加急剧下降,并在重连次数充分大后趋于稳定值。而保持网络3阶特性不变的随机重连所构造的网络,则可以很高的精度呈现原有网络的社团特性,从而表明网络的社团结构,可以由三阶度相关特性有效地刻画(不需要更高阶)。提供了一种网络构造方法,即利用3阶重连可构造体现现实网络社团结构等拓扑特性的随机网络。

By which order of degree distribution of networks,the community structure in complex networks can be remarkably maintained is always one problem up in the air in the network science.In this paper,the community structures of large-scale complex networks are studied based on community detection and random rewiring that maintains degree distribution of 1st-order,2nd-order and 3rd-order.We first analyze community structures of 4 representative realistic networks after random rewiring.Comparing with the analysis of the original networks,we find out that,after 1st-order or 2nd-order random rewiring,characteristics of community structure decline rapidly as the times of rewiring increase and they reach a stable level when the times of rewiring are large enough.However community structure is well maintained after 3rd-order random rewiring.We establish a path towards construction of random graphs matching the community structure property of real networks after the 3rd-order random rewiring.