基于增量和密度的动态网络社团检测算法

复杂网络作为一种描述和分析现实复杂系统的重要工具而广受关注，学者们已经对网络的物理意义和数学特性等方面进行了深入地研究。复杂系统是随着时间不断变化的，将不同时刻的系统状态进行采样建模便形成了本文研究的复杂动态网络。对复杂动态网络进行社团检测和演化分析，有助于提高人们对整个网络特性和发展趋势的认识，具有重要的理论和实际意义。 复杂动态网络往往具有多个时刻，用传统的方法需要对每个时刻分别进行社团检测，然后分析社团之间的关系，这样不仅容易在相邻的时刻产生很大偏差的社团划分，还导致很高的时间复杂度。增量方法将前一时刻的社团检测结果作为下一时刻的输入，可以有效地降低时间复杂度，同时还可以保证前后时刻的社团检测结果具有较好的一致性。本文提出了一种增量和密度相结合的社团检测方法，对大部分增量相关节点进行基于社团归属度的调整，对新增节点进行局部的基于密度的扩展，克服了一般增量方法认为在不同时刻社团数目固定和不能产生新社团的缺陷。 本文在人工合成数据和真实网络数据进行实验，结果表明本文提出的算法可以在近似增量方法的时间复杂度，取得比增量方法更好的社团检测效果，具有良好的社团发现能力，可以用于大规模复杂动态网络的社团研究。此外，本文对真实网络中得到的社团结果，进行整体的社团演化分析，并对长期保留的社团进行节点生命周期的分析，发现了一些具有特定意义的社团结构。