摘要
社区结构是复杂网络中普遍存在的模块化特征。这体现在网络中的节点可以被分为多个内部连接相比于网络其他部分更加紧密的节点簇，这一过程称为社区发现。对复杂网络进行社区发现，有助于分析网络中个体的局部性特征及其相互之间的关联关系，对理解整个网络的结构和功能具有至关重要的意义。当前社区发现已经在蛋白质结构分析、传染病防治、商品推荐和互联网通信等多个领域得到了应用。 目前，大多数社区发现算法基于社区质量评价指标搜索网络的最优社区划分。然而许多社区质量评价指标并不能准确度量社区结构，其主要原因在于：一方面，这些指标忽略了社区发现过程中的社区稳定性；另一方面，基于拓扑结构的社区质量评价指标往往存在分辨率极限问题和社区内聚度识别问题。除此之外，现有算法在社区发现策略上难以平衡搜索范围和效率的矛盾。这些问题限制了算法在真实世界数据集上的稳定性和准确度。 针对以上问题，本文在分析了相关工作的基础上，基于社区划分间的平均互信息，网络结构与社区划分之间的互信息，以及节点间的点互信息，提出了对应的社区质量评价指标，并基于此实现了四种社区发现算法。本文主要研究内容及贡献如下： (1)基于社区划分间平均互信息的社区发现算法 通过社区划分间的平均互信息，我们从社区稳定性的角度对社区质量进行评价。在前期的研究中，这一思路被应用于GN算法和COPRA算法，得到了相比于原算法准确度更高的社区划分。但受限于社区发现策略，两种算法依然存在时间复杂度高、社区发现结果不稳定的问题。本文提出的AMI-NRL算法通过网络表征和层次聚类实现了更高效的社区发现策略，从而大幅降低了算法的时间复杂度。本文提出的另一个算法AMI-OMLPA则通过引入节点影响力和社区划分间的平均互信息进一步提升了多标签传播算法的稳定性和准确度。 (2)基于网络结构与社区划分间互信息的社区发现算法 作为基于拓扑结构的社区质量评价指标，网络结构与社区划分间的互信息在分辨率极限和社区内聚度识别上的表现优于广泛采用的模块度和二层平均编码长度指标。基于这一指标本文提出了MINC-NRL算法。该算法吸纳了使用网络表征和层次聚类作为社区发现策略的优点，同时解决了AMI-NRL算法在社区规模较小、社区数量较多时算法容易受到单个节点影响的问题。通过使用重叠层次聚类，算法有效避免了一些处于社区边缘的节点被过早分配到特定社区的情况，同时也具备了重叠社区发现的能力。实验表明，网络结构与社区划分间的互信息能准确评价非重叠和重叠社区划分的质量，MINC-NRL算法在真实世界数据集和人工数据集上均能得到准确的结果。 (3)基于节点间点互信息的社区发现算法 针对非重叠社区，谱方法是一种兼具准确性和稳定性的社区发现方法。谱方法通过构造节点间的相似矩阵实现社区发现，但目前方法所采用的相似矩阵仅提取图的特定结构特征，无法准确衡量节点间的联系，大部分谱方法还需要指定社区个数作为输入，而这在许多应用场景下是未知的。针对上述问题，我们基于节点间的点互信息构造拉普拉斯图核，提升了图核衡量节点间联系的能力，并通过引入社区质量评价指标QPMI解决社区个数未知条件下的谱聚类问题。实验表明，该算法在不同规模的真实世界数据集和人工数据集均能判断出网络中的社区个数，并得到准确的非重叠社区划分。
NETL