复杂网络社团发现理论与应用 pdf下载

适读人群 ：计算机、自动化等专业高年级本科生、研究生和相关研究人员

该书的主要内容包括了近年来国内外在该领域最重要的研究成果，如社团的主要发现方法、社团发现合理性的评价指标、社团结构的分辨率和视野的局限性、社团的层次结构等

《复杂网络社团发现理论与应用》主要介绍复杂网络社团发现理论与应用。复杂网络社团发现旨在揭示复杂网络中真实存在的网络社团结构。研究复杂网络社团结构，在分析实体复杂网络的拓扑结构、理解现实复杂网络的功能、发现复杂网络隐藏的规律和预测复杂网络的动力学行为等方面具有重要的现实意义，并且具有广泛的应用前景。《复杂网络社团发现理论与应用》首先介绍复杂网络基础知识、社团定义及相关基础和社团定量刻画；其次介绍主流的社团发现方法、算法和社团结构的层次性；最后介绍社团发现的应用。

该书的主要内容包括了近年来国内外在该领域最重要的研究成果，如社团的主要发现方法、社团发现合理性的评价指标、社团结构的分辨率和视野的局限性、社团的层次结构等

目录
前言
第1章 复杂网络基础知识 1
1.1 复杂网络概述 1
1.2 图论基础 2
1.2.1 图的矩阵表示 3
1.2.2 度分布 5
1.3 无标度网络 7
1.3.1 泊松分布与幂律分布 7
1.3.2 BA模型 9
1.4 小世界网络 13
1.4.1 平均路径长度与聚类系数 13
1.4.2 WS模型和NW模型 16
1.5 度相关性 20
1.6 现实世界中的复杂网络 22
参考文献 24
第2章 社团定义及相关基础 26
2.1 网络的社团特性 26
2.1.1 网络社团的普遍性 26
2.1.2 社团定义 34
2.1.3 社团内部结构 41
2.2 基准网络及其社团结构 45
2.2.1 计算机生成的基准网络 45
2.2.2 实际基准网络 47
2.2.3 划分结果比较方法 50
参考文献 52
第3章 社团定量刻画 55
3.1 社团分割的合理化指标 55
3.2 Newman模块度 56
3.2.1 配置模型 57
3.2.2 基于Newman模块度的GN算法 57
3.2.3 Newman模块度的局限性 60
3.3 基于信息论的社团分割合理性度量 68
3.3.1 网络中的随机行走理论 69
3.3.2 基于随机行走理论的模块度 75
3.3.3 基于编码的模块度 76
参考文献 77
第4章 基于寻优的社团发现方法 79
4.1 贪婪算法 79
4.1.1 基于Newman模块度的寻优方法 79
4.1.2 基于编码模块度的寻优方法 85
4.2 蚁群算法 90
4.2.1 基于Newman模块度的寻优方法 92
4.2.2 基于编码模块度的寻优方法 94
4.3 模拟退火算法 97
4.3.1 基于Newman模块度的寻优方法 98
4.3.2 基于编码模块度的寻优方法 101
参考文献 102
第5章 基于直观概念的社团发现算法 104
5.1 分裂算法 104
5.2 网络合并算法 116
5.2.1 网络合并算法概述 116
5.2.2 相似度指标 124
5.2.3 基于相似度的网络合并 126
5.3 谱分析算法 126
5.3.1 基于谱分析的社团划分算法 129
5.3.2 网络矩阵谱分析方法的综合分析 136
参考文献 140
第6章 重叠社团发现算法 142
6.1 重叠社团的定义 142
6.2 派系过滤算法 144
6.3 基于边的社团发现算法 150
参考文献 166
第7章 多尺度社团发现与网络的层次结构 168
7.1 社团发现方法的分辨率局限特性 168
7.2 多尺度社团发现方法 172
7.2.1 基于社团数量的多尺度社团发现方法 173
7.2.2 基于参数化模块度的多尺度社团发现方法 183
7.2.3 不同尺度社团结构之间的嵌套性分析 191
参考文献 195
第8章 社团发现的应用 197
8.1 用户通话网络的社团结构 197
8.1.1 用户通话网络模型构建及拓扑结构 197
8.1.2 通话网络的社团发现及应用分析 203
8.2 BBS用户网络的社团结构 208
8.2.1 BBS用户网络模型构建及拓扑结构 208
8.2.2 社团发现与热点主题 212
8.3 复杂公交网络的性能分析 215
8.3.1 城市公交网络模型 216
8.3.2 社团划分及其应用 223
8.3.3 公交停靠站点网络抗毁性分析和网络优化 225
参考文献 227

