摘 要

本毕业设计的名称为“基于normal矩阵谱平分算法的网络社团结构识别设计”，对于复杂网络社团结构识别的研究越来越重要，是在当今科技飞速发展，全世界人类联系越来越紧密的大背景下，人们身处的环境越来越多样化。其实人们每时每刻都处在复杂网络的世界中，比如新陈代谢网络、世界贸易网络、各种流行病传染网络、城市交通网络、世界贸易网络。这些网络都对我们的生活起到十分重要的影响，尽管他们看上去不尽相同，但每一个都涉及很复杂的网络，更为重要的是：越来越多的研究表明，这些看上去不尽相同的网络在许多方面都有十分相似的特点。

随着对复杂网络各方面特点的研究越来越深入，人们发现几乎所有的复杂网络都有社团结构。即一个大型的复杂网络是由若干个小型社团组成的，社团内部节点的联接十分紧密，而社团之间的联接就比较稀疏。

本文采用了自顶向下的结构化分析方法，介绍了基于normal矩阵谱平分算法的网络社团结构识别设计。首先进行了项目概述，介绍了项目开发的背景、国内外研究现状以及研究的目的和意义。接下来是normal矩阵谱平分算法的原理及社团结构识别的方法，并将此方法应用于实际网络取得了不错的效果。

关键词：谱平分算法；网络社团结构识别；复杂网络

Detecting communities based on Normal matrix

Abstract

This project is named “Detecting communities based on Normal matrix”,detecting communities in large networks is more and more important,with the rapid development of science and technology, the whole world has become more and more closely related to human contact.In fact, people in the world are in a complex network of the world, such as the metabolic network, the world trade network, a variety of epidemic network, urban transport network, the world trade network. These networks have a very important impact on our lives,Although they look different, but each are related very complex network, more important is: more and more studies have shown, these look different network in many places has a surprisingly similar.

As the research of complex networks is getting deeper and deeper, it is found that there are many complex networks with community structure. A large complex network consists of a number of small organizations, the internal nodes of the community is very close, and the connection between the community is relatively sparse.

In this paper, the top-down structured analysis method is introduced, and the design of network community structure identification based on normal matrix spectral analysis algorithm is introduced. First of all, the project overview, describes the background of the project development, research status and the purpose and significance of the study. The next is the principle of normal matrix spectral divide algorithm and the method of community structure identification, and apply this method to the real network.

Key Words： spectral divide algorithm; detecting communities; complex network

目 录

引 言 1

第1章 绪论 2

1.1项目开发的背景 2

1.2国内外研究现状 3

第2章 基本概念 5

2.1网络的图表示 5

2.2平均路径长度 5

2.3聚类系数 6

2.4度分布 6

2.5社团结构检测 7

第3章 谱平分法介绍 9

3.1谱平分算法的基本思想 9

3.2基于normal矩阵的谱平分法 11

第4章 社团结构划分实验 13

4.1程序描述 13

4.2小型示例网络结果分析 13

4.3Zachary空手道俱乐部网络 16

总 结 18

参考文献 19

附 录 21

致 谢 26

引 言

许多系统都可以科学的被表示为网络：通过线或边连接的节点或顶点的集合。包括互联网和万维网，代谢网络，食物网，神经网络，通信和分销网络，和社会网络。网络系统的研究历史追溯了几个世纪，它在过去的十年中飞速发展，特别是在数学科学方面的研究，部分原因是由于越来越多的具有准确可用性的大规模描述网络的拓扑结构数据出现在现实世界中。这些数据的统计分析，揭示了一些意想不到的结构特征，如高速网络传递，幂律分布，和重复的社团存在模式。

有个问题已经引起了相当多的关注：在网络和社区结构中的特征检测，在密集连接组的顶点出现只有稀疏连接的组。检测到这样的社团可能有显著的实际意义。例如，在全球范围内的组可能对应于相关主题的网页；社会网络中的群体可以对应于社会单位或社团。仅仅是发现一个网络中包含着紧密联系的群体，能传递很多有用的信息：如果一个新陈代谢网络被分成了这样的群体，它可以提供一个模块化的视图的网络的动态，具有不同的组的节点进行不同的功能，具有一定程度的独立性的证据。

尽管网络是高度抽象的离散数学描述，但是其规模的庞大性和链接的复杂性使得功能和特点变得十分复杂。而社团化是一种揭示系统结构和功能之间对应关系，降低研究复杂网络难度的非常好的办法，社团结构识别在对于复杂网络的研究中起到了很重要的作用。

第1章 绪论

1.1项目开发的背景

20世纪90年代，随着网络技术的飞速发展与互联网的迅速普及，人类十分快速地进入了网络时代[1]，从互联网到维基百科，从物流运输网络到全球气候网络，从动物生活的生物圈网络到生物体内的循环网络，从各方面的科学研究到人们生活中的各种社会关系、工作、旅游网络，复杂网络对人类生活起到的影响日益渐增。其实复杂网络对于人类的生活是一把双刃剑：它使人们的生活越来越简单，越来越现代化，提高了人们的生活质量与幸福指数，却也带来了一些负面的影响，例如病毒的传播、大面积的交通堵塞。随着人类生活网络化的程度越来越高，对复杂网络的研究[2]也变得越来越重要。从20世纪末开始，越来越多的科学家发现了复杂网络研究广泛的实际应用性，从金融学科[3]、生命物理到信息物理等越来越多的领域都展开了对于复杂网络物理意义及数学原理方面的研究，在整个科学界承担着一个越来越重要的角色，甚至被称为“网络的新科学”。