论文部分内容阅读
近年来,随着互联网(Internet)的不断发展普及,各种网络应用平台如雨后春笋般出现,人们已经生活在充满各种各样复杂网络的环境中。因此,社会网络分析已经成为各界学者关注的重要话题。而在复杂网络数据集上进行相关分析,并发现存在于网络数据中的关键性规律和信息,已经成为研究复杂网络的主要手段和目的。在复杂网络中,人相当于节点,人与人之间的联系相当于节点之间的边。人们通过大量研究发现,在复杂网络中都普遍存在社区结构。社区结构代表着具有相似属性或扮演相似角色的节点集合。通常情况下,社区内部的节点之间具有更加紧密的联系。通过对社区结构的研究,可以对复杂网络内部结构与属性进行深入的研究与探索,从而发现其隐含规律并对其行为进行预测。因此,对社区结构的发现与研究,已经成为计算机领域的重要研究课题之一。本文将对复杂网络,社区结构,社区发现算法,社会网络分析等话题进行分析与研究,主要包括以下几个方面的内容:(1)针对现有社区发现算法存在的低准确度问题,本文提出了一种基于中心节点的社区发现算法。通过各节点度数及节点间相似度寻找社区的中心节点,然后利用局部模块度对各个社区进行优化,并根据节点吸引力将孤立节点和重叠社区节点尽量归入其社区,最终获得整个复杂网络的社区结构。(2)针对基于中心节点的社区发现算法在进行社区划分时每个节点默认在复杂网络中担任相同角色,在模块度计算时权值相同,从而导致不同节点无法体现其自身在网络中所承担的角色与价值的问题。本文引入PageRank算法的基本思想,提出核心子团的概念。为了体现出不同节点在网络中所担任的不同角色,本文还提出加权局部社区贡献度的概念,并在此基础上提出一种基于核心子团的社区发现算法。在找到个社区中心节点的基础上,通过节点度等特征找到该社区的核心子团,然后利用加权局部模块度对各个社区进行优化,并对未被划分社区的特殊节点进行社区优化,从而获得整个网络的社区划分。(3)本文提出的两种算法在复杂网络应用中具有一定的优势,通过在复杂网络数据集上进行社区划分实验,并与相关社区发现算法进行准确度和运行时间对比。最终可以发现,本文中的社区发现算法具有一定的优越性。