近似线性时间的社团结构动态演化挖掘算法

Near Linear Time Community Detection Algorithm Based on Dynamical Evolution

探测网络社团结构对于分析、设计复杂的自然或工程网络至关重要,然而现有的探测技术主要依托于最优化和启发式算法,不能兼顾计算效率和准确性。因此提出了一种基于演化迭代技术的动态社团探测算法,它能准确高效地发现网络中的社团结构。首先引入了一个离散时间的动态系统,通过描述社团划分收敛到特定指标最优的演化轨迹来确定社团划分。接着提出了一个一般化的指标函数,以确定网络中最优的社团数量及最稳定的社团结构。该指标函数极具概括性,改变相应的参数即可引申到各种已广泛应用的指标函数。针对参数选择的困难,利用图生成模型自动确定社团划分的指标函数。此算法效率很高,计算复杂度与稀疏网络中的节点数量呈近似线性关系。最后,在人工和真实网络中进行了大量的仿真实验来测试算法表现,结果显示所提算法能够揭示很多有价值的信息。

Detecting communities is is crucial for analyzing and designing complicated natural and engineering network.The existing community detection algorithms rely heavily on optimization and heuristic methods,which can not balance computational efficiency and accuracy simultaneously.Thus we proposed an evolutionary algorithm which uses a new dynamical system based on community membership vector to formulate the conditions driving the convergence of dynamics trajectory.Then,we proposed a quality function,which can unify the conventional algorithms by selecting appropriate parameters.Furthermore,considering the difficulty in choosing parameters,we established a graph generative model according to the network prior information,by which the optimum formalism of the quality function can be obtained automatically.Our algorithm is highly efficient and the computational complexity is nearly linear with the number of all nodes in a sparse network.Finally,extensive experiments were performed in both artificial and real networks,which reveal much useful information.