摘 要

本文所研究的基于相异性的算法是根据节点到其他任一节点的距离通过表达式来计算出节点之间的相异性指数，再根据相异性指数来判断它们是否属于同一个社团，从而将网络划分成一系列具有层次的社团结构。本文对基于相异性的算法进行了详细的介绍，讲解了它的运行过程，并把它应用到空手道俱乐部网络验证它的可行性。研究后成功地将空手道俱乐部网络的社团结构划分，划分结果与实际情况相符合。该研究结果表明了基于相异性的算法是有效可行的。本文的特色在于我在研究过程中采用了用节点到其他任一节点的最短距离来代替平均距离这一更加简洁有效的方法，使算法计算过程更加简明。

关键词：社团结构；距离；相异性指数；相异性算法

Abstract

This paper studies the algorithm based on dissimilarity, the algorithm is based on the distance from the node to any other node to calculate the dissimilarity index between the nodes. Then according to the dissimilarity index to judge whether they belong to the same group. Thus, the network is divided into a series of hierarchical community structure. In this paper, the algorithm based on dissimilarity is introduced in detail, the operation process of it is explained, and apply it to the karate club network verify its feasibility. After the study, it successfully divides community structure of karate club network, the division result is consistent with the actual situation. The research results show that the algorithm is effective and feasible. The characteristic of this paper is that I used the shortest distance to replace the average distance in the research process, which is more simple and effective.

Key Words：community structure; distance; dissimilarity index; algorithm based on dissimilarity

目 录

第一章 绪论 1

1.1研究背景 1

1.2国内外研究现状 2

1.3研究内容 3

第二章 复杂网络及社团结构 5

2.1复杂网络的基本概念 5

2.1.1网络的图 5

2.1.2复杂网络的平均路径长度 6

2.2复杂网络的社团结构 7

第三章 基于相异性指数的算法 8

3.1算法的思想和原理 8

3.2算法的步骤 9

3.3算法的评价 10

第四章 matlab建模仿真 11

第五章 用基于相异性指数的算法识别典型网络 14

5.1空手道俱乐部网络 14

5.2海豚社会网络 15

总 结 17

参考文献 19

附 录 21

致 谢 28

第一章 绪论

1.1研究背景

随着信息时代互联网的迅猛发展，人与人之间的社会关系，人与社会环境之间的联系，物种之间的关系变得越来越错综复杂。随着图论的提出，对于社会网络的研究也迅速地发展起来。在图论的描述中，我们如果抽象的将每个个体作为一个点，其间的联系用边连线，构成的图就是复杂网络。各种复杂的网络在我们的生活中随处可见。由于复杂网络描述灵活形象，并且能对各种系统进行建模、分析，目前对它的研究已融入到社会学、生物学等众多科技领域。随着对复杂网络性质的深入研究，人们发现了一些如自吸引、小世界、无标度等特性，更发现许多网络其实都有社团结构这个共同性质。社团结构这一性质的研究受到了各个学科的学者的广泛关注。

研究识别复杂网络中的社团结构在实际生活中有非常重要的意义。网络社团结构就是说整个网络其实是由两个或者更多个“群落”或“集群”构成的，判断网络中的节点是否属于同一个群落是通过观察他们之间的联系是否紧密，因为在每个群落，它内部所包含的节点之间的连接相对非常紧密，而不同群落的节点之间连接相对来说就显得比较稀疏。在复杂网络中，我们可以根据各个节点具有的不同特性将它们划分为不同的社团。识别复杂网络中的社团结构对我们分析复杂网络的结构和性质是很有帮助的，我们可以从其中单个社团所具有的功能推测出整个复杂网络可能具有的功能，从社团的固有规律去推测复杂网络可能具有的规律，从而预测该网络可能出现的行为。社团结构分析已经成为近几年复杂网络领域研究的一个重要方向和热点，它在社会学、生物学、科技等领域中都有广泛的应用。就像在酿酒酵母中存在的蛋白质与蛋白质的互相作用网络，我们可以通过每个蛋白质集群所具有的被定义的生物功能来识别它们。社团结构的识别划分算法大体上分为凝聚算法和分裂算法两个大类。例如分裂算法中经典的一种：GN算法，虽然它能成功地将复杂网络划分成为一个个社团，却没有一个参数来定量地描述它划分出的各个社团之间的差异程度。为了找到这么一个能描述社团之间差异的参数，Zhou在布朗粒子移动生成的距离矩阵基础上引入了相异性指数的概念，该指数能定量地显示网络中两个最近相邻节点直接属于同一个社团的可能性大小。这样，一个按层次划分的算法就出现了，它利用相异性指数给出的信息，把一个网络分解成一序列按层次的簇群，其中的每个社团都具有标志性的上下相异性阈值。这个算法可以量化地划分复杂网络中的社团结构，并且通过在几个网络中的应用，我们发现它比之前的其他算法更加的精准。例如在人工随机组合网络中，用基于相异性的算法对网络的节点进行社团结构划分，产生错误分类的节点数目要比用GN算法小。我们的工作就是运用这个基于相异性指数的算法来对典型网络进行社团结构识别。

