论文总字数：29400字

摘 要

本文主要研究了经典社交网络结构模型生成算法的生成过程和结构及时间特性以及它们各自的缺点，然后提出了一种新的社交网络结构模型的生成算法，并用python制作了网络模型生成系统来展示这些算法所构造的模型及特性。主要的工作和成果如下：

1. 本文研究了经典社交网络结构模型生成算法（ER随机图，WS小世界网络，NW小世界网络，BA无标度网络，GN-Benchmark 算法，LFR-Benchmark 算法）的生成过程，并研究了社交网络模型所具有的时间复杂度、平均最短路径长度、聚类系数、节点度分布、模块度等方面的特性。
2. 本文用python设计了一个可视化的交互系统，用来自动生成经典社交网络结构模型，并展示出模型的结构信息。并设计了一个具有社区结构，符合小世界，无标度，幂律分布等特点的具有标签的无标度网络构造模型Scale-free Networks with Tag算法(TSF算法)，该模型允许用户自定义网络规模、社区规模、混合参数等基本网络参数，并结合LFR-Benchmark、GN-Benchmark对该模型做出评价。

通过本文的实验表明TSF算法在相同的环境中具有更好的聚类系数和模块度，尤其是当混合系数增大时，模型的性能仍然较高。本文还设计并实现了一个可视化的交互系统，结合本文提出的TSF模型和其他经典网络生成模型，用来自动生成经典社交网络结构模型，并展示出模型的结构信息。

关键词：复杂网络；无标度网络；社区结构； python可视化

Realization and Analysis of Visual Social Network Structure

ABSTRACT

This paper discusses the characteristics of structure and time and the shortcomings of classic social network generating algorithm, and then proposes a new generation algorithm of the social network structure model, and uses python to make a network model generation system to demonstrate the model and characteristics of the structure of these algorithms. The main work and achievements are as follows:

1.This paper uses python to design a visual interactive system, used to automatically generate the classic social network structure model, and show the structure of the model information. Based on these algorithms (ER, WS, NW, BA, GN, LFR) to generate the classic social network structure model, this paper shows the model in time complexity, average path length, clustering coefficient, degree distribution, the modularity of these five aspects of information.

2. This paper designs a network construction model TSF with community structure, small world, scale-free, power-law distribution and so on. The model allows users to customize the basic network parameters such as network size, community size and mixed parameters, and combine LFR -Benchmark, GN-Benchmark to evaluate the model.

We take some experiments with the typical algorithm such as LFR -Benchmark and GN-Benchmark to evaluate our model. It is demonstrated that our model performs better than LFR/GN-Benchmark, especially when the mixing coefficient getting larger. We designed a visual interactive system, using our model as well as some other typical models. We also develop the API, for other researchers testing their own model. The system can show the structure of the given model and compare the performance with other algorithms (ER, WS, NW, BA, GN, LFR) in the aspect of time complexity, average path length, clustering coefficient, degree distribution, the modularity and so on.

Keywords: complex network; scale-free network; community structure; python visualization

目 录

摘 要 1

ABSTRACT 2

第一章 绪论 1

1.1 研究背景和意义 1

1.1.1 选题背景 1

1.1.2 经典社交网络结构模型简介 1

1.1.3 python简介 3

1.2 研究内容 4

1.3 论文组织结构和思路 4

1.4本章小结 4

第二章 社交网络结构模型和基本特性 5

2.1 社交网络结构模型 5

2.1.1规则图 6

2.1.2 ER随机图 8

2.1.3 WS小世界模型 8

2.1.4 NW小世界模型 9

2.1.5 BA无标度网络 10

2.1.6 GN-Benchmark算法 11

2.1.7 LFR-Benchmark算法 12

2.2社交网络结构模型的性能指标 13

2.2.1平均最短路径长度 14

2.2.2聚类系数 14

2.2.3度与度分布 14

2.2.4模块度 15

2.2.5算法的复杂度 15

2.3本章小结 15

第三章 一种具有社区结构的无标度网络模型生成算法-TSF 16

3.1算法需求 16

3.2无标度网络模型生成算法TSF 16

3.2.1节点初始化 16

3.2.2社区内部连边 18

3.2.3社区间连边 19

3.3本章小结 20

第四章TSF 生成图算法的社区结构和时间特性比较 21

4.1生成图算法的社区结构特性比较 21

4.2实验结果与分析 22

4.2.1 TSF算法的时间特性比较 22

4.2.2混合参数改变时算法性能比较 24

4.2.3网络规模增大时算法性能比较 25

4.3本章小结 26

第五章 社交网络结构模型生成系统 27

5.1系统框架 27

5.2功能模块 27

5.3详细设计 28

5.4结果展示 28

5.5本章小结 32

第六章 总结和展望 33

6.1研究成果总结 33

6.2研究成果局限性 33

6.3未来研究工作展望 33

致 谢 35

参考文献 36

绪论

社交网络结构的研究已经有几十年的历史了，相继提出了很多模型构建的算法，本章主要介绍了社交网络模型构造算法的研究背景和发展概况，并介绍了python的特点和本文的主要研究内容。

1.1 研究背景和意义

1.1.1 选题背景

人们使用各种网络来形容自然界中存在的数量极大的复杂关系。典型的网络是由许多代表真实系统中不同的个体的节点和连接这些节点的表示不同的节点间的关系的边组成的。例如，人类和别的动物的神经系统可以看作是网络，其中节点就是大量神经细胞，边就是这些细胞间连接的神经纤维；计算机网络也可以看作是网络，其中节点是自主工作的计算机，边是连接这些计算机的通信介质比如光缆、双绞线、同轴电缆等。复杂网络结构存在于我们生活中的很多方面，比如电力网络、交通网络、社会关系网络、等等。复杂网络结构小到细菌和蛋白质系统大到人类各种关系，这些都是网络结构。因此，生成经典社交网络结构模型对研究这些复杂网络影响深远。

1.1.2 经典社交网络结构模型简介

1960 年Erdös P.和Rényi A.提出了“ER 随机网络模型” [1][2]对社交网络结构进行模拟，节点间连边的概率是固定的，这样最终生成的网络模型的节点度是服从二项分布的。1998 年Watts D. J.和Strogatz S. H.给出了“WS 小世界模型”的构建方法[3][4][5]，该方法基于规则图，把规则图中的每条边按照一定的概率重新连接，生成的社交网络结构模型的节点度分布服从泊松分布。1999 年Newman M. E. J.和Watts D. J.对WS 模型进行改进，提出了“NW 小世界模型”[6][7]，他们没有使用“随机化重连”而是在规则图的两点间按照一定的概率加边，克服了WS 模型中无法确保得到连通随机网络的局限性，并模拟了美国西部的电力网络、电影演员的协作网络和蠕虫的神经网络等。为了体现真实复杂网络的无标度特性，2001 年Barabási A. L.和Albert R.将社交网络结构的无标度特性归结为两个方面：增长机制和优先连接机制（如万维网、金融网络和美国飞机航班网络等），提出了“BA无标度模型”[8][9][10]，这种模型的节点度服从幂律分布。然而BA 无标度模型不能反映出现实生活网络中节点多种多样的连接情况，并且生成的网络模型的幂指数固定为3。

2002 年Newman M. E. J.等人提出了GN-Benchmark 算法[11]，构造了具有明显社交网络结构的正则网络模型，将128 个节点平均分到4 个社区中，其所有节点度数均为16，且各节点社区内部边和社区间连边比例相同。GN- Benchmark 算法构造的正则网络目前已被广泛的用于图聚类算法评测中[12]。

剩余内容已隐藏，请支付后下载全文，论文总字数：29400字