|
|
一、网络模型
1、规则网络Regular networks
- 全局耦合网络Globally coupled network：网络中的任意两点都有边相连
平均路径长度最小而聚类系数却是最大
- 最近领耦合网络Nearest-Neighbor Coupled Network：网络的每个节点仅与其两边最近几个节点相连
网络的平均路径长度会随着节点数量的不断增大而增大；聚类系数很高
- 星形网络Star network ：它有一个中心点，网络中剩下的所有节点都与这个中心节点直接相连，而彼此之间没有连边
规则网络示例
2、复杂网络Complex networks
真实系统通过高度抽象得到的具有复杂结构和特性的网络被科学家们称为复杂网络。
复杂网络：是一种特殊的网络结构,它是将复杂系统中的元素抽象为节点,元素间的关系抽象成边的网络结构模型.并不是所有的网络都属于复杂网络,它需要满足如下的三个特征:1）小世界特性(Small world),即网络中点与点之间的特征路径长度值小,接近随机网络,但网络的聚合系数却很高,接近规则网络。2)无标度特性(Scale-free),即在网络中少数节点的度值会很大,而大部分节点却很小,节点的度值分布符合幂率分布规律"~-。3）社团结构特性,复杂网络中的节点往往会呈现出集群特性,即社团区域内部节点之间的联系非常强,而社团内节点与社团外节点的联系明显减弱。
1）随机网络(ER 随机网络) A random network
- 定义：在由 N 个节点构成的图中以概率 P 随机连接任意两个节点而形成的网络，即节点间有无连边是一个不确定的事，而是被一个概率 P 决定.
- 特点：没有聚类特性但具有较小的平均路径长度
随机网络示例
2）WS 网络/小世界网络
- 定义：通过用非常小的概率 p 移除规则网络 里的原始边，并随机连接一个新的端点，构造的新的网络（即WS 网络）
- 平均路径长度较小且聚类系数很大
小世界网络
图中p=0 对应于规则网络，p=1 对应于完全随机网络
3）无标度网络模型（BA 网络模型）
- 引入增长型和优先连接性来进行网络的构造：即网络中不断加入新的节点，新节点加入后优先与网络中节点度大的节点连接
4）其他网络模型
- 确定性无标度网络模型
- 确定性小世界网络模型
- 多局域世界演化网络模型
- ……
二、基础知识
1、相依边、相连边、空闲连边、桥边
- 相连边 ：同一层网络节点之间的连边
- 相依边：不同层网络具有相互依赖关系节点之间的连边
- 空闲连边：是一种虚拟连边, 指的是那些在级联失效过程中断开的连边。当一条连边断开以后, 则它两端的节点各自得到一条空闲连边，如下a中虚线边所示：
- 桥边：用于保持全局连通性，比如社团之间的边，这类边通常会对网络中的信息流转起着至关重要的作用，称之为桥边。桥边对整个网络的连通性和可靠性具有重要的影响。
2、网络巨片、连通分量
网络中往往会存在一个特别巨大的连通片，包含了整个网络的绝大多数节点，因此称为巨片（Giant Component）
连通分量：无向图G的一个极大连通子图称为G的一个连通分量（或连通分支)。连通图只有一个连通分量，即其自身;非连通的无向图有多个连通分量。
3、共同边界节点
共同边界节点：两个网络中距离各自巨分支距离为 1 的一对失效的相互依赖节点
4、无标度网络（scale-free network）
无标度网络具有严重的异质性，其各节点之间的连接状况（度数）具有严重的不均匀分布性：网络中少数称之为Hub点的节点拥有极其多的连接，而大多数节点只有很少量的连接。少数Hub点对无标度网络的运行起着主导的作用。从广义上说，无标度网络的无标度性是描述大量复杂系统整体上严重不均匀分布的一种内在性质。
- hub：度值非常大、直接相连的“枢纽节点”
- 度分布为幂律的网络也被称为无标度网络 。
- 无标度网络是怎么产生的？最直接的解释是网络节点本身的特性->增长和优先连接：
- 增长：网络规模不断扩大，后来新节点与已存节点进行连接，即使是随机的，但因为早期节点更容易被发现，所以被连接的概率也会较大；
- 优先连接：新节点总是更倾向于与那些具有较高连接度的节点相连。就好比同等条件下人们往往选择朋友更多的那个做朋友。
5、局域攻击
局域攻击也叫局部攻击, 指的是网络位于某个地理空间范围内的节点受到了攻击
在现实生活中, 局域攻击比随机攻击更为普遍, 如军事打击、自然和人为的灾害等
6、控制层网络、非控制层网络
非控制层网络：不能人为干预
7、复杂网络的统计特性
1）平均路径长度
复杂网络里，两节点之间的最短路径上所包含的边的数目就表示两个节点之间的距离。网络中任意两个节点之间距离的平均值就是网络的平均路径长度，它代表了网络中节点间的分离程度，是网络全局特性的反映。
2）度、度分布、度相关性
- 度：复杂网络里，一个节点与网络中其他节点的连边总数就是节点的度。
- 度分布：网络中节点的度值按从小到大排序，统计得到度为 k 的节点占整个网络节点数的比例 P(k)，就是网络的度分布（Degree distribution）；从概率角度看，P(k)就是网络中随机选择一个节点，其度为 k 的概率
- 度相关性
- 同配：度大节点倾向于连接度大节点。同配网络相关性系数 > 0
- 异配：度大节点倾向于连接度小节点。异配网络相关性系数 < 0
- 中性：节点间的连接与它们自身的度值无关。中性网络相关性系数 = 0
3）聚集系数
复杂网络里，一个节点的邻居节点之间连边的数目占这些邻居节点之间最大可能连边数目的比例就是节点的聚集系数。网络中所有节点聚集系数的平均值就是网络的聚集系数，它反映了网络中节点的聚集情况即网络的聚集性。
4）介数
分为节点介数和边介数。
- 节点介数：指网络中所有最短路径中经过该节点的数量占总的最短路径数量的比例
其中分母为从节点 j 到 q 的所有最短路径的数目,分子表示从节点 j 到节点 q 的 条最短路径中经过节点 i 的数目。选择介数中心性最高的部分节点进行保护。
- 边介数则指网络中所有最短路径中经过该边的数量占总的最短路径数量的比例。
介数反映了相应的节点或边在整个网络中的地位和影响力，具有重要的现实意义。例如，在社会关系网或技术网中，介数的分布情况代表了不同人员、资源和技术在相应生产关系中的作用，这对于发现和保护网络中的重要资源和技术具有很强的现实意义。
5）小世界特性
复杂网络的小世界特性是指节点规模非常大的网络(网络中的节点总数 N 非常大)，却拥有着较小的平均路径长度。也就是网络的平均路径长度 L 随网络的节点总数呈对数增长，即 L～InN。大量的实证研究显示，现实世界的网络几乎都具有小世界特性
6）无标度特性
- 网络同质性：对于度分布区间极其狭窄的随机网络和规则网络，聚集在节点平均度附近的节点非常多，说明节点具有同质性，所以可以被认为是节点度的一个特征标度。
- 网络异质性：如果一个网络的节点度服从幂律分布，那么在网络中度较小的节点占绝大部分，而度较大的节点只是极少数，此时的网络具有异质性，没有特征标度。
8、节点重要性排序方法
| 类别 | 节点重要度指标和算法 | | 基于节点邻居数量 | 度中心性、半局部中心性、ClusterRank 算法、k-壳分解 | | 基于路径 | 介数中心性、离心中心性、接近中心性、Katz 中心性、信息指标、流介数中心性、连通介数中心性、随机游走介数中心性、路由介数、子图中心性 | | 基于特征向量 | 特征向量中心性、Alpha 中心性、累计提名、PageRank 算法、LeaderRank 算法、HITs 算法、自动信息汇集算法、SALSA 算法 | | 基于节点移除和收缩 | 节点删除的最短距离法、节点删除的生成树法 、节点收缩法、残余接近中心性 |
- 定义：与网络中的其他节点相比，能够在更大程度上影响网络的结构与功能的一些特殊节点
1）基于网络局域特征的排序方法
重点考虑网络节点局部的信息，包括节点自身信息及其邻节点信息等。
需要掌握的信息相对较少，计算复杂度较低，适合用于大规模复杂网络。
该方法认为节点的度越大邻节点越多则它在网络中的影响力越大；如引文网络采用论文的被引次数来衡量论文的影响力
2）基于网络全局属性的排序方法
- 介数中心性/中介中心性 Betweenness Centrality
网络中所有的两节点间的最短路径中经过某个节点的条数越多，那么该节点就越重要。这种中心性代表了节点在网络传播之间起到的影响力
这种方法需要计算节点到网络中的其他节点的最短距离，到其他节点的最短距离之和越小，紧密度越大，则节点就越接近网络的几何中心，节点也就越重要
定义：一个节点与网络中的所有节点的最短距离之中的最大值。点的离心中心性越小，说明越接近网络的中心，节点就越重要
该方法缺点明显，不能准确反映节点的中心地位
- 特征向量中心性（Eigenvector Centrality）
网络邻接矩阵对应的最大特征值的特征向量。
用来衡量连接的质量。如果节点A连接并影响着节点B，而节点B被其他更多节点连接着，则节点A的特征向量中心性就很大
- 子图中心性 (subgraph centrality)
- ……
|
|
发表于 2022-11-27 10:27:43