第1章 复杂网络基础知识
　　网络规模的扩大增加了大型复杂网络的研究难度。为了在可接受的计算成本下发现并研究网络中蕴含的规律，有必要简化研究对象，因而社团发现算法越来越受人们的关注。在复杂网络中发现社团结构，并以这些社团结构为单位形成的网络作为研究对象，能够大幅减少研究的复杂度。
　　本章介绍复杂网络及其在科学领域和现实世界中的应用，主要介绍与社团发现有关的复杂网络基础知识，包括复杂网络概述、图论基础、无标度网络、小世界网络、度相关性和现实世界中的复杂网络等内容。
　　1.1 复杂网络概述
　　物理学家霍金认为：21世纪是复杂性的世纪。作为研究复杂性科学和复杂系统的有力工具，复杂网络已成为学术界研究的一个热点，在工程技术、社会、政治、医药、经济和管理领域都有着潜在和广泛的应用。复杂网络借助图论和统计物理的方法，可捕捉并描述系统的演化机制和规律，同时也能很好地分析系统的整体行为。复杂网络的复杂性主要体现在以下几个方面。
　　(1) 结构复杂性：网络结构纵横交错、复杂混乱，且连接结构可能随时发生改变。例如，万维网(world wide web， WWW)每天都会产生和删除许多网页和链接。另外，节点之间的连接可能具有不同的权重和方向。例如，交通网络中每条公路上都有不同数量和方向的汽车在行驶。
　　(2) 节点复杂性：网络中的节点可能是具有分岔和混沌等复杂非线性行为的动力系统。例如，基因网络中每个节点都具有复杂的时间演化行为。一个网络中还可能存在多种不同类型的节点。例如，控制哺乳动物细胞分裂的生化网络包含各种各样的蛋白质和酶。
　　(3) 各种复杂性因素的相互影响：现实中的复杂网络每时每刻都会受到各种因素的影响。例如，如果耦合神经元同时被重复激活，它们之间的连接就会加强，这也是记忆和学习的基础。另外，各种不同类型的网络之间也存在密切的联系，从而相互影响，如电力网络的故障可能会导致网络流量变慢、金融机构关闭、运输系统失去控制等一系列连锁反应。
　　由于真实网络的规模庞大、结构复杂，其拓扑结构在21世纪初才得到广泛的研究。人们对真实网络拓扑结构的研究大致经历了以下过程：最初，研究者们认为真实网络各要素之间的关系可以用一些规则的结构表示，如二维平面上的网格；20世纪50～90年代末，人们主要用随机网络描述没有明确设计原则的大规模网络；近年来，研究者们发现大量的真实网络既不是随机网络，也不是规则网络，而是统计特性与前两者都不同的网络，其中最有影响的复杂网络模型是小世界网络和无标度网络。下文将介绍复杂网络中需要用到的基本概念。
　　网络可以抽象为一个由节点集V和边集E组成的图，节点数记为，边数记为。网络中节点和边与具体研究对象紧密相关。例如，在生命系统的巨型遗传网络中，节点表示蛋白质，边表示蛋白质之间的相互作用；在WWW中，节点表示各个不同的页面，边表示页面之间的链接。节点数和边数均有限的图称为有限图，否则称为无限图。由于研究的网络都是真实网络的模型，一般为有限图。如果网络中任意一个节点对与对应同一条边，则称该网络为无向网络，否则称为有向网络。两个端点相同的边称为环(loop)，有公共起点并且同时具有公共终点的两条边称为平行边或重边。无环并且没有重边的图称为简单图，任何两个节点之间都有边相连的简单无向图称为完全图。现实世界中的网络往往需要根据某种度量标准，为网络上的每个点和每条边都赋予相应的权值，这种网络称为加权网络[1，2]。例如，在交通网中，每两个站点之间的距离不同，而且每条线路上的车流量往往也不同，即每条边具有不同的权值。没有赋予权重的网络称为无权网络，无权网络也可以看作是每条边的权值都是1的网络。点和边的权值通常用和表示。无向网络中，一个点的权值是与之相连的所有边的权值总和，即。
　　介数分为节点介数和边介数。节点介数为网络中所有最短路径中经过该节点的数目比例，边介数的含义和节点介数相似。介数反映了节点和边在整个网络中的地位和作用，有很具体的现实意义。在社会关系网络或技术网络中，介数的分布特征反映了不同人员、资源、技术等因素在生产关系中的地位，对在网络中发现和保护关键资源和技术具有非常重要的意义。
　　1.2 图论基础
　　图论最早起源于1736年欧拉(Euler)所解决的哥尼斯堡(Konigsberg)七桥问题，现已广泛应用于计算机科学、商业、心理学等领域。本节介绍图的矩阵表示和度分布。
　　1.2.1 图的矩阵表示
　　任何复杂的网络都可以表示为图，借助矩阵对图进行研究，可以大大简化和促进对图的分析。
　　1. 邻接矩阵
　　每一个图都是由节点和连接一对节点之间的连线组成，其中连线的长度和节点的位置无关紧要。图1-1是同一个图的两种表示。
　　图1-1 同一个图的两种表示
　　定义1-1 设是一个简单图，它有个节点，则阶方阵称为图的邻接矩阵。
　　图1-2 5个节点的简单无向图
　　其中，表示节点相邻，表示节点不相邻。例如，5个节点的简单无向图(图1-2)的邻接矩阵为
　　当给定的简单图是无向图时(图1-2)，邻接矩阵对称；当给定的简单图是有向图时，邻接矩阵不一定对称。
　　2. 关联矩阵
　　定义1-2 设图有个节点和条边，和。的关联矩阵定义为的二进制矩阵，其中若与关联，则；否则。
　　容易看出，矩阵的行对应个节点，列对应条边。例如，图1-3为6个节点8条边的简单无向图，关联矩阵为
　　图1-3 6个节点8条边的简单无向图
　　的第行元素的和为deg()，这对邻接矩阵显然也成立，而且每一列的和都是2，这是由于每条边都与且仅与两个节点关联。令为的对角矩阵(所有的非对角线元素都为0)，满足。
　　容易验证，对于邻接矩阵、关联矩阵和对角矩阵，存在。无论是邻接矩阵还是关联矩阵都可以确定一个唯一的图；反过来，一个图可以有多个邻接矩阵和关联矩阵。这是由于对于邻接矩阵，可以改变节点的标记序列；对于关联矩阵，可以改变节点和边的标记序列。
　　3. 距离矩阵
　　顾名思义，距离矩阵存储的是节点间的距离。
　　对于图，定义的距离矩阵的元素。显然。另外，根据距离的对称性，有，即图的距离矩阵为对称矩阵。例如，图1-4的距离矩阵为
　　图1-4 6个节点的简单无向图
　　1.2.2 度分布
　　度是节点属性中简单而又重要的概念，是网络的一个重要统计特征。与节点连接的其他节点的数目，或者连接到该节点的边的条数称为节点的度。节点的度有两个延伸概念，一个是最小度；另一个是平均度。最小度是指网络中度最小的节点的度。平均度是指网络中所有节点的度的算术平均值，即
　　(1-1)
　　在任意图中，因为每条边必关联两个节点，而一条边给予每个关联节点的度值贡献为1，所以图中节点度值的总和等于边数的两倍：
　　(1-2)
　　在有向网络中，度分为入度和出度。节点的入度是从其他节点指向该节点的边的数目，记为：
　　(1-3)
　　出度是从该节点指向其他节点的边的数目，记为：
　　(1-4)
　　在无向图中，可以看成是将每个节点映射到一个非负整数的函数，即()。在图1-2的邻接矩阵(G)中，可以看到，第行元素由节点出发的边决定，第行中值为1的元素数目等于的出度。同理，在第列中值为1的元素数目是的入度。不难发现，一个节点的度越大，说明它在网络中的地位越重要。
　　网络中节点度的分布情况可用分布函数描述，表示一个随机选定节点的度恰好为的概率。在实证研究中，经常以频率代替概率的模拟统计方法计算度分布，即取网络中度值为的节点数与节点总数的比值，网络中所有节点度的平均值称为网络的平均度，记为，。图1-5中共有10个节点，其中度值为3的节点有6个，度值为4的节点有3个，度值为6的节点有1个，因此该图的度分布为。
　　图1-5 由10个节点构成的简单无向图
　　度分布是区分不同结构复杂网络的一个重要指标。例如，阶完全图所有节点都与其他任意节点相连，因此它的节点度值都是，度分布是。星形网络的度分布是两点分布，而规则网络的度分布是单点分布。
　　根据不同类型的度分布，可以将网络分为均匀网络和非均匀网络。规则格子网络和完全随机网络都属于均匀网络，前者有简单的度序列，是由于所有节点具有相同的度，度分布为Delta分布，函数图形为单个尖峰的形状。后者的