论文部分内容阅读
从图数据中挖掘出互相连接紧密的社区结构是一项具有重大商业价值和社会效益的前沿技术。近年来,随着图数据规模的不断扩大,社区挖掘的复杂性越来越高,这就迫切需要提出一些面向海量图数据的社区挖掘算法加以支持。本论文深入分析了面向大规模图数据的社区挖掘技术所面临的挑战,提出了一种基于MapReduce结构聚类（Structural Clustering Algorithm for Networks）的社区挖掘算法MRSCAN以及一种基于k-core-truss的社区子图模型。具体地,本文的工作主要包括以下2部分内容:（1）提出基于MRSCAN的社区挖掘算法。SCAN是一种知名的基于密度的图聚类算法。不同于一般的聚类算法,该算法不仅能够很好地找到图中的聚类结构,而且还能发现图中的桥接节点和离群节点,在现实应用背景中有着重要的意义。然而,随着图数据规模越来越大,传统的SCAN算法(复杂度为O(m1.5),m为图中边的条数)很难处理大规模的图数据。例如,在具有超过数百万个节点和边的大规模图数据环境中使用传统SCAN算法进行处理基本不可行。为此,本文提出的第一个基于MapReduce的算法MRSCAN来解决SCAN算法的可扩展性问题。首先,MRSCAN分布式地计算图节点之间的结构相似性以及求出核心节点;然后,提出对核心节点维度扩展的概念,将图中的点是否为核心进行维度扩展,使得每个节点在合并聚类时能够被识别是否为核心节点;最后,提出两种分布式合并聚类的算法,通过观察提出一般的合并聚类算法,再利用最小化核心编号对其进行算法层面的优化。在多个真实的网络数据集上进行大规模测试,实验结果验证了MRSCAN算法的有效性和可扩展性。（2）提出了一种新的社区子图模型:k-core-truss。该模型能够很好地解决现有的k-core、k-truss模型所存在的缺陷。基于该模型,给定社交图数据中一个或多个查询用户,实现在大规模的社交数据中快速的查找出该查询用户所在社交圈子的算法,并进一步扩展到在社交图谱中查找代表紧密关系的凝聚子图。在多个真实的大规模图数据集上分别进行实验测试,实验结果验证了上述模型与算法的正确性、有效性与可扩展性。