复杂网络中社区发现关键技术研究

摘要

现实世界中的很多复杂系统都可以抽象为一个复杂网络,如社会系统中的人际关系网,生态系统中的蛋白质交互网,科技系统中的万维网等。在这些复杂网络中,节点表示个体,节点之间的边表示个体之间的联系。大量的研究表明,复杂网络中普遍存在着社区结构,即社区内部的节点具有更加密切的联系。社区结构往往代表了具有相同属性或者扮演相似角色的节点集合。社区发现能够探究网络的结构与功能,发现其中隐藏的规律及预测其行为,是进行网络分析的基础和关键,因此具有重要的理论意义和广泛的应用前景。目前,社区发现已成为计算机等众多领域最具挑战性的基础研究课题之一。
　　本课题主要围绕复杂网络中的非重叠社区发现、重叠社区发现、动态网络社区发现以及局部社区发现等四个方面存在的问题进行研究,主要包括以下几个方面的内容:
　　1.大多数现有的社区发现算法都是非监督的学习方式,不能充分利用少量的先验知识以提高社区发现的质量,为此,提出一种基于快速近邻传播的半监督网络社区发现算法(SCAN-FAP),该算法主要包括基于约束的SimRank相似度和基于快速近邻传播的社区发现两部分,前者用于有效利用已知的先验知识,后者在前者的基础上充分利用所得到的相似度并提高社区发现的性能。实验结果表明,SCAN-FAP能够有效利用少量的先验知识,显著提高社区发现的质量,并且算法的性能优于其它几种代表性的半监督聚类算法。
　　2.为了能够更加有效地探测复杂网络中的重叠社区结构,提出一种基于链接密度聚类的重叠社区发现算法(DBLINK),该算法首先采用基于密度的聚类算法将网络中的边集划分为若干个互不相连的链接社区,然后将不属于任何链接社区的边孤立出来,只将有效的链接社区转化为具有重叠性的节点社区,从而避免了网络社区过度重叠的现象发生,并提高了重叠社区发现的质量。在模拟网络和真实网络上进行了测试,并与几种代表性的重叠社区发现算法进行比较,实验结果表明了DBLINK的高效性与有效性。
　　3.针对动态复杂网络的社区发现问题,在基于链接密度聚类的重叠社区发现算法基础之上,提出一种基于增量链接密度聚类的动态网络社区发现算法(iDBLINK),该算法通过相邻时刻边与边之间相似度的变化,对当前时刻的局部链接社区进行一定的更新,主要包括链接社区的创建、增长、合并、删除、收缩以及分裂等。该算法虽然只关注非重叠的链接社区的更新,却能够自然地反映出节点的重叠社区结构。在模拟网络和真实网络上的实验结果表明,相对于其它几种代表性的增量社区发现算法,iDBLINK能够更加有效地适应于动态网络的社区发现。
　　4.现有局部社区发现算法容易受到单一源节点的影响,且不能识别重叠节点所在的多个局部社区。针对该问题,提出一种基于节点极大团扩展的局部社区发现算法(LCD-MC),该算法首先找出包含指定节点的所有极大团的集合,然后在此基础上将各个未扩展的极大团作为初始局部社区,分别通过贪婪优化的算法不断地进行社区扩展。LCD-MC不仅能够得到比较稳定和准确的结果,而且当指定节点为重叠节点时,能够有效识别多个局部社区。在模拟网络和真实网络上进行了测试,并与具有代表性的局部社区发现算法进行比较,实验结果表明了LCD-MC的有效性。

目录

封面

声明

致谢

中文摘要

英文摘要

目录

Contents

图清单

表清单

1绪论

1.1 研究背景及意义（Background and Significance）

1.2 研究现状（Research Status）

1.3 研究内容（Research Content）

1.4 本文组织结构（Structure of the Dissertation）

2复杂网络社区发现相关理论基础

2.1 引言（Introduction）

2.2 复杂网络的表示及性质（ Representation and Properties of Complex Networks）

2.3 社区结构（Community Structure）

2.4 非重叠社区发现算法（Non-Overlapping Community Detection Algorithms）

2.5 重叠社区发现算法（ Overlapping Community Detection Algorithms）

2.6 社区发现的评价（Evaluation of Community Detection）

2.7 本章小结（Summary）

3 基于快速近邻传播的半监督非重叠社区发现

3.1 引言（Introduction）

3.2 相关工作（Related Work）

3.3 算法框架（Framework of Our Method）

3.4 基于约束的SimRank相似度（Constraint SimRank Similarity）

3.5 基于快速近邻传播的社区发现算法（ Community Detection Based on Fast Affinity Propagation）

3.6 时间复杂度（Time Complexity）

3.7 实验（Experimental Results）

3.8 本章小结（Summary）

4 基于链接密度聚类的重叠社区发现

4.1 引言（Introduction）

4.2 基于链接的重叠社区发现算法（ Link Based Overlapping Community Detection Algorithms）

4.3 基于链接密度聚类的重叠社区发现算法 DBLINK（Density Based Link Clustering Algorithm for Overlapping Community Detection, DBLINK）

4.4 实验（Experimental Results）

4.5 本章小结（Summary）

5基于增量链接密度聚类的动态网络社区发现

5.1 引言（Introduction）

5.2 动态网络社区发现（ Community Detection in Dynamic Networks）

5.3 问题定义（Definitions）

5.4 算法iDBLINK（Algorithm iDBLINK）

5.5 实验（Experimental Results）

5.6 本章小结（Summary）

6基于极大团扩展的局部社区发现

6.1 引言（Introduction）

6.2 局部社区发现算法（Local Community Detection Algorithms）

6.3 基于极大团扩展的局部社区发现算法 LCD-MC （ Local Community Detection Algorithm Based on Maximum Clique Extension, LCD-MC）

6.4 实验（Experimental Results）

6.5 本章小结（Summary）

7 结论与未来展望

7.1 主要研究成果（Main Contributions）

7.2 进一步研究的工作（Future Work）

参考文献

作者简历

学位论文数据集