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