论文部分内容阅读
近年来,随着各类新型社会媒体的快速发展,包含用户与用户之间的社交行为记录的数据积累呈现爆炸性增长,这为研究大规模的人类交互和集体行为提供了机会。本文所研究的社区发现(Community Detection)问题是社会计算的重要组成部分。通过对社区的挖掘,可以使人们加深对网络结构的理解,并将其应用于物理学、社会学、生物学、交通物流等各个领域。 目前绝大多数研究中社区发现算法是针对全局社区发现(Global CommunityDetection)问题的,它往往需要预先知道网络的整体结构,且在处理大规模网络时会遇到较大挑战。另一类社区发现问题被称为局部社区发现(Local CommunityDetection),它规避了全局社区发现的局限性,只要给定一个网络中的种子节点,利用网络的局部结构(主要指邻居关系)不断向外扩展社区来发现该种子节点所隶属的社区。在发现社区的过程中,局部社区度量用于评价每一个步骤中局部社区的质量,以此来选择下一步需扩展的节点。基于上述过程,局部社区发现中的关键问题是:(1)种子节点的选取导致的算法结果的差异;(2)局部社区度量的定义以及算法向外扩展策略的设计。 本文提出了新的局部社区度量方法来研究种子不敏感的局部社区发现算法,主要贡献如下: (1)针对现有算法采用不同种子节点时的结果不稳定问题,提出了基于d邻域节点连接相似度的种子不敏感的局部社区发现算法。d邻域包含了当前正在处理节点的直接相邻节点和非直接相邻节点。基于d邻域提出了新的节点连接相似度(d-neighbors相似度和wd-neighbors相似度),并由此定义了新的局部社区度量紧实-分隔指标(Compactness-Isolation,简称CI)。根据CI,提出了种子不敏感的局部社区发现算法GMAC和其改进版本iGMAC,并首次提出了两个针对局部社区发现算法的种子不敏感性评价标准“发现结果的一致性标准”和“一致性比率标准”。基于真实数据和人工合成数据的实验表明,GMAC和iGMAC算法能够准确地发现社区,同时对种子节点的敏感度也相对较低。 (2)针对局部社区算法的向外扩展策略,通过引入“依附边”的概念,提出了一种优先加边的局部社区发现算法EFIA。“依附边”的两个端点都与当前局部社区相连接,且在算法的迭代过程中的首先处理“依附边”,然后采用加点的策略处理其余的邻居节点。基于真实数据和人工合成数据的实验表明,EFIA算法能有效提高现有算法的准确度,特别是能较完整地发现真实社区(即求全率)。 (3)首次从准确性、种子不敏感性和处理噪音社区的鲁棒性三个方面对典型局部社区度量方法进行了实验评估,以帮助用户在各种实际应用中选择合适的局部社区度量。针对已有的各类文献提出的各种典型局部社区度量,首先从社区核心和边界区域的边紧凑程度以及内外部节点连接相似度的角度出发,归类整理了现有典型度量,其次通过引入两个新的局部社区算法不敏感性指标和处理带有噪音社区的能力的评价指标,对典型度量的准确性、种子不敏感性和处理噪音社区的鲁棒性进行了实验评估,分析了每种度量的优缺点,并给出了一系列建议帮助用户在各种实际应用中选择合适的局部社区度量。