摘要
互联网技术的飞速发展推动了社交信息的网络化进程。现实世界中许多信息系统都可以用网络结构来表示，而网络结构又可以进一步化分为多个大小不同的社区，社区是移动社交网络最重要的一个特征。如何对网络社区结构进行快速有效地识别是目前的研究热点。 本文针对现实生活中，人们通常隶属于多个社团这一现象，重点研究重叠社区的识别算法。在此基础上，进一步探讨网络重叠社区结构与强弱边之间的关系，主要研究内容如下: (1)传统的非负矩阵分解算法忽视了网络系统的可扩展性，在社区划分过程中导致时间复杂度和空间复杂度较高。针对此问题，本文提出了一种主成分分析(PCA)与隶属度指数(MI)相结合的算法，实现重叠社区结构的有效识别。该算法首先使用PCA技术挖掘网络中的关键特征，然后采用隶属度指标对节点进行分类。实验结果表明，该算法可以快速、高效地实现重叠社区结构的检测，并且模块度Q值也接近于传统算法。 (2)考虑到重叠社区中重叠节点所具有的独特性，重叠节点与非重叠节点之间的关系很难用传统的强弱关系定义。针对此问题，本文提出了重叠社区系数指标，基于该指标，对网络中节点度与强弱边以权值的形式进行重新界定，揭示节点之间所隐藏的复杂关系;在此基础上，通过改变重叠节点的数量来研究网络中强弱边的数量变化情况。进一步地，基于两种强弱边的划分方法，分析强弱边数量的变化情况。 (3)研究重叠点及强弱边在信息扩散中的作用，并以传染病为例，对4组真实数据集下传染病扩散速度进行统计和分析。实验结果显示在传染病预防过程中不仅要关注节点之间外在的联系，而且要考虑到节点之间内在的关系，这样才能更准确地发现那些重要节点，实现传染源的有效控制。 上述研究工作从重叠社区结构的角度出发，探索重叠社区结构与强弱边之间的关系。提出了一种新的节点度定义指标与强弱边判别方法，具有较高的理论意义和实际应用价值。
NETL