【摘要】 社团探测技术对于理解和分析现实世界网络具有非常重要的意义.本文提出了一种新的动态社团探测算法,利用迭代技术高效而准确地揭示网络中的社团结构.首先引入一种新型的基于离散时间的动态系统,描述社团归属的从随机状态到最优划分的演化轨迹,进一步利用严格的数学分析找出了社团归属收敛到最优的条件.另外,本文还创新性地提出了划分指标函数的一般化形式,通过选择不同的参数,可以引申到几乎所有著名的指标函数.本文算法非常高效,计算复杂度分析显示算法需要的时间与稀疏网络节点的数量呈线性关系.除此之外,为了确定社团的最优数目,本文利用Markov状态转移矩阵及其特征系统给出了具体而严格的求解证明.最后,本文将算法应用到人工网络和实际网络中,结果显示算法不仅具有极高的准确性,还能够揭示很多有用的隐藏信息,如层次结构和社团交互模式等.更多还原

【Abstract】 Detection of communities or clustering is particularly valuable for understanding, analyzing and optimizing many natural and engineering complex networks, such as gene regulatory networks, smart grid and transportation networks. Present techniques relies heavily on the optimization or heuristic methods, which cannot balance the computational efficiency and accuracy. In this paper, we propose an iterative algorithm to realize the exact detection of network communities, by using a novel method based on dynamical system. We first introduce a discrete-time dynamical system that characterizes the evolutionary iteration of community membership from a random configure to the optimal one, and then specify the conditions that can direct the trajectory of this dynamical system to the convergence, which reveals the community label of each node. The computational complexity analysis shows the high-performance of our algorithm: The required computational time is linearly dependent on the total number of nodes in a sparse network. Analyzing the eigenvalue gap of the Markovian transition matrix, a rigorous theory is provided to find the optimal number of communities divided from a network.We also show that the new algorithm can be generalized to unify the conventional algorithms that are widely used.Finally, we perform extensive simulations using both synthetic and real-world benchmark networks to illustrate the nice performance of our method.更多还原