摘 要

复杂网络的身影在各种网络系统中都可以见到，例如科研合作网络、交通网络等，这使得研究复杂网络成为必要。本文从复杂网络的中尺度结构出发，着重研究了复杂网络的社团结构、核心-外围结构的相关知识和复杂网络的基本属性与分析方法。目前社区检测已经从不同的角度进行了广泛的研究，因此本文研究了几种经典的算法并作网络模型应用。核心-外围结构在社会网络、国际贸易和其他领域中均已被发现，但其定义和检测还没有得到应有的重视。因此本文着重研究了检测复杂网络多核心-外围结构的算法，并作网络模型应用。

同时，机器学习方法成为现今学者们的研究热点，并开始用于复杂网络的网络结构分析。虽然相关工作仍然非常少，但针对复杂网络的多核心外围结构探测的分析与设计，机器学习有望提供一个更准确且更新颖的方法。本文采用简单、快捷、高效的聚类算法对复杂网络结构做了分析，研究了K-means算法的原理和具体的执行步骤。在此基础上，研究了一种基于信息中心度的概念，以节点关联矩阵为途径选择聚类中心并进行节点聚类，将复杂网络结构划分为k个社区，然后通过模块传递，确定理想的网络社区结构。

关键词：复杂网络，社团结构，核心-外围结构，机器学习

ABSTRACT

Nowadays, people live in a world full of all kinds of complex networks. From research cooperation networks to various political, economic, and social networks, from large power networks to transportation networks, complex networks are everywhere, making it necessary to study complex networks. Starting from the mesoscale structure of complex networks, this paper focuses on the community structure and core-peripheral structure of complex networks, and introduces the basic attributes and analysis methods of complex networks. At present, community testing has been extensively studied from different angles. Therefore, this paper studies the classical algorithm, and applies it to a simple karate club network, and analyzes the algorithm detection results. The core-edge structure has been discovered in social networks, international trade and other fields, but its definition and testing have not received the attention it deserves. Therefore, this paper focuses on the algorithm for detecting multi-core-peripheral structure of complex networks, and uses it as a network model.

At the same time, the machine learning method has become a research hotspot for scholars this year, and has begun to be used for network structure analysis of complex networks. Although the related work is still very small, machine learning is expected to provide a more accurate and innovative approach to the analysis and design of multi-core peripheral structure detection for complex networks. In this paper, the K-means algorithm based on simple, fast and efficient clustering algorithm is used to study the principle and specific execution steps of K-means algorithm. In addition, an algorithm is introduced in detail. Based on the information center degree proposed by Fortunato et al., the association degree of nodes is defined. Cluster node selection and node clustering are performed through node association matrix, and the complex network is divided into k communities. Passed through the module. Determine the ideal network community structure.

Keywords: complex network, community structure, core-peripheral structure, machine learning

目录

第1章 绪论 1

1.1 研究背景与意义 1

1.2 国内外研究现状 2

1.3 本文研究的主要内容 2

1.4 本文的结构安排 3

第2章 复杂网络结构概述 4

2.1复杂网络结构简介 4

2.2社团结构的定义 4

2.2.1经典的网络模型 5

2.3核心-外围结构分析 7

2.4本章小结 8

第3章 复杂网络结构识别算法 9

3.1社团结构的识别别算法 9

3.1.1 Kerninghan-Lin算法 9

3.1.2基于Laplace矩阵的谱平分法 11

3.1.3分裂算法 12

3.1.4凝聚算法 13

3.2 复杂网络多核心-外围结构的识别算法 14

3.2.1一种检测网络核心-外围结构和社区结构的统一方法 14

3.2.2一种可扩展的用来检测网络中多个非重叠核心-外围对的算法 16

3.3本章小结 17

第4章 聚类算法在复杂网络核心-外围结构探测上的应用 18

4.1 k-means算法 18

4.2基于K-means聚类算法的复杂网络核心-外围结构发现新方法 18

