复杂网络结构分析方法及应用

计算机网络,网络结构,研究

《复杂网络结构分析方法及应用》通过实际案例从应用的角度介绍复杂网络分析方法，主要介绍复杂网络理论在基因转录调控网络分析领域、图像目标识别领域、教学质量评价领域的应用。在基因转录调控网络分析领域，首先构建基因转录调控过程复杂网络模型，然后通过网络拓扑结构识别具有特定功能的模块。在图像目标识别领域，首先构建图像的复杂网络模型，然后通过图像网络模型的拓扑结构特征识别关键点（集）和关键目标。在教学质量评价领域，首先构造教学质量评价复杂网络模型，然后根据网络模型的拓扑结构特征综合评价学生的培养质量。*后，介绍三种分别用于上述三个领域的分析平台软件。

目录
前言
第1章 复杂网络结构分析概述 1
1.1 网络可视化 2
1.2 网络结构量化指标 4
1.2.1 中心度量指标 5
1.2.2 模块性 9
1.3 实际网络研究现状 15
1.3.1 复杂网络理论 15
1.3.2 医学网络 16
1.3.3 技术网络 19
第2章 基因转录调控网络分析 21
2.1 网络生物学 21
2.2 基因转录调控过程 22
2.2.1 基因表达 22
2.2.2 转录调控 24
2.3 基因转录调控网络的关系数据来源 25
2.4 转录调控网络的构建 27
2.4.1 布尔网络 28
2.4.2 贝叶斯网络 29
2.4.3 神经网络 32
2.4.4 微分方程 32
2.5 基因转录调控网络结构特征分析 34
2.5.1 转录调控网络结构三个层次 34
2.5.2 网络结构特征比较分析 36
第3章 基因转录调控网络功能模块识别方法 49
3.1 基于边特征属性的原核生物转录调控网络功能模块识别算法 49
3.1.1 边相似度 49
3.1.2 基于图论的层次聚类算法 50
3.1.3 边网络的构建 52
3.1.4 原核生物基因转录调控网络模块识别结果 53
3.2 基于三元组分布特征的模块识别算法 56
3.2.1 网络模体和三元组 56
3.2.2 基于边相似度算法OCDT 63
3.2.3 实验结果与讨论 65
第4章 基于复杂网络的图像目标识别 67
4.1 复杂网络理论在图像目标识别中的应用研究概述 67
4.2 基于有向复杂网络拓扑结构特征的图像关键点识别方法 71
4.2.1 图像的复杂网络模型 72
4.2.2 基于节点结构特征的关键点识别方法 73
4.2.3 基于有向复杂网络拓扑结构特征的图像关键点识别结果 74
4.3 基于有向复杂网络三元体分布特征的图像关键点识别方法 78
4.3.1 图像的复杂网络模型 79
4.3.2 复杂网络模型社团识别方法 80
4.3.3 基于有向复杂网络三元体分布特征的图像关键点识别结果 81
4.4 基于有向复杂网络拓扑结构特征的视频监控图像关键点识别方法 84
4.4.1 视频监控图像复杂网络模型 84
4.4.2 关键点识别 85
4.4.3 视频监控图像关键点识别结果 85
4.5 基于复杂网络理论的水中细菌图像关键点识别方法 87
4.5.1 图像复杂网络模型 88
4.5.2 关键点特征值计算方法 89
4.5.3 水中细菌图像关键点识别结果 89
4.6 基于多层次复杂网络拓扑特征的图像关键点识别方法 91
4.6.1 图像的局部复杂网络模型 92
4.6.2 图像的高层次复杂网络模型 92
4.6.3 关键点识别结构特征 93
4.6.4 基于多层次复杂网络拓扑特征的图像关键点识别结果 94
第5章 复杂网络理论在高校应用技术型工科专业评价领域的应用 100
5.1 高校应用技术型工科人才培养质量评价指标 100
5.1.1 应用技术型工科人才知识结构评价指标 101
5.1.2 应用技术型工科人才能力结构评价指标 102
5.1.3 应用技术型工科人才思想品德评价指标 103
5.2 一种基于相互评价的学生培养质量评价复杂网络模型 103
5.2.1 基于互评的教学评价复杂网络模型的动态演化 104
5.2.2 基于互评的教学评价复杂网络结构特征分析 105
5.2.3 基于互评的教学评价复杂网络评价结果 105
5.3 基于复杂网络拓扑结构特征的课程教学评价模型 107
5.3.1 基于方格技术的课程教学评价复杂网络模型的构建 108
5.3.2 基于复杂网络拓扑结构特征的课程教学评价结果 109
5.4 基于复杂网络理论的电子科学与技术专业学业成绩评价模型 112
5.4.1 课程影响复杂网络模型构建 113
5.4.2 电子科学与技术专业学业成绩评价网络模型评价结果 115
5.5 基于复杂网络理论的电子信息工程专业学习成绩评价模型 116
5.5.1 电子信息工程专业学生成绩评价复杂网络模型的构建 117
5.5.2 电子信息工程专业学生成绩评价复杂网络模型评价结果 120
5.6 基于通信工程专业学业成绩的复杂网络评价模型 121
5.6.1 通信工程专业学生综合评价复杂网络模型的构建 122
5.6.2 通信工程专业学业成绩评价复杂网络模型评价结果 124
5.7 基于电子信息工程专业课程体系的智能硬件与产品设计专业课程设置评价 126
5.7.1 课程关系网络模型的构建 126
5.7.2 电子信息工程专业和智能硬件与产品设计专业课程关系网络特征分析 128
5.8 基于电子信息工程专业的车联网方向课程评价 130
5.8.1 课程关系网络模型的构建 130
5.8.2 基于网络模型结构特征的课程评价 132
5.9 基于电子信息工程专业的智能数据工程方向课程体系评价 133
5.9.1 课程关系网络模型的构建 133
5.9.2 基于网络模型结构特征的课程评价 134
第6章 复杂网络分析应用平台 137
6.1 基因转录调控网络分析平台 137
6.1.1 平台的功能和结构 137
6.1.2 网络模块识别评价函数 139
6.1.3 定向网络重叠模块划分质量评价函数 141
6.2 图像复杂网络模型分析平台 142
6.2.1 图像复杂网络模型分析平台的功能和结构 143
6.2.2 图像复杂网络模型分析平台界面 144
6.3 应用技术型高校人才培养质量评价平台 145
6.3.1 平台界面 146
6.3.2 课题研究应用结果及评价 148
参考文献 149

