大规模网络重叠社区发现技术研究

摘要

现实世界的很多复杂系统（如社会网络、蛋白质交互网络、因特网等）都是由相互联系的实体组成的，自然地以网络的形式存在或者可以用网络来表示。社区结构刻画了网络中节点间关系的局部聚集特性，一般由性质相似或功能相近的网络节点组成。重叠社区发现问题研究已经成为一个研究热点。深入分析与研究网络中的重叠社区结构，对于理解复杂系统的组成规律、预测系统的组成节点及系统本身的行为有着重要意义。本文从网络社区结构分析、重叠社区发现方法研究和原型系统验证等方面，研究了大规模网络的重叠社区发现方法和技术。本文主要工作如下：
　　1.提出了一种采用邻居投票机制的重叠社区发现方法。该方法受到支持向量机分类方法思想的启发，假设不同社区之间的重叠部分主要由社区的边界节点组成。该方法将网络重叠社区发现分为两个阶段：第一阶段对网络进行非重叠社区发现；第二阶段对社区边界节点的社区隶属情况进行判别。为此设计了基于局部信息的邻居投票机制。该方法适用于大规模复杂网络，且无需预知网络中的社区个数等先验知识。采用此方法设计并实现了LM-NV（Louvain method with neighbor voting）重叠社区发现算法，该算法在第一阶段采用了LM非重叠社区发现算法。LM-NV算法的时间复杂度在最坏的情况下为O(m+nk)，同网络中边的规模近似呈线性关系，具有良好的时间效率；在模拟网络数据和真实网络数据上的实验表明，该算法的社区发现准确度优于LFM,COPRA,LINK算法。
　　2.设计并实现了一种半监督的局部扩展式重叠社区发现算法SLEM（semi-supervised local expansion method）。该算法借鉴带约束的半监督聚类的思想，利用部分标注信息指导社区发现的过程，避免了非监督重叠社区发现算法的盲目性问题；采用基于网络节点度中心性的种子选取策略，能够得到局部性好、结构稳定的社区发现结果，解决了结果的抖动性问题；对社区发现结果的后处理，在保证高社区覆盖率的前提下尽量减少冗余的社区。在模拟网络数据和真实网络数据上的实验表明，对于稀疏程度不同的网络，综合考虑重叠模块度、社区连接密度和网络覆盖率三种指标，SLEM算法的社区发现结果优于NLEM,LFM,GCE算法的结果。
　　3.设计并实现了一个微博网络重叠社区发现原型系统。该系统通过分析节点信息和节点间连接关系，构建微博用户关系网络；采用LM-NV算法对网络进行重叠社区划分；将划分结果以可视化的方式进行交互展示，便于研究者直观地分析和研究网络社区结构。利用此系统构建了由新浪微博上机器学习、数据挖掘等领域用户形成的1489个节点、108064条边的用户关系网络，划分为5个重叠社区，并分析了各社区的属性和不同社区间的相关性。该结果验证了LM-NV算法的有效性，对关键人物挖掘和信息传播分析提供了支撑。

目录

封面

声明

中文摘要

英文摘要

目录

第一章 绪论

1.1 研究背景

1.2 研究目的及意义

1.3 国内外研究现状

1.4 本文主要工作

1.5 论文组织结构

第二章 社区发现相关研究

2.1 社区发现问题描述

2.2 典型的重叠社区发现算法

2.3 测试网络数据集

2.4 社区划分结果的评估

2.5 本章小结

第三章 采用邻居投票机制的重叠社区发现

3.1 相关知识

3.2 邻居投票机制的提出

3.3 LM-NV算法

3.4 对LM-NV算法性能的验证

3.5 本章小结

第四章 半监督的局部扩展式重叠社区发现

4.1 相关知识

4.2 SLEM算法

4.3 对SLEM算法性能的验证

4.4 本章小结

第五章 微博网络重叠社区发现原型系统

5.1 系统整体结构设计

5.2 系统主要功能

5.3 系统界面展示

5.4 社区发现结果解释与分析

5.5 本章小结

第六章 总结

6.1 本文工作总结

6.2 下一步研究展望

致谢

参考文献

作者简历