论文部分内容阅读
社会关系广泛存在于现实生活中,它们可以抽象成各式各样的社会网络。近些年来,研究者们发现社会网络中存在的社团结构是大规模网络分析和挖掘的基础,对于分析社会系统的组织原则与动力学特征以及预测系统中实体的行为具有重要的研究意义,在社会学、生物学和商业活动中具有广泛的应用前景。网络中社团结构的研究已成为一个具有重要社会价值及应用价值的课题。如何更快更好地发现社团结构或者是发现更真实的社团结构是网络社团研究中的关键问题。本文首先研究如何寻求降低社团发现算法的时间复杂度和提高社团发现的精确度间的平衡关系,然后给出精确地发现网络中实际的社团结构的新思路。作者对上述问题进行相应研究,将层次粒化方法引入社团划分方法中来,提出基于邻接粒化的社团发现算法(AGCDA)和基于相容粒化的社团发现算法(TGCDA)。本文的主要工作如下：1)首先对社团发现算法的研究现状进行详细地调研,并分析部分经典算法的优势和不足,同时将层次粒化方法引入本文中来更快更好地发现社团结构或者是发现更真实的社团结构。2)为了获取社会网络社团发现算法的复杂度和精确度间的均衡,将层次粒化的方法引入社团发现,本文提出基于邻接粒化的社团发现算法(AGCDA)。该算法初始时根据网络中节点间的邻接关系对网络进行初始粒化,然后不断地对网络进行层次粒化,直到不满足粒化条件为止,最后在该粒度下求解非重叠社团结构。该算法有效地解决时间复杂度和精确度难以平衡的问题。实验部分在基准网络和应用网络上进行测试,并与经典的社团发现算法进行比较。基准数据集上的实验结果表明了该算法可获得高于LPA算法7.6%的模块度和低于NFA算法96%的时间。因此,AGCDA算法的时间复杂度较低,获取的社团模块度较高,实现了社团发现时间和精确度的均衡,总体性能更优。3)为了更加准确地发现社会网络中真实的社团结构,本文提出基于相容粒化的社团发现算法(TGCDA)。该算法初始时根据网络中节点间的相容关系对网络进行初始粒化,然后不断地对网络进行层次粒化,直到网络中的所有节点包含在一个粒子中为止,最后在具有最大相容粒化标准的粒度下求解非重叠社团结构。该算法初始粒化网络时形成若干个极大相容粒子,其保证具有高连接密度的社团至少要包含一个极大相容粒子,因而可以更准确地发现接近于网络中真实存在的社团结构。实验部分在人工数据集和基准数据集上测试TGCDA算法的有效性,在基准数据集上,TGCDA算法可以获得高于NFA算法17.55%的NMI精确度,同样在人工数据集上也有所提高。因此对于具有真实社团结构的网络,TGCDA算法可以更加准确地发现网络中的社团结构。