第1章 复杂网络结构分析概述
　　过去几个世纪，自然科学的许多成就都是建立在还原论方法的基础上的，即把复杂系统简化为一个个小的、孤立的部分的组合。然而，由于自然现象所固有的复杂性无法嵌入理论分析中，用还原论方法只能处理真实世界中有限类别的复杂系统。目前的科学发展有一种趋势，就是把各种科学方法扩展为更加统一的方法，复杂网络就是在这样的科学框架下发展起来的一种科学领域。
　　世界上许多系统都是由各个部分或部件以某种方式连接在一起组成的。例如，因特网是被连接起来的计算机的集合，人类社会是被社会交往联系起来的人的集合。这些系统的许多方面都值得研究，例如，研究单个部件的性质，如计算机如何工作，或者一个人如何感觉或行动。也可以研究连接或交互的性质，如因特网上使用的通信协议或动态通信过程。但这些相互作用的复杂系统还有一个对系统行为至关重要的方面，那就是组成元素之间的连接模式。
　　一个给定系统中的连接模式可以表示为一个网络，系统的组成部分是网络节点，连接部分是边。我们发现，这种网络的结构，特别是相互作用的特定模式，会对系统的行为产生重大影响。例如，因特网上计算机之间的连接模式影响数据传输的路由和数据的传输效率。社交网络中的联系影响着人们学习、形成观点和收集新闻的方式，也影响着其他不太明显的现象，如疾病的传播。除非我们对这些网络的结构有所了解，否则不可能完全理解相应的系统是如何工作的。网络是一种简化的表示，它将一个系统简化为一个抽象结构，只表达出连接模式的基本结构。可以在网络中的顶点和边上标记附加信息，以表达系统的更多细节。
　　复杂网络是一些聚集在一起的节点被一定数量的边连接起来所构成的图形。在很多领域，复杂网络可以看作复杂系统的抽象表达形式或简化形式，用于表达复杂系统中各组成元素之间的连接模式（Liu et al.，2011；Boccaletti et al.，2009；Newman，2003）。一个具体的网络可以表示为一个由节点集合V和边集合组成的图。节点的数量 ，边的数量。如果图中任意的节点对和对应同一条边，则该网络是无向网络。如果图中的边表示由节点i指向节点j的边，那么该网络就是定向网络。如果给每条边都赋予相应的权值，则该网络就称为权值网络。如果网络是所有边权值都为1的等权网络，那么该网络就称为无权网络。
　　图1-1描述了四种不同类型的网络，其中图1-1（a）为无向无权网络，图1-1（b）为定向无权网络，图1-1（c）为定向权值网络，图1-1（d）为无向权值网络。无论哪种类型的网络都可以用邻接矩阵A来表达，A是一个的矩阵，其中行和列代表网络节点，矩阵的元素代表节点间存在的边。
　　（1-1）
　　表示权值网络时，eij是边的权值；表示无权网络时，。如果网络是无向的，则邻接矩阵A是对称矩阵。如果网络是定向的，那么A就是非对称矩阵。网络的数学模型是研究网络各种特征属性的基础。
　　图1-1 不同类型网络举例
　　图中箭头的方向表示定向网络中边的方向，数值表示权值网络中边的权值
　　1.1 网络可视化
　　各种各样的系统都可以表示为网络。如果可以收集这些网络结构的数据，那么可以用这些数据做什么呢？关于复杂网络所代表的复杂系统的形式和功能，它们能告诉我们什么？我们可以分析或构建网络模型的哪些特性？这些特性与我们关心的实际问题有什么关系？这些都是本书所要表达的主题。本节将简要地介绍常见的复杂网络可视化工具，并在1.2节中介绍度、介数、接近度等复杂网络中心度量指标和复杂网络模块结构性度量指标，以利于我们接下来对各种复杂实际网络的讨论。
　　分析一个网络结构的**步往往是把它描绘出来，图1-2是一个复杂网络的典型实例。网络可视化模型是由专门为网络可视化设计的计算机程序生成的，有许多这样的工具可供使用，有商业的，也有免费的。
　　图1-2 一个定向网络
　　目前被广泛使用的复杂网络分析平台主要有Pajek（Nooy et al.，2011）、UCINET（Petrou，2001）、Cytoscape（Kohl et al.，2011）和NeAT（Brohee et al.，2008）。
　　Pajek是由Mrvar等学者于1996年开发的专门处理大型网络的应用软件，主要目标是将大型网络分解为若干子网从而进行更加细致和精确的分析，同时软件提供很多有效的网络分析算法，可以进行聚类分析、中心度分析、因子分析、差异性分析等多种常见分析。通过参数设定，Pajek软件可以生成随机网络、无标度网络等各种复杂网络模型，能够计算节点度、*小路径、聚类系数等常用的网络结构属性。Pajek拥有强大的可视化功能，基于Kamada-Kawai、2D Fruchterman-Reingold和3D Fruchterman-Reingold算法可以根据节点距离展示网络结构形态。
　　UCINET也是一个被广泛使用的网络分析平台，由加利福尼亚大学欧文分校的一群网络分析者编写。UCINET软件将目标网络的矩阵和该矩阵的相关信息分开输入，在分析时可以将网络数据与其属性值相结合，能够有效地处理缺失数据。UCINET软件提供了多种数据处理和分析工具，可以进行模块识别、聚类分析、中心度分析、结构洞分析等多种网络结构分析，并且可以构造出系统图和树状图。但是由于UCINET软件自身没有网络可视化程序，需要借助其他软件才可以进行可视化。
　　Cytoscape是一个开源的生物信息学软件平台，它能够将不同的生物分子表达数据按照统一的形式整合在一起构成完整的生物分子网络，Cytoscape平台的内核提供了网络可视化的基本功能，并且可以通过插件很容易地增加软件平台的功能（Kohl et al.，2011）。
　　NeAT软件能够兼容多种生物网络数据库的数据格式，能够转换网络的表达形式，识别网络间的相同点与不同点，生成各种随机网络，查找*小路径。除此之外，该软件还具有派系提取、邻接节点提取、显示聚类结果和比较聚类结果等功能（Furht and Borko，2010）。
　　除以上四个软件平台以外，还有很多平台被用于生物网络等复杂网络的构建、可视化和结构分析当中，表1-1列出了目前主要的复杂网络分析平台及其功能。从表中可以看出，绝大多数的分析平台都具有网络可视化和拓扑结构分析功能，少部分的分析平台能够在无向网络中识别模块，但是目前还没有能够在定向网络中识别出重叠模块的分析平台。
　　表1-1 复杂网络结构分析平台
　　1.2 网络结构量化指标
　　在分析网络数据时，可视化是非常有用的方式，它可以让人立即看到网络的重要结构特征，否则很难从原始数据中找出这些特征。可视化允许我们将这种天赋用于解决网络问题，但是，网络的直接可视化只适用于只有几百或几千个顶点的网络，以及相对稀疏的网络。如果一个网络中有太多的顶点或边，那么这个网络图就会非常复杂，以至于肉眼难以识别其特征，可视化网络图的用处就会变得很有限。今天，许多实际网络有数十万甚至数百万个节点，这意味着可视化对其分析没有多大帮助，我们需要使用其他技术来确定它们的结构特征。为了满足这一需求，复杂网络理论开发了一个巨大的工具库，其中包含度量和度量标准，可以帮助我们理解复杂网络数据的特征。
　　1.2.1 中心度量指标
　　中心度量是一种重要并且十分有效的网络结构特征量化指标。在一个网络系统中，中心性量化了节点或边的重要性，有各种各样的节点中心性的数学测量方法，它们关注的是网络中心的不同概念和定义。
　　1.度分布
　　度（degree）也称为连通度，是网络节点的一个*简单也是*重要的属性（Egerstedt，2011；Ghoshal and Newman，2007）。一个网络中节点的度数就是它所连接的边的数量。在因特网中，度是指计算机、路由器或其他设备的数据连接数。在许多情况下，网络中度值**的节点，也就是那些连接*多的节点，在系统的运行中也扮演着*重要的角色，因此度可以作为一个有用的网络结构特征指标，帮助我们将注意力集中在系统*关键的元素上。
　　节点的度是与之相连接的所有边的数量，在无向网络中，节点的度只是一个单一的数字，但在定向网络中，节点的度分为出度和入度两种，其中出度是指从该节点指向其他节点的边的数量，入度是指从其他节点指向该节点的边的数量。例如，Web页面的入度是链接到它的其他页面的数量，出度是它链接到的页面的数量。也就是说，在邻接矩阵为的网络中，如果存在一条由节点i指向节点j的边，则Aij=1，那么节点的出度和入度分别为
　　（1-2）
　　因为网络中所有节点的出度之和等于入度之和，等于网络中所有边的数量m，即 ，所以网络的平均出度cout等于平均入度cin，即 ，显然在定向网络中。
　　如果一个由n个节点构成的定向网络中所有的边都为单向边，那么该网络中可能存在的**边数为。边密度用来衡量网络的密集程度，它等于网络中边的实际数量与理论**值之间的比值：
　　（1-3）
　　边密度的值为0～1。当网络中节点数量趋向于无穷大时，如果边密度趋向于0，则网络称为稀疏网络；如果边密度趋向于1，则网络称为密集网络。在对复杂网络进行研究时，往往依据实际情况设置阈值区分稀疏网络和密集网络。
　　网络中节点度的分布是其*重要的属性之一，可以用分布函数PD(k)和累积度分布函数PDc(k)来描述。PD(k)表示度为k的节点在所有节点中所占的比例，PDc(k)表示度大于等于k的节点在所有节点中所占的比例。
　　2.接近度
　　接近度（closeness）是衡量网络节点之间平均距离的物理量，用于判断网络中信息传递的效率（Mason and Verwoerd，2007）。网络中节点间的距离是指连通两个节点的一系列顺序相连的节点和边的序列中*短序列的长度，这些节点和边的序列就是路径，因此节点间的距离也称为*短路径。路径的长度是指路径包含的边的数量，不同的路径可能包含相同的边。例如，在一个朋友网络中，两个朋友的距离是1，因为有一条边直接将他们连接起来，而自己的朋友的朋友与自己的距离是2。
　　在一个邻接矩阵为的定向网络中，如果Aij的值为1，则说明网络中存在一条从点i到点j的边，如果AikAkj等于1，则说明网络中存在一条从点i经过点k*终到达点j的长度为2的路径。在网络中这种从点i到点j的长度为2的路径总数。同理，如果AikAklAlj等于1，则网络中存在一条从点i经过点k再经过点l*终到达点j的路径，这种路径的总数。以此类推可以得到，从点i到点j的长度为r的路径总数。
　　在定向网络中，接近度可分为出接近度和入接近度。如果用dij表示从点i到点j的距离，用dji表示从点j到点i的距离，那么节点i的出接近度为