导　　师： 毛睿;李荣华

授予学位： 硕士

作　　者： (）;

机构地区： 深圳大学

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

关 键 词： 社交网络 动态更新 聚类算法 广度优先树 负载均衡

领　　域： []