基于节点相似性的复杂网络社区发现算法研究

摘要

复杂网络是众多现实复杂系统的抽象表现形式，其节点代表复杂系统中的个体，网络连边蕴含着系统个体间的某种内在联系。随着复杂网络的物理意义和数学特性的深入研究，实际网络中的一个共同性质，即社区结构，引起学者们的广泛关注。研究发现：整个网络是由若干个“社区”构成的，并且每个社区内部节点之间的连接相对紧密，但各个社区之间的连接却比较稀疏。复杂网络社区发现研究对分析复杂网络的拓扑和层次结构、理解社区的形成过程、预测复杂网络的演化趋势、发现复杂网络的独有特征等具有十分重要的理论意义与应用价值。 成功挖掘复杂网络社区的关键在于根据网络节点或边的特性设计合适且高效的社区发现算法。本文选择网络节点之间的余弦相似性和朴素相异性等指标作为划分社区节点的标准，分别设计出网络社区发现新算法，并基于其他几种重要的相似性指标获得多种相似性指标的最优组合，进一步获得Zachary空手道网络、海豚关系网络、美国足球网络和电力网络等真实网络的社区发现结果。 本文首先简要介绍复杂网络及其社区发现的概念、基本方法与研究意义。在此基础上，重点介绍了几类重要的社区发现算法及其划分思想，如K-L算法、谱二分法、GN算法、Newman快速算法等。然后，选择节点间的余弦相似性作为划分社区节点的标准，利用社区间的全局相似信息，通过迭代凝聚具有最大相似性的两个社区，得到网络社区发现结果；而最优社区数量由迭代过程中的模块度的最大值自动获得。利用新算法，获得Zachary空手道网络、海豚关系网络、美国足球网络和电力网络等真实网络的社区数量和最大模块度值，并通过实证分析获得多种相似性指标的最优组合结果。进一步，基于节点属于不同社区的相异特征，定义节点间的相异性度量，结合分裂算法思想进而设计出基于节点间相异性度量的新社区发现算法。实证发现，此算法的时间复杂度和社区发现结果的准确性等稍微优于GN算法。最后，总结了本文的研究工作，并对进一步的研究工作进行了展望。

目录

声明

1 绪论

1.1复杂网络的研究背景和意义

1.2 复杂网络社区发现的研究背景和意义

1.3 复杂网络社区发现的研究现状

1.4 本文的内容和结构

2 复杂网络社区发现基本理论与经典算法

2.1 复杂网络的主要概念

2.2 复杂网络社区结构的定义和评价指标

2.3 复杂网络社区发现算法

3 基于邻居节点余弦相似性的复杂网络社区发现算法

3.1 节点相似性

3.2 算法描述与示例

3.3 真实网络的社区发现结果

3.4 算法分析和比较

3.5 各种相似指标的比较和分析

3.6 本章小结

4 基于邻居节点相异性的复杂网络社区发现算法

4.2 算法描述与示例

4.4 算法分析与比较

5 总结与展望

5.1 本文的主要工作

5.2 工作的展望

致谢

参考文献

作者在读期间发表的学术论文及参加的科研项目