基于动态系统的网络社团线性探测算法

发布时间：2018-06-04 11:29

本文选题：社团探测 + 动态系统　；参考：《中国科学:数学》2017年02期

【摘要】：社团探测技术对于理解和分析现实世界网络具有非常重要的意义.本文提出了一种新的动态社团探测算法,利用迭代技术高效而准确地揭示网络中的社团结构.首先引入一种新型的基于离散时间的动态系统,描述社团归属的从随机状态到最优划分的演化轨迹,进一步利用严格的数学分析找出了社团归属收敛到最优的条件.另外,本文还创新性地提出了划分指标函数的一般化形式,通过选择不同的参数,可以引申到几乎所有著名的指标函数.本文算法非常高效,计算复杂度分析显示算法需要的时间与稀疏网络节点的数量呈线性关系.除此之外,为了确定社团的最优数目,本文利用Markov状态转移矩阵及其特征系统给出了具体而严格的求解证明.最后,本文将算法应用到人工网络和实际网络中,结果显示算法不仅具有极高的准确性,还能够揭示很多有用的隐藏信息,如层次结构和社团交互模式等.
[Abstract]:Community detection technology is very important for understanding and analyzing real world networks. In this paper, a new dynamic community detection algorithm is proposed. The iterative technique is used to efficiently and accurately reveal the community structure in the network. Firstly, a new discrete time based dynamic system is introduced to describe the evolution of community attribution from random state to optimal partition, and the condition of community attribution converging to the optimum is found by strict mathematical analysis. In addition, this paper creatively proposes a general form of partitioning index functions, which can be extended to almost all famous index functions by selecting different parameters. The computational complexity analysis shows that the time required by the algorithm is linearly related to the number of sparse network nodes. In addition, in order to determine the optimal number of communities, a concrete and strict proof is given by using the Markov state transition matrix and its characteristic system. Finally, the algorithm is applied to artificial network and real network. The result shows that the algorithm not only has high accuracy, but also can reveal a lot of useful hidden information, such as hierarchical structure and community interaction mode.
【作者单位】：中央财经大学管理科学与工程学院;中国科学院数学与系统科学研究院;

【相似文献】