论文部分内容阅读
社交网络分析是以社交网络为主要研究对象进行的一系列数据挖掘技术的总称。它能够从各个方面研究社交网络的拓扑特性,达到对拓扑信息的挖掘分析。社区发现是社交网络分析中的基础性与关键性技术,它通过研究拓扑结构中节点的疏密连接,将连接紧密的节点归入相同社区,将连接稀疏的节点归入不同社区。社区发现技术可以挖掘节点之间隐藏的拓扑特性,更好地挖掘局域拓扑信息。当前社交网络不断发展,以社区发现技术为代表的社交网络分析技术也得到了快速发展,并且在各个领域都有了广泛应用。随着随着社交网络的发展,其自身的数据规模也急剧增大,这要求社区发现算法需要兼具高精度与高可扩展性。与此同时,社交网络的数据结构也越来越复杂,出现了带节点属性的属性图结构,这要求社区发现算法需要能够兼顾节点属性与拓扑结构。而无论是传统的纯拓扑社区发现算法还是属性图算法,其在精度质量、稳定性、可扩展性上都有一定局限性,所以提出一个能兼具高精度与高可扩展性、支持属性图结构的社区发现算法,就显得尤为关键。近年来基于动态距离的社区发现算法,因为其高精度、高可扩展性,逐渐受到人们关注。但该算法的参数取值过于抽象,盲目选取的参数值极容易引发超大社区与碎片化社区两个质量问题;即使有合适参数值,由于算法机制的原因,结果中仍然会遗留一部分碎片化社区。这两个问题都极大地影响了算法精度质量的发挥。此外,该算法仅为纯拓扑算法,不支持属性图数据,这也进一步限制了算法的精度效果与应用领域。针对原算法参数抽象及其引发的超大社区与碎片化社区的问题,本文提出的新算法中增加了参数调节机制。本文从参数对结果的影响效果入手,研究分析了结果质量并定义了相关的指标与约束条件。本文基于参数取值与算法结果之间的关系,通过考察当前结果对质量约束的满足情况,推测当前参数的取值,进行相应的参数更新,同时更新参数的搜索范围进行剪枝加速。本文还针对少量顽固的碎片化社区,还提出了碎片消除机制。它基于标签传播的原理,将碎片点就近合并进临近社区,同时保持算法的可扩展性。本文将参数调节机制与碎片消除机制结合,增加一个用户可选的、直观具体的参数来指定预期社区数目,通过失效机制来避免其盲目取值对结果的不良影响,最终得到了算法在纯拓扑上的改进算法。实验证明,纯拓扑上的改进算法能够有效解决相关质量问题,显著提升结果质量。此外,针对算法仅仅局限于纯拓扑领域、无法挖掘属性信息的问题,本文提出了属性图上的扩展算法。该算法对原有算法内核进行重定义。本文借助信息转化,基于属性图构建出了新的异构图结构,并在相互作用原理的基础上分析规范了异构图中节点的行为模式,对节点之间的相互作用进行重定义,使得算法能够同时利用拓扑与属性,并通过二者的相互作用实现动态平衡。实验证明,算法在属性图上的扩展能够显著提高其在属性图上的精度(提升幅度从3.2%至46.3%不等),且能够增强算法面对复杂变化拓扑时的精度稳定性。本文同时将两个算法进行结合,得到了复合功能的算法,该算法具备了所有新增的功能。数据实验表明,算法在属性图上相较于其他经典属性图算法,其精度效果有了较大提升;同时该算法保持了原算法的高可扩展性,在处理大规模与超大规模社交网络时有着很大的优势。