4.3本章小结 20

第5章 总结与展望 21

5.1 全文总结 21

5.2 工作展望 21

致谢 22

参考文献 23

附录A空手道俱乐部网络模型算法 24

附录B 社团结构划分算法 25

附录C 一种检测网络核心-外围结构和社区结构的统一方法 28

第1章 绪论

• 1. 研究背景与意义

复杂网络的研究起始于上世纪90年代，伴随着互联网的迅速普及而获得了高速发展的机遇。社交网络和生物网络等网络系统的实证研究不断地启发着研究人员开发各种技术和模型去理解或预测这些系统的行为。通过近三十年的研究，研究者们已经发现了复杂网络的诸多特性，包括小世界效应，去分布，聚类，网络相关性，随机图模型，网络增长和优先附着模型以及网络上发生的动态过程等概念^[1]。复杂网络是利用网络节点来将现实世界中种类繁多的复杂系统进行抽象表示，例如生物网络、社交网络、合著网络等。复杂网络中节点可以代表某些独立存在的个体也可以代表一些基本单位，边则表示这些独立的个体或单位之间的联系。人类社会中的诸多实际问题都可以通过将个体对象抽象为网络节点，再将网络节点进行建模形成复杂系统，进而完成网络处理与数据分析。利用网络模型进行数据处理的分析方法已经被广泛地应用于描述现实世界中各实体对象之间的联系以及影响。

通过对大量的网络数据的研究发现，复杂网络在小世界、无标度等基本特征之外，大量的网络系统体现出中尺度结构这个相同的性质，但是令人遗憾的是，目前学术界对这种类型的网络系统的研究仅仅局限在其中之一的社团结构上，并且已经开发了各种技术来检测社团结构,基于标签传播，链路划分，clique渗流理论，多目标进化算法等多种重叠社区检测算法[2]。然而还没有将足够的精力转移到核心-外围结构这另一种广泛存在的中尺度结构上，这种网络结构已经在社会网络，科学等诸多的系统中被检验到。目前大量的研究结果表明，网络的核心-外围结构在核心节点与外围节点的联系上，优于社团结构的连接。网络核心边缘结构可能具有不同的表现形式，也可能存在多重核心的现象，这些现象普遍存在于各类实际网络中。

探测复杂网络的多核心外围结构具有重要的实际意义。多核心-外围结构在反映网络特点方面优于社团结构，但社团结构的研究方法与成果对核心-外围结构识别算法的研究具有重要的借鉴意义。将其识别算法应用于现实世界的复杂系统的处理与分析将带来更大的收益。本文详细分析了研究复杂网络的多核心外围结构的实际意义，并且总结了国内外研究学者的相关成就，本文主要是在这些研究的基础上，对复杂网络模型的多核心-外围结构进行建模以及仿真设计。近年，一个令科研学者们振奋的研究方向蓬勃发展-机器学习，并开始用于复杂网络的结构分析。在研究工作有章可循的基础上，本文将以机器学习为切入点，对复杂网络的多核心外围结构进行分析与设计，尝试利用机器学中聚类算法对网络结构进行分析与检测，并与传统识别算法进行对比，分析和总结优劣。

• 1. 国内外研究现状

Euler对Konigsberg七桥问题的抽象和论证思想，使复杂网络首次进入人们的视野^[3]。在之后的学者们不断地探索与研究中，真正奠定了其理论基础的研究是“随机图理论”的提出与完善。在二十一世纪，复杂网络已然成为一个重要的研究领域，来自全世界各地的科学家们越来越多的将关注的目标锁定在此学科，并投身其中不断拓展和深挖，使得新方法不断涌现。

