大规模动态社会网络社区结构挖掘与分析方法

发布时间：2020-07-19 00:37

【摘要】： 现实世界中的许多系统都以复杂网络的形式存在,网络簇结构是复杂网络最普遍和最重要的拓扑属性之一,具有同簇节点相互连接紧密、异簇节点相互连接稀疏的特点。复杂网络聚类方法旨在挖掘出复杂网络中客观存在的网络簇结构,对于分析复杂网络的拓扑结构、理解其隐含模式、预测其行为都具有十分重要的理论意义,在社会网、生物网和万维网中具有广泛的应用。 本文对复杂网络聚类方法的相关背景和理论进行了研究;在此基础上,以Enron邮件数据集为例,从动态数据集构建复杂网络;对目前具有代表性的一些算法从算法原理上进行剖析,并通过实验对典型算法从聚类精度和运行速度上进行定量比较;针对大规模动态复杂网络,设计了一种简单、快速挖掘复杂网络中局部簇结构的复杂网络聚类方法,该方法基于本文所提出的网络簇增长模型,是一种启发式的复杂网络聚类方法,能够在不了解整个网络结构的前提下,从网络的局部信息出发,在近乎线性时间内挖掘出一个局部网络簇结构,通过对比实验的测试,算法在随机网络中的聚类精度与CPM算法和FN算法相当,且能够在大规模网络中快速查找出一个局部网络簇结构;最后本文简要介绍了动态网络的分析方法。
【学位授予单位】：吉林大学
【学位级别】：硕士
【学位授予年份】：2009
【分类号】：N941.4
【图文】：

如社会系统中的人际关系网，科学家协作网和流行病传播网，生态系统中的神经元网、基因调控网和蛋白质交互网，科技系统中的电话网、因特网和万维网(图1.1)以及语言中的语义词汇网等。由于这些网络具有很高的复杂性，因此被称为“复杂网络(complexnetwork)”。复杂网络已成为当前最重要的多学科交叉研究领域之一[1][3][4]。与小世界性[1]、无标度性[3][4][5]等基本统计特性相并列，网络社区结构(network cluster structure或network community structure，以下称网络簇结构)是复杂网络最普遍和最重要的拓扑结构属性之一，具有同簇节点相互连接密集、异簇节点相互连接稀疏的特点[6][7][8][9][10]。网络社区结构挖掘方法(以下称为复杂网络聚类方法，complex network clusteringalgorithms)旨在揭示出复杂网络中真实存在的网络簇结构。图1.1 现实世界中的复杂网络－万维网复杂网络的簇结构的研究已经具有很长的历史，它与计算机科学中的图形分割(Graph Partition)和社会科学中的分级聚类(Hierarchical Clustering)有着密切的关系[11][12][13]。图形分割的一个实际例子是并行计算[11]。假设有n个相互通信的计算机程序分布到g个处理器上运行，每个程序不一定与其他的所有程序直接通信。所有程序之间的通信模式可以用一张图或网络来表示。图1.2中的一个节点表示一个程序

假设有n个相互通信的计算机程序分布到g个处理器上运行，每个程序不一定与其他的所有程序直接通信。所有程序之间的通信模式可以用一张图或网络来表示。图1.2中的一个节点表示一个程序，每条1

图 1.2 一个具有簇结构的网络示意图络来自社会网络分析的一个经典问题[11]。20世纪70年代间来观察美国一所大学中的空手道俱乐部成员间的相互社乐部内部及外部的社会关系，他构造了俱乐部成员之间有凑巧，在对俱乐部的观察过程中，该俱乐部的主管与收费的问题产生了争执。结果，该俱乐部分裂成了两个分俱乐部。图1.3中的节点1和节点33分别代表了俱乐部的主节点分别代表了分裂后的小俱乐部中的各个成员。在复杂chary网络的分析已经成为一个经典的例子，本文提到的很都用到了这个例子。

【相似文献】

相关期刊论文 前10条

1 赵正龙;陈忠;孙武军;庞清武;;邻居效应下的复杂社会网络扩散[J];系统管理学报;2008年05期

2 ;[J];;年期

3 ;[J];;年期

4 ;[J];;年期

5 ;[J];;年期

6 ;[J];;年期

7 ;[J];;年期

8 ;[J];;年期

9 ;[J];;年期

10 ;[J];;年期

相关博士学位论文 前2条

1 杨波;复杂社会网络的结构测度与模型研究[D];上海交通大学;2007年

2 赵正龙;基于复杂社会网络的创新扩散模型研究[D];上海交通大学;2008年

相关硕士学位论文 前3条

1 马海宾;大规模动态社会网络社区结构挖掘与分析方法[D];吉林大学;2009年

2 吴婷婷;局部网络外部性探讨[D];厦门大学;2009年

3 吴婷婷;局部性网络效应探讨[D];厦门大学;2009年

本文编号：2761632