网络中极大k-plex发现算法和网络社群简历挖掘研究

摘要

针对网络的挖掘已经成为数据挖掘领域中的热点。由于需要用图结构来描述的数据广泛存在于生物、化学、通信和社会学等众多领域，因此针对网络的挖掘有着广泛的应用。社群是网络中的相对密集的区域，其内部实体间存在着紧密的连接，而区域之间相互隔离或只有少许联系桥接其间。网络社群是我们了解网络的结构、功能和增长机制的一个重要工具。本文的工作围绕着对网络社群的分析展开，大体分为下面两部分。 第一部分是对一种具体的社群结构——极大k-plex(k丛)的挖掘算法的研究。k-plex是众多网络社群定义中的一种，近年来一些使用k-plex对网络进行分析的方法和应用逐渐出现，但受没有高效的k-plex发现算法的限制，都只能局限在小规模网络上。我们提出了一种基于回溯的极大k-pleX挖掘算法并提出了若干剪枝策略来提升算法的性能。为了分析更大的网络，我们也讨论了算法的并行化，并研究了计算单元之间的负载均衡策略。我们还针对对k-plex规模的限制提出了一些近似算法策略以进一步提高算法的性能。在这一部分的最后，我们对算法和各种策略的效果进行了实验并且进行了分析。 应用各种算法从网络中挖掘出社群之后，为了进一步应用网络社群信息，更好的了解在现实中社群的概况和动态，我们又提出了针对网络社群的简历挖掘，并且研究了其中的三个问题：社群的特征化、社群的区分和社群演化历史的挖掘。社群的特征化算法试图提示社群形成的原因；社群区分算法则要寻找一个社群最独特的特征；而社群的演化历史挖掘则利用网络中不同时刻的快照来挖掘社群的演化轨迹。最后，我们用两个实际的案例来展示了社群简历挖掘的效果。

目录

文摘

英文文摘

声明

第1章 绪论

1.1 论文背景及目的

1.1.1 背景

1.1.2 研究目的

1.2 工作内容及成果

1.3 论文结构

第2章 相关技术研究现状

2.1 社群发现算法

2.1.1 图分割类算法

2.1.2 层次聚类算法

2.1.3 GN算法及其衍生算法

2.1.4 基于团重叠的算法

2.1.5 由团派生的结构及算法

2.2 网络社群简历挖掘相关工作

第3章 极大K-Plex发现算法

3.1 记号和相关概念

3.2 基本算法

3.3 直径剪枝

3.4 剪枝加速

3.5 并行算法

3.6 近似算法

3.7 实验

第4章 社群简历挖掘

4.1 核心成员发现

4.2 社群特征化

4.3 社群区分

4.4 社群演化挖掘

4.5 实验案例

4.5.1 电信呼叫网络简历挖掘

4.5.2 科研合作网络简历挖掘

第5章 结束语

参考文献

致谢

攻读学位期间发表的论文