在复杂网络研究的初始阶段中，Borgatti和Everett提出了一个与具有理想化核心-外围结构的网络比较的研究方法，并将其应用于衡量实验结果,在他们的研究之后，许多核心外围检测算法得到了迅速发展^[4]。Morbach等人对网络核心外围结构的属性进行了研究，Rombach等人创新了更为灵活的模型但遵循了相同的思路与原理。Michael等提出了一种基于3元图案的检测核心外围结构的方法，Mason A等研究了基于密度和基于传输的核心外围模型，Jaewon等研究了如何利用重叠社区解释核心外围结构。通过科学家们持之以恒的进行一系列的探索，人们对现实生活中的各类复杂系统之间的内在联系及其组织结构和基本特性有了更加精准的认识。

国内复杂网络的研究起步于二十一世纪初，期间涌现出了许多优秀的研究学者和科研成果。譬如，上海交通大学的汪小帆研究小组在复杂网络领域的研究中做出了突出贡献，引领了国内复杂网络研究的发展。国内外对于复杂网络的网络模型已经有一定的研究，并且在不断地深化和提高之中，张其林等提出了一种具有无标度特性的核心外围结构网络演化模型用于分析复杂网络结构，马小科等将复杂网络社团模型和算法应用于生物网络中并取得了成效。岳清唐等利用核心-外围结构分析了我国的贸易结构、经济结构和条件，并得出了具有重要价值的结论。随着国内复杂网络领域的蓬勃发展和科研成果的不断涌现，已经有越来越多的有志之士投身于此，相信在不远的未来，科研学者们将摘得复杂网络领域的明珠。

• 1. 本文研究的主要内容

在本文研究的主要内容如下：

1. 介绍了复杂网络的基本属性和网络模型机制，这些基本属性和网络模型是我们研究复杂网络的前提。由于复杂网络的社团结构已经被广泛研究，核心-外围结构研究相对较少，二者的联系也较为紧密，研究社团结构对核心-外围结构是有重要参考价值的。故本文详细介绍了社团结构的性质和识别算法。在熟悉了解社团结构的基础上，引出了核心-外围结构，并介绍了相关算法。
2. 在充分了解复杂网络结构的基础上，本文研究了采用机器学习的新方法来研究复杂网络的结构问题。研究了聚类算法中的K-means算法，了解了其检测原理与检测步骤，并研究了一个于K-means聚类算法发现复杂网络结构的新方法。
   1. 本文的结构安排

本文一共分为五章。

第一章为绪论，总体把握了论文的走向，详细陈述了研究背景、国内外研究问题的现状和主要研究的内容。

第二章介绍了复杂网络结构的基本属性，从复杂网络的基本属性出发，详细介绍复杂网络的社团结构及其分析方法，而后研究了核心-外围结构的基本属性，阐述了二者的区别与联系。

第三章介绍了4种经典的发现复杂网络社团结构的算法，介绍了算法的基本思想和执行步骤，同时也对算法的优缺点进行了比较分析。 之后研究了复杂网络的另一种典型结构，即核心-外围结构。研究了两种识别核心-外围结构的算法，介绍了其基本原理与优势。

第四章引入机器学习中无监督学习的聚类方法,简单介绍聚类的目的、意义以及目前常用的几种聚类方法。研究了一种基于K-means聚类算法的复杂网络多核心-外围结构发现新方法。该方法的原理是基于Fortunato等人提出的边缘信息中心度理念。第一步是定义节点的关联度；然后选择聚类中心和节点分组由关联度矩阵执行，通过这个步骤，复杂网络将被划分为K个社团，最后使用模块度来获取理想的社区结构。

第五章概述了本文所做的研究，旨在跟进工作，分析研究的不足和后续研究方向。

第2章 复杂网络结构概述

2.1复杂网络结构简介

