摘 要

本文主要研究的是一种基于信息中心度的复杂网络社团结构识别的算法，通过具体的实际网络来验证该算法的准确性。研究社团结构对分析复杂网络有着极大的帮助，研究该算法，是为了更为方便的从各种复杂网络中，快速的识别出其中存在的各个社团结构，来更好的分析复杂网络的各个性质。在研究过程中，主要通过MATLAB编程软件来实现对该算法的程序编写要求，然后用海豚网络和空手道网络两个典型网络所编写的邻接矩阵来对该算法进行验证。

本文分为三大部分，第一部分是对复杂网络中社团结构的研究，通过简单的介绍复杂网络和社团结构引出社团结构的识别算法；第二部分是对这种信息中心度算法的基本介绍；第三部分是对该算法程序的MATLAB软件编写及仿真。通过最后的仿真结果可以看出该算法能够快速便捷的识别社团结构，对分析复杂网络性质有极大的帮助。

关键词：复杂网络；社团结构；信息中心度；模块度

Abstract

The main research of this paper is a kind of complex network community structure identification algorithm based on information center degree, and the accuracy of the algorithm is verified by the actual network. Study on community structure analysis of complex networks has a great help. To study the algorithm, in order to more convenient from a variety of complex network, the rapid recognition that the existence of the various community structure to better analysis of complex network properties. In the course of the study, mainly through software MATLAB programming to achieve the program of the algorithm written requirements, and written with dolphins and karate network two typical network adjacency matrix to the algorithm is validated.

This paper is divided into three parts. The first part is the study of community structure in complex networks. Through the simple introduction of complex networks, community structure and leads to community structure identification algorithm; the second part is a basic introduction to the information center of algorithm; the third part is on the program written in MATLAB software and simulation. Through the simulation results we can see that the algorithm can quickly and easily identify the community structure, which has a great help for the analysis of complex network properties.

Key Words: complex network; community; information centrality; modularity

目 录

第1章 绪论 1

1.1 目的及意义 1

1.1.1 研究背景及目的 1

1.1.2 国内外现状 1

1.2 研究内容及预期目标 2

1.2,1 研究内容 2

1.2.2 预期目标 2

第2章 复杂网络及社团结构 4

2.1 复杂网络基础 4

2.1.1 复杂网络图 4

2.1.2 最短路径长度及平均路径长度 4

2.1.3 聚类系数 4

2.1.4 度分布 5

2.2 社团结构 5

2.3 小结 6

第3章 基于信息中心度的社团结构识别算法 7

3.1 GN算法 7

3.2 基于信息中心度的社团结构识别算法 7

3.2.1 基本思想和方法 7

3.2.2 基本流程及特点 8

3.2.3 模块度 8

3.3 二种典型网络模型 9

3.3.1 海豚网络模型 9

3.3.2 空手道俱乐部网络模型 10

3.4 小结 11

第4章 MATLAB编程与算法实现 12

4.1 MATLAB编程 12

4.1.1 典型网络模型的程序编写 12

4.1.2 信息有效率的程序编写 13

4.1.3 信息中心度的程序编写 13

4.1.4 移除边的程序编写 13

4.1.5 模块度的程序编写 14

4.2 算法实现 14

4.3 小结 16

第5章 总结 17

参考文献 19

附录 20

致谢 34

1. 绪论

在社会，生物和技术系统中网络分析是一个用来理解复杂现象和组织的强大方法，而在许多网络中都有的共同特性是亚群或者社团结构的存在。社团结构是许多社会、生物、技术网络的重要特征。在这里，我们研究的是一种识别各种复杂网络中社团结构的算法，这个算法是由Fortunato提出的基于用信息中心度来界定社团边界的构想，用一种分层聚类的方法，不断地寻找和删除网络中信息中心度最高的边，来得到最后的社团结构。

1.1 目的及意义

1.1.1 研究背景及目的

近代以来，网络技术的日益发展使得人类社会进入了一个新的网络时代。而通过对这些复杂网络[1]的研究和了解，能够促进我们自身社会的发展和繁荣。长久以来，对于复杂网络，在数理学科、生命学科和工程学科等不同领域都有着广泛和深度的研究和应用，了解和认识复杂网络的一些基础特性，并通过这些特性来发展现有的科学进程，已成为网络研究中的一个重要的挑战性课题[2,3]。随着对复杂网络的物理结构和功能特征的深入研究，研究者们发现许多复杂网络都具有社团结构[4,5]的特征。在对复杂网络的研究中社团结构是复杂网络的一个关键结构规律，通过对复杂网络中各个社团结构的特性和规律研究，能够很快地了解这个复杂网络的一些特性和规律。因此准确分析复杂网络的社团结构是复杂网络研究中的一个非常重要的课题[6]。因此，如何快速准确的在复杂网络中，找到所需要的社团结构是我们所需要解决的问题。而这里所要研究的基于信息中心度[8,9]的方法就是一种从各类复杂网络中寻找到所需要的社团结构的一种分裂算法。

研究这种基于信息中心度的分裂算法，是为了在各种各样的复杂网络中，可以准确有效的找到其中的各个社团结构，特别是当这些社团是非常混杂并且几乎没有其他方法可以检测到的时候，这样可以为后续的研究结构以及分析网络性质做准备。