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

摘要：

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

关键词：社团挖掘、演化计算、动态迭代系统、近似线性时间

所属期刊栏目：43

分类号：TP393(计算技术、计算机技术)

资助基金：国家自然科学基金资助项目71401194,91324203,11131009

在线出版日期：2016-08-30（万方平台首次上网日期，不代表论文的发表时间）

页数：共6页

页码：395-399,412