基于结构相似度的社区发现方法研究

摘要

现实中的许多系统都可以采用复杂网络进行描述，如物流网络、共享单车轨迹网络和互联网络等。复杂网络存在着许多重要的统计特性，如基于“六度分割”理论的小世界特性以及结点度符合幂律分布的无标度特性。此外，还有社区结构特性，即表现为同一社区内结点连边比较稠密而社区间连边则表现比较稀疏。社区发现有助于我们探测网络内部拓扑结构，发现网络隐藏规律，这对我们进一步理解网络功能，预测网络行为具有非常重要的理论意义和现实价值。目前，社区发现算法层出不穷，大致可分为采用启发式策略的算法、基于优化的算法以及其他算法。然而，这些算法依然存在着精确度不高、运行速度较慢等问题。为了解决上述问题，本文针对社区发现方法，主要开展了如下工作： 1、本文针对基于划分的社区发现算法计算权值时间复杂度高、迭代次数对网络边过于依赖的问题，将结构相似度与阈值相结合，提出了一种基于结构相似度和阈值的社区发现方法 SSTCA。该算法主要思想如下：(1)针对给定阈值 k，计算网络两点间的结构相似度作为这两点间边的权值。(2)通过删除结构相似度小于 k 的多条边；重复执行步骤(1)和步骤(2)，直到没有边删除为止，计算此时社区对应的模块性函数 Q；(3)将阈值增加步长?k，重复执行步骤(1),(2)，并计算对应的模块型函数 Q 值，直到达到阈值上限为止；(4)选取最大模块度对应的社区作为最终的社区划分结果。实验结果表明：该算法能够在保证社区划分精度的同时大大提高算法的运行速度。 2、本文针对基于传统遗传算法的社区发现方法生成的初始种群精确度不高，容易导致算法整体搜索性能不佳的问题，提出了一种基于改进遗传算法的社区发现方法SSGA。该方法将结构相似度与轮盘赌选择法相结合，使染色体的每个基因趋向于选择结构相似度较大的邻居结点，从而提高初始种群的社区划分质量并加速算法的收敛速度。本算法在人工基准网络和真实世界网络上进行了测试。实验结果表明：在人工基准网络中，SSGA算法生成的初始种群精确度和模块度比基于传统遗传算法的社区发现方法平均提高了18%和12%，算法整体划分精度比FEC和FN算法平均提高了24.02%和 22.01%；在真实世界网络中，SSGA 算法的社区划分精度均优于 FN、FEC和LPA算法。因此，SSGA算法不仅能够提高初始种群的精度，而且还具有较高的整体划分性能。

目录

声明

1绪论

1.1研究背景及意义

1.2国内外研究现状

1.3研究内容

1.4组织结构

2社区发现概述

2.1基础知识

2.2社区结构定义

2.3经典数据集

2.4小结

3基于结构相似度和阈值的社区发现方法

3.1概述

3.2算法思想

3.3实验结果及分析

3.4小结

4基于结构相似度和遗传算法的社区发现方法

4.1概述

4.2算法SSGA形式化描述

4.3实验分析

4.4小结

5总结与展望

5.1总结

5.2展望

参考文献

附录

附录1

致谢

攻读硕士学位期间所发表的学术论文