基于局部模块度的动态社团检测算法

摘要

随时间缓慢变化的复杂系统可以建模为抽象的动态网络。由于动态网络在社会学、生物信息学、物理、计算机等研究领域有广泛应用，越来越受到科研工作者的重视。近几年动态网络成为科研热门领域，具有实际意义的动态社团结构是动态网络中普遍而又重要的特征。
　　当前动态社团检测算法仍主要基于静态检测方法的相关理论基础。基于极大化Q函数的动态社团检测算法存在分辨率问题，即为了获得更优的模块度值小社团常被合并为大社团。另一方面，很多动态社团检测算法需要设置多个参数或阈值，这就要求对网络有一定的先验知识或需要借助Q函数对结果进行判定。而且，已有的动态社团检测算法不能识别出如社团间的重叠结构等重要拓扑特征。为解决上述问题，本文提出了一种基于进化聚类和局部模块度的重叠结构动态社团检测算法。基于局部模块度的社团检测方法，将整个网络的社团检测问题转化为自底向上的凝聚问题，能适应网络中规模不等、密度不均的社团结构。通过统计节点随机游走行为特征，增强无权网络的分辨率，并使用进化聚类框架下的时序开销嵌入技术来平衡当前社团的拓扑特征与历史信息，从而检测出社团演化的动态规律。该算法仅在进化聚类过程中对平衡因子进行设置，无需领域先验知识。
　　本文使用真实网络数据对该动态网络社团检测算法进行评估，包括Drosophila melanogaster数据集和科学家合作网络（DBLP）数据集。实验结果表明，基于进化聚类框架和局部模块度的动态社团检测算法与基于进化和局部优先的算法相比，扩展模块性指标提高了15％，显著提高了Drosophila melanogaster社团检测结果质量。并且，该算法能有效刻画出 DBLP中科研团队的动态演化过程。综上，该算法可适用于无社团结构先验知识的网络，有效检测出具有特定意义的小规模社团及其重叠结构。

目录

封面

声明

中文摘要

英文摘要

插图索引

表格索引

缩略语对照表

目录

第一章 绪论

1.1 研究背景及其意义

1.2 动态社团检测研究现状

1.3 本文工作及论文结构

第二章 动态网络分析基础

2.1 动态网络定义与表示

2.2 动态社团检测算法分析

2.3 动态社团演化分析

2.4 本章小结

第三章 动态社团检测算法

3.1 问题描述及定义

3.2 算法设计

3.3 本章小结

第四章 实验结果分析

4.1 实验数据

4.2 评价标准

4.3 实验结果分析

4.4 本章小结

第五章 总结与展望

参考文献

致谢

作者简介