基于动态规划的大规模网络在线聚类研究

发布时间：2020-08-02 10:16

【摘要】：很多复杂系统都可以抽象成复杂网络或者图来进行研究,同时,复杂网络科学的发展也极大地促进了人们对复杂系统的理解。在对复杂网络研究过程中,相继有很多重要特性被发现,比如自相似、吸引子、小世界、无标度和社团结构等。其中,社团结构是复杂网络中最重要的特性之一,对研究复杂网络的结构和功能有着举足轻重的作用,在社会学、物理学、生物学和计算机科学等很多领域均具有非常重要的意义。网络聚类就是检测复杂网络中的社团结构,这些社团结构具有内部连接紧密社团之间连接稀疏的特点。随着人们对社团结构持续不断的深入研究,已经涌现出大量优秀的图聚类算法。目前,在快速发展的社交网络和大数据的推动下,网络规模也不断增长,很多网络的规模甚至包含数百万个结点和数十亿条边。如何解决大规模网络聚类已成为该领域内的研究难点。基于此,本文首先简要介绍图聚类的研究背景及意义,并概述该领域重要的研究进展。接着对复杂网络的定义和特性、社团结构的定义以及图聚类的评价指标等相关基础知识作了简单介绍。然后,从优化一般图聚类算法出发,结合最近提出的基于快速发现和搜索密度峰值聚类算法和复杂网络无标度特性,提出基于中心结点快速检测的图聚类算法(CFCN),该算法通过快速搜索和检测聚类中心来实现网络的快速聚类。另一方面,为了改善一般聚类算法可扩展性以适应大规模网络聚类,同时满足实时性需求,本文提出了基于动态规划的大规模网络在线聚类框架(DPOCG),该框架通过构造超级结点和移除边缘结点大大减小了时变网络规模,从而使一般的图聚类算法得以适用。本文的主要研究工作如下:(1)提出了一种基于中心结点快速检测的图聚类算法。该算法首先计算每个结点的局部密度ρ和综合距离β,接着通过由ρ和β画出的决策图来快速确定检测聚类中心的局部密度阈值thrho和综合距离阈值thbeta,并检测出聚类中心,最后将非聚类中心结点分配到与其关系最紧密的聚类中心所在聚类以实现整个网络聚类。我们在真实世界网络上的实验结果表明,基于中心结点快速检测的图聚类算法的聚类效果明显优于对比算法。(2)提出一种基于动态规划的大规模网络在线聚类框架。该框架基于动态规划的思想并结合网络演变的特点,将大规模网络按一定时间段分成若干阶段的子网络。接着通过两种方式来减小每一阶段子网络的规模,分别是根据相邻阶段聚类内部结点状态变化情况对聚类内部状态未改变结点构造超级结点和移除网络边缘结点。最后应用一般图聚类算法?在缩减规模后的网络上进行聚类,并对移除结点按最近邻策略快速聚类,最终实现整个网络聚类。快速高效的DPOCG框架很好的解决了大规模网络聚类,并改善了一般聚类算法的可扩展性,同时满足了实时性要求。通过在合成的BA网络和真实世界网络上实验,结果表明了DPOCG框架的有效性,且聚类效果明显优于其它几种对比的大规模网络聚类算法。
【学位授予单位】：西南大学
【学位级别】：硕士
【学位授予年份】：2018
【分类号】：O157.5
【图文】：

科学家,规则网络,图论,网通

计算机科学等，复杂系统都可以抽象成网络来研究，如新陈代谢网[1]、蛋白质相互作用网[2]、科学家合作网（图1-1）、公路网、航空网[3]、万维网[4]等。复杂网络[5]在数学上又可以抽象为图，通过应用图论的有关概念，能够对复杂网络中个体之间的相互作用进行深刻的描述，其中，网络中的个体可以看作图中的结点，个体之间的相互作用可以由图中边表示。对于图论的研究，最早可以追溯到 1736 年欧拉解决哥尼斯堡七桥问题，从此人们开始了解更多关于图及其数学特性[6]。到了二十世纪，图在表示各种不同领域的系统方面变得非常有用，像生物，社会，技术和信息等方面的网络都可以作为图来研究，而且图分析对于理解这些系统的特征已经变得至关重要。比如始于 20世纪 30 年代的社会网络分析，已经成为社会学中最重要的话题之一[7]。近年来，计算机革命为学者提供了大量的数据和计算资源来处理和分析这些网络数据，进而人们能处理的真实网络的规模也大大增加，达到数百万乃至数十亿的结点。处理如此大量数据的需求已经对图处理方式产生了深刻的变化。图 1-1 科学家合作网通过对图论的进一步研究，早期科学家建立了完全规则网络[8]和完全随机网络理论[9]。其中，规则图中每个结点都有相同的邻居数，也就是每个结点的度都相等。

规则网络,随机网络,聚类系数,结点

西南大学硕士学位论文度和聚类系数这两个概念，下面将给出定义。网络的平均路径长度可以用来描述网络的随机性，它的定义如下：L ￠（￠ )∑ ≠ （2-2）其中，n 为网络中结点数，为从结点 i 到结点 j 的最短路径，平均路径长度 L 则表示网络中任意两个结点最短路径和的平均值。聚类系数则用来描述网络中结点群聚性或者聚集的紧密程度。网络的聚集系数是所有结点的聚类系数均值，网络中结点 v 的聚类系数定义如下： ( )（2-3）网络的聚类系数为：C ∑ （2-4）其中，m 表示结点 v 的个邻居结点之间的边数。Regular Small-world Random

泊松分布,泊松分布,幂律分布

第 2 章预备知识及基础理论分布[58]（如图 2-2）。但是科学家们通过研究发现，现实世界的大部分网随机网络，它们的结点度分布服从幂律分布[59]（如图 2-3），即有：P( ) （2 P(k)表示网络中结点度为 k 的概率，γ 是一个常数通常在 1 到 3 之间。如结点的度分布服从幂律分布，我们可以将这种特性称为无标度特性，具性的网络则称为无标度网络。

【参考文献】