论文部分内容阅读
近年来,社交网络蓬勃发展,网络的结构越来越复杂,基于社交网络的移动互联网应用越来越多。社交网络结构中的稠密子模块,代表了用户的群体。研究网络中的社区,有助于理解网络中的网络结构和网络的功能。而通过分析社区特征,有助于发现用户群体的需求,指导移动互联网应用提供精准的服务。由于服务的质量需求的提升,对社区质量和效率的要求也越来越高。对于中小规模的网络,模块度系列算法等由于考虑的特征不足,造成找到的社区的质量不高;MCL等算法没有抓住社交网络的稀疏性的特点,造成了算法的效率偏低。对于超大规模的社交网络,现有的局部社区发现算法,发现的社区包含无关子图,降低了局部社区的质量。因此,基于全局社区和局部社区存在的问题,本文做了两方面的工作。本文针对基于边关系的全局社区发现算法找到的社区质量不足、发现社区效率偏低等问题。首先提出了节点力的模型,量化了节点之间的相互影响。参考经典受力分析模型,给出了节点之间直接影响和间接影响的组合办法,得到了节点力的受力分析模型。接着,本文设计并实现了 Edge Pruning算法。算法的核心思想是每一轮迭代的时候,逐步删除最有可能的社区之间的连接边。由于受力分析模型考虑了节点之间的间接影响,使得模型更接近真实社交网络的情况,因而降低了误删的概率;Edge Pruning逐步删边的策略,逼近了真实社区的结构;此外,算法引入了局部特征,通过预筛选的机制,在降低误删的概率的同时,也减少了每一轮迭代的计算量。真实数据集和基准数据集上的实验表明,Edge Pruning算法在提高了发现社区的质量的同时,还降低了运行的时间。其次,针对现有的局部社区发现算法结果存在无关子图的问题,本文设计并实现了局部社区发现算法LCDFA。论文首先基于受力分析的模型,判别出强连边,根据贪心的思想,将强连接的节点归入同一个社区,设计并实现了子算法LFA。接着,LCDFA让LFA和Heat Kernel这两个子算法从两个不同的角度去发现同一个社区。然后,将这两个子算法的结果对所有的节点进行投票,得票数为两票的节点为最终的局部社区。真实数据集和基准数据集上的实验表明,LCDFA通过投票的办法,限制无关子图的大小,减少无关子图的影响,提高了局部社区的质量。