1.2国内外研究现状

复杂网络起源于图论，早期的图论为复杂网络的发展奠定了数学理论基础，而对它的研究从Wiener N等人将网络转化为数学中的图开始，他们通过用“节点”代替“顶点”，“边”代替“连接”来描述复杂网络[1]。在二十世纪末，对于复杂网络的研究开始明显兴起，其中具有代表性的是Watts和Stogatz在1998年提出了小世界模型，之后他们对它进行了更多的后续研究并指出了很多现实网络都具有小世界特性。随着研究的深入，对复杂网络的研究逐渐地产生了不同方向的各个分支，它们都以很快的速度发展起来。目前对复杂网络的研究工作主要包含了以下几个方面：1）复杂网络的建模与分析；2）复杂网络同步、控制和动力学特性；3）复杂网络抗毁性研究；4）复杂网络的社团结构检测；5）复杂网络搜索。在这几个方向中，复杂网络的社团结构检测是起源于人们发现许多网络其实都有社团结构这个非常重要的共同性质。例如我们生活中时刻用到的万维网，根据其中的网站所讨论的话题内容分类，我们可以把它看成是由很多个具有共同话题的网站社团组成的[2,3]，而在蛋白质网络中，整个网络就可以看成是由许多不同功能类型的蛋白质社团群落组成的。复杂网络的社团结构识别已经成为复杂网络研究工作中一个非常重要的分支，它的研究与计算机科学中的图形分割（graph partition）和社会学中的分级聚类（hierarchical clustering）有密切的关系[4,5]。研究过程中人们提出了很多用来划分复杂网络社团结构的算法，主要有以下几种：1）Kernighan-Lin算法；2）基于Laplace图特征值的谱平分法；3）分级聚类算法；分级聚类算法包含了凝聚方法（agglomerative method）和分裂方法（divisive method）[5]这两类；4）其他方法。GN算法就是一种典型的分裂方法[6]。与传统的算法相比，GN算法弥补了它们在一些方面的不足[7,8]，但和传统算法一样，它对网络社团结构依然没有一个量的定义。后来，Tsuchiura等人用布朗微粒在两个节点之间随机跳跃需要的步数来衡量两个节点之间的距离[9]。Zhou基于这种布朗微粒移动产生的距离矩阵，引入了相异性指数的概念，这样就定量的描述了网络中两个最近相邻节点属于同一个社团的可能性大小[10]。之后又有外国研究者相继提出了一种加权相异测度的聚类优化算法[11], 考察了不同的位置参数的人群抽样的相异指数的模拟样本行为[12] 和一个统一种群中两个样本的相异指数分布[13], Manter Daniel K和Bakker Matthew G则作了采样社团使用可变加权奥德姆的相异性指数研究[14],国内方面汪小帆、李翔、陈关荣在《复杂网络理论及其应用》一书中介绍了基于相异性的算法[15]，汪小帆是国内研究的代表人物，他还和刘亚冰综述了复杂网络社团结构研究领域一些比较新颖的有代表性的算法,他们重点分析了基于模块度指标的改进算法[16]。张太华、顾新建、吴永祥提出了基于最短路径的相异性算法，这是对Zhou提出的算法的一大改进[17]。黄浩英则是研究提出了独具特色的基于相异性系数和谱分析的社团发现算法的相异性指数算法[18]。

1.3研究内容

本次我研究的课题就是运用基于相异性指数的算法对一些典型网络进行社团结构识别设计，在研究中我主要做了以下几方面的工作：

（1）学习了复杂网络理论的基本知识，学习了网络社团结构的相关知识，对复杂网络进行了概述，总结了网络的一些基本概念、性质和特点。尤其是认识了我所选取的研究对象：空手道俱乐部网络和海豚网络。在研究过程中，我了解了这些网络，知道了它们的背景，查看了它们在被不同算法研究处理后得到的社团结构。