基于图结构聚类的社区搜索算法的研究

发布时间：2020-05-20 11:51

【摘要】：近年来,随着信息技术的快速发展,各个行业都形成了自身的海量数据,在电信行业形成的海量通话数据、生物化学中分子之间的关系数据、交通网路的架构信息以及社交网络中形成的数据信息。如何充分的挖掘这些数据的潜在价值是目前学术界和工业界探讨的热点问题。对于这些数据形成的巨大的复杂网络系统,可以用图结构清晰地表示,而对图中的数据进行聚类操作是挖掘图数据信息的一个基本工具。然而,现实中的数据总是在不断地动态更新,传统的基于图结构的聚类算法SCAN(A Structural Clustering Algorithm for Networks)并不能有效地处理和维护实时更新的数据信息。因此本文提出了一种基于广度优先树BFS-tree(Breadth First Search-tree)的增量图结构聚类算法ISCAN(Incremental Structural Clustering for Dynamic Networks)。当数据更新时,利用该算法无需重新计算整个图,只需更新少量的边,通过广度优先树的断裂以及合并来维护已有的聚类结果。此外,为了减少在计算图中顶点之间相似性所消耗的时间,本文提出了如何利用多核进行结构相似性的计算,并且提出了两种有效的负载均衡策略。传统的结构聚类算法,对给定的阈值参数非常的敏感,细微的变化都会对聚类结果产生较大的影响,本文提出了一种基于三角形的结构聚类模型,相对于传统的结构聚类算法,不仅能够降低聚类结果对参数的敏感性,而且能够得到更加紧密的社区。最后,以现实世界中形成的量图数据为依据做了大量的对比试验。实验结果证明了提出的增量图结构聚类算法和并行计算结构相似性的有效性、正确性,以此同时,通过实验发现,我们提出的基于三角形的结构聚类,不仅能够得到更加紧密的社区,而且当阈值发生改变时,聚类的结构更加的稳定。
【图文】：

负载均衡,运行效率

22图 3.6 不同负载均衡策略的运行效率对比观察图 3.6，发现随着 CPU 核心数的线性升高，系统的运行时间几乎是线性降低的；，根据实验结果，，可以发现基于切片的负载均衡策略的运行效率普遍高于基于边度行效率。这是由于计算有边顶点之间的结构相似性的过程中，当且仅当在完全理想下时间复杂度是: d(u) d(v)，但是，由于硬件因素以及算法运行过程中的线程的同步问题，从而造成一些误差，使得程序不能达到完全理想的理论运行时间。但

变化参数,聚类,结构聚类,聚类模型

构聚类处理动态更新的数据。接下来，将在具体的实验结果中分析传统的结构聚类模型和本文提出的基于三角形的图结构聚类模型的效果，更具实验结果对数据集中的部分聚类结果进行对比分析。具体如下图所示。(a)SCAN( 2, 0 4) (b)TSCAN( 2, 0 4)
【学位授予单位】：深圳大学
【学位级别】：硕士
【学位授予年份】：2018
【分类号】：TP311.13

【参考文献】