社交网络中社团发现机制的研究

发布时间：2017-12-10 06:21

  本文关键词：社交网络中社团发现机制的研究

  更多相关文章： 社区发现 非重叠社区 重叠社区 BSP Propinquity

【摘要】：复杂网络一般是指节点数量多且节点间交互关系复杂的网络。社区结构是复杂网络的拓扑特点之一,整个网络由若干社区构成,社区内部节点的交互频繁,社区间节点的交互较弱。如何从复杂网络中解构出社区结构,已成为复杂系统研究领域中一大热点。随着网络规模的逐渐增大,特别是Facebook、Twitter、微博等社交网络的崛起,复杂网络的规模指数上涨,不仅对社区发现算法的计算复杂度提出了苛刻的要求,同时也引入了对算法并行化的要求。在不考虑重叠社区的情况下,虽然目前已经提出了一些线性时间复杂度的算法,但由于这些算法通常采用较为激进的贪婪策略,因此在网络规模较大且稠密的图拓扑中结果并不可靠。在重叠社区发现算法中,现有方案通常需要经过多次计算来获得最佳的社团数,计算开销过大。同时,由于文献中多数社区发现算法均不具备并行能力,无法基于分割后的局部点集实现算法逻辑,这将很难满足复杂网络下海量数据的计算需求。基于此,本文分别针对非重叠社区和重叠社区,提出两个社区发现算法,以满足在大规模网络分析中实现高效并行计算的需求。本文针对相关程度矩阵的计算,提出了一种基于节点动态阈值调节的优化方式,不仅解决了现有算法收敛速度较慢的问题,同时引入了节点自身特性辅助阈值设置,提升了算法准确性。在权重设计方面,考虑原算法中相关程度矩阵各个组成部分的重要程度不同,进行了有区分度的权重设置,并增加了算法对加权图的支持。针对非重叠社区,提出了两个社区发现算法:基于关键节点的社区发现算法CKE(Community Detection based on Key Nodes Extracting)和基于谱聚类的社区发现算法SKC(SpectralKMeans Cluster based Detection)。CKE算法为了解决原算法中将连通组成部分作为社区结构导致社区间错误合并的问题,引入了点介数算法辅助筛选出关键节点,利用关键节点在多个社区间起桥梁作用这一特性,将其作为划分社区的分界节点,结合BFS算法实现非重叠社区。通过仿真可以证明,CKE算法能够准确找到关键节点,得到有效的社区划分。SKC算法则是利用了聚类思想,通过谱聚类将相关程度矩阵转换为效用矩阵,以完成社区划分。针对现有算法中K值和初心难以预估的问题,引入Canopy聚类辅助设置。针对重叠社区,提出了两个社区发现算法:基于点聚集的社区发现算法CCO(Core-clique Combination Optimization detection algorithm)和基于扩散标记的社区发现算法IMB(Iterative diffusion Markbased on high-Betweennes)。CCO算法以发掘高内聚度的点聚集为核心,通过在其上提取重叠节点完成社区发现。常规的重叠点发现策略通常以聚类密度进行判定,其计算复杂度较高,针对这一问题在CCO算法中提出了简化的解决策略。IMB算法则是通过扩散标记思想实现重叠社区的发现。为了保证不同规模的社区结构均能被提取,IMB算法引入了基准阈值?作为标准,利用其能够度量节点与邻接节点间紧密程度这一特性,实现扩散标记。通过仿真可以看出,在少量的几轮迭代标记后,即可获得较好的重叠社区划分结果。针对大规模网络分析中实现高效并行计算这一需求,需要为算法建立以节点为中心的并发模型,结合图的分割思想,引入分布式计算框架,才能取得较好的社区划分结果。因此,本文还探讨了如何在Hadoop上分布式执行上述几种算法,实现社区划分。
【学位授予单位】：电子科技大学
【学位级别】：硕士
【学位授予年份】：2015
【分类号】：O157.5
，

本文编号：1273466