许多复杂的系统，无论是生物的，物理的还是社会的，都可以用网络来代表。网络由一组节点和边缘组成，其中节点表示对象（例如，人，网页），边缘表示对象之间的成对关系（例如，友谊，超链接）^[5]。通过对大量的复杂网络进行研究，学者们发现其通常是由互相紧密连接的节点组构成，又被称之为社区。社区通常与一组共享角色或相似性的节点相关联，例如朋友圈子社交网络，一组讨论相同主题的网页和蛋白质的功能组。核心-边缘结构是网络的另一个细观结构，在过去二十年中经历了兴趣的激增。最简单形式的核心-外围结构是指网络划分为两组节点，称为核心和外围,其中核心节点密集互连（即相邻），外围节点与核心节点相邻但不与其他节点相邻^[6]。核心-外围结构已经在许多网络中被检测到，研究复杂网络的结构对于研究现实中各种网络的联系及影响，进而提出建议有重要意义。复杂网络结构中的社团结构已经被广泛研究，核心外围结构虽然已经被广泛发现，但研究比较少，二者既有区别又有联系。因此研究社团结构的基本属性，经典结构，识别算法等对核心-外围结构有重要的参考意义。

2.2社团结构的定义

目前，有多种关于网络社团结构的定义，但至今还没有哪种定义能够得到广泛认可。学术界普遍认可的、最为常见的定义有两种：第一种是基于网络节点的相对连接密度；另种是以网络的连通性为评价标准。

Radicchi等研究学者以节点之间连接密度的比较为切入点，将复杂网络社团结构划分为强社团结构和弱社团结构。如果一个子图中任意一个节点与其内部节点之间的连接度大于其与外部节点的连接度，那么此网络结构就成为强社团结构;而弱社团结构却不是与强社团结构定义相反，实际上弱社团结构指的是子图中所有节点与社团内部节点的度之和要大于其所有节点与社团外部节点连接的度之和^[7]。

Palla等给出了以连通性为标准定义的社团结构，也称作派系。如果一个子图有3个或者3个以上的节点组成，任何两个节点之间均有连接的全连通子图，那么此结构就称为派系^[8]。

2.2.1经典的网络模型

二十世纪七十年代，Zachary网络模型被提出，这是Zachary花费了大约24个月的时间观察美国某大学中空手道俱乐部成员之间的关系所得到的。它是一个实用的测试不同算法划分效果的网络模型。在调查过程中，由于俱乐部的主管和校长之间发生矛盾，纠纷的关键点在于是否增加俱乐部的费用，俱乐部分为分别以校长和主管为核心的两个小俱乐部。

我们将俱乐部的三十四名成员抽象为三十四个节点以此生成网络模型，其中校长由节点三十三代表，主管由节点一代表。圆形的节点代表分裂后拥护校长的成员，方形节点代表分裂后拥护主管的成员。

支持俱乐部主管一方分别为节点：

1,2,3,4,5,6,7,8,11,12,13,14,17,18,20,22。

支持校长一方节点为：

9,10,15,16,19,21,23,24,25,26,27,28,29,30,31,32,33,34。

图2.1 空手道俱乐部网络

由图2.1可以很明显的观察到，34个节点被划分为两个社团，其中16个节点以节点1为核心，18个节点以节点33为核心，这与实际网络是一致的，说明我们建立的空手道俱乐部模型是有效的。

空手道俱乐部网络模型的数据集如表2-1所示：

表2-1 空手道俱乐部网络模型数据集

2.3核心-外围结构分析

核心-外围结构是网络的另一个细观结构，在过去二十年中经历了兴趣的激增。最简单形式的核心-外围结构是指网络划分为两组节点，称为核心和外围，其中核心节点密集互连（即相邻），外围节点与核心节点相邻但不与其他节点相邻。核心-外围结构已经在社交网络、神经网络、贸易网络和交通网络等诸多网络中被检测到。例如，在国家间的世界贸易网络中，经济强国与其他强国进行贸易，构成核心,经济上较弱的国家主要与强国进行贸易，构成边缘^[9]。

以上是毕业论文大纲或资料介绍，该课题完整毕业论文、开题报告、任务书、程序设计、图纸设计等资料请添加微信获取，微信号：bysjorg。

相关图片展示：