互联网技术的发展,推动着在线社会网络应用的进步,社交网络的火爆预示着大数据时代的到来。研究发现在线社会网络就是真实社会网络的缩影,它们都具有明显的社区结构特征。对社会网络研究分析,深入了解其网络结构特征、演化规律等有助于深入了解复杂社会网络系统,指导现实问题。社区发现是复杂网络中研究社区结构划分的一种发现技术,社区发现技术包括不允许重叠点和允许重叠点的社区发现。研究发现,重叠社区发现才更符合现实社会网络中一个节点可能会从属于多个社区这一现象。社会网络的每个社区或者人们说的小圈子中总会有影响力比较大的一个或某几个人,研究发现在线社会网络同样具有这一社交特征,本文从局部信息的思想和在线社交网络的特点出发,提出一种基于节点影响力和贡献度系数的可发现重叠点的社区发现算法—中心扩张CE算法。该方法以社区中心节点开始不断吸收邻居节点寻找此影响力最大的节点所在的社区成员进行社区划分,不需要事先指定社区的数目。算法使用中心扩张理论并提出贡献度系数、重叠度和社区偏向性的概念,更符合在线社交网络的特点,算法用空手道俱乐部(Zachary)社会网络、美式足球(American College Football)网络关系和某新浪微博用户粉丝关系网络进行验证,实验证明了CE算法的可靠性并能发现社区中的重叠点和重叠点的偏向性。能发现重叠点的社区发现算法己有不少,但是研究重叠点的算法很少或者说没有,本文在划分出重叠点的同时,还研究分析了重叠点的偏向性,即重叠点更偏向于从属哪个社区的问题。在论文的最后对全文的创新点和不足进行总结,并提出了论文下一步工作的展望与目标。
