网络 （Network）

记录系统各个组成部分及他们之间的连接关节的复杂系统。

加权网络 （Weighted network）

加权网络中的每个链接都有自己的权重。

节点 （Node）

表示系统中的组成部分。

边 （Edge）

表示系统中节点间的交互关系。

有向网络或有向图 （Directed network）

表示一个网络中所有的链接都是有向的。

无向网络或无向图 （Undirected network）

表示一个网络中所有的链接都是无向的。

路径 （Path）

表示沿着网络中的链接行走过的路线。

路径的长度 （Length of path）

表示路径包含的链接个数。 （某些情况下要求一条路径经过每个节点不能超过一次）。

最短路径 （Shortest path）

节点$a$和节点$b$之间的最短路径是指包含链接数最少的路径。记作$d$，可以使用广度优先算法来计算出来。（最短路径不包括环和自环）

平均路径长度 （Average path length）

所有节点对之间最短路径的平均长度，用$$表示。

$$=\frac{1}{N(N-1)}\sum_{i,j=1,..,N}^{}d__{ij}$$

其中，$i$不等于$j$, $N$代表节点数，$d_{ij}$代表节点$i$和节点$j$之间的最短路径。

网络直径（Diameter）

距离最远的两个节点之间的最短距离。

或者 网络中所有最短直径的最大长度。

网络直径可以使用广度优先算法（Breadth First Search Algorithm）来计算。其算法为：

（1）从节点$a$出发，并将其标记为0；

（2）找出与节点$a$相连的节点，标记为1，然后将他们放入到一个队列里；

（3）从队列里取出为1的节点，找出与该节点相连且尚未被标记的节点，将其标记为2；

（4）依次类推，直到找到所有的标记。最大的那个标记就是就是网络直径。

欧拉路径 （Euler path）

经过每条链接恰好一次的路径。

汉密尔顿路径 （Hamiltonian path）

经过每个节点恰好一次的路径。

平均度 （Average degree）

平均度$$是网络的一个重要属性，在无向网络中，平均度被定义为：

$$ = \frac{1}{N}\sum_{i=1}^{N}k_i=\frac{2L}{N}$$

其中，$L$代表网络中总的度数，$N$代表总的节点数。 有向网络中，需要区分入度和出度：

$$=\frac{1}{N}\sum_{i=1}^{N}k^{in}$$

$$=\frac{1}{N}\sum_{i=1}^{N} k^{out}=\frac{L}{N}$$

$$=$$

其中，$k^{in}$ 代表入度, $k^{out}$ 代表出度。

度分布（Degree distribution）

表示“在网络中随机选出一个节点其度为$k$”的概率。

$$P_k=\frac{N_k}{N}$$

其中$N_k$表示有$k$个度的节点数，$N$表示节点数。

邻接矩阵 （Adjacency matrix）

常用邻接矩阵来表示网络中的链接关系，邻接矩阵内的元素的定义如下：如果存在一个链接从节点i向节点$j$，则 $A_{ij}=1$，如果无链接则其值为0， 也可用数值表示边的权重。

完全图 （Complete graph）

表示系统中两两节点之间都有链接的网络。

集聚系数 （Agglomeration coefficient）

表示一个节点的邻居节点之间彼此链接的稠密程度。

$$c_i=\frac{2L_i}{k_i\left (k_i-1 \right )}$$

$L_i$表示节点i的$K_i$个邻居之间的链接数。

连通性 （Connectivity）

如果一个网络中的所有节点对都是连通的，则称该网络是连通的。

如果网络中至少有一个节点是不连通的，则称该网络是不连通的。

桥 （Bridge）

如果网络中存在两个连通分支，只需要选择合适的位置放置一个链接，就能使网络变成连通的，这样的链接被称为桥。

一般桥是指断开之后就不在保持连通的链接。

二分网络 （Binary network）

二分网络的节点可以分成两个不相交的集合$U$和$V$，使得每个链接都连接着一个$U$中的节点和一个$V$中的节点。换句话说，如果我们把集合$U$中分节点涂成绿色，把集合$V$中的节点涂成紫色，则每个链接连接着颜色不同的两个节点。

无标度网络 （Scale-free network）

将度分布符合幂律分布的复杂网络称为无标度网络。

随机网络 （Random network）

表示在节点之间随机放置链接。包括两种模型：

（1）$N$个节点通过L条随机放置的链接彼此相连（由埃尔德什和雷尼提出）

（2）$N$个节点中，每对节点之间以概率p彼此相连（由埃德加 N. 吉尔伯特提出）

网络的最大度

网络的最大度（$K_{max}$），也被成为度分布$P_k$的自然截断，表示网络中最大枢纽节点的期望大小。

六度分割 （Six Degrees of Separation）

六度分割也叫小世界现象，根据该理论，来自世界上任何地方的两个人，都可以通过不超过6个相识关系连接起来。

生成任意度分布的网络

（1）度保持的网络随机化算法

随机选择两条序列，如果这两条序列交换之后不会产生多重连接，则进行交换。因此，连接交换涉及的4个节点的度在交换过程中不会改变，如此一来，枢纽节点依然是枢纽节点，度很小的节点依然很小，但通过链接交换得到的网络就变成随机连接的了。

（2）隐参数模型

从$N$个孤立的节点开始，为每个节点分配一个隐参数。 所生成的网络的性质将依赖于隐参数序列的选择。

隐参数模型和度保持的网络随机化算法可以用来消除配置模型的自环和多重链接，从而生成无标度网络。

介数中心度 （betweenness Centrality）

是基于最短路径对网络图中心性的衡量标准之一。针对全连接网络图，其中任意两个节点均至少存在一个最短路径，在无权重网络图中该最短路径是路径包含边的数量求和，加权网络图中该最短路径则是路径包含边的权重求和。每个节点的介数中心性即为这些最短路径穿过该节点的次数。

直观上来说，betweenness反映了节点v作为“桥梁”的重要程度

偏好连接 （Preference connection）

在真实网络中，新加入的节点更倾向于与链接数高的节点相连。

中性网络 （Neutral network）

随机网络就是中性网络

同配网络 （Co distribution network）

网络中的枢纽节点趋向于彼此相连，而非小度节点， 同时小度节点倾向于连接其他小度节点。 其极端表现为同配网络，即度为k的节点只连接到度为$k$的节点上。

异配网络 （Heterogeneous network）

网络中的枢纽节点彼此不相连，而是连接到小度节点。 因此网络表现为中心辐射特征。

度相关性 （Degree correlation）

描述相连节点的度之间的关系。

网络的鲁棒性 （Robustness of network）

网路节点的故障对于网络的完整性的影响。

如果一个系统在内部或者外部发生错误时仍能保持其基本功能，那么这个系统就是具有鲁棒性。在网络中，鲁棒性就是指系统丢失一些节点和链接后仍能执行其基本功能的能力。

韧性：

如果一个系统可以改变自身的运行模式来适应内部和外部的错误，且仍能执行其功能，那么这个系统就具有韧性，因此，韧性是一个要求系统改变核心活动的动力学属性。

冗余：系统中存在并行的组件和功能，且能在需要时相互替代丢失的组件和功能。网络中大部分节点对之间存在多条独立路径，因此网络在信息导航方面有相当大的冗余。

冗余和韧性是与鲁棒性密切相关的两个概念。

社区 （Community）

是网络中局部紧密连接的子图，这一断言依赖于两个假设：

1. 每个社区对应一个连通子图，（连通性假设）
2. 社区内的节点更倾向于连接到同一社区内的其他节点，而非其他社区的节点。 （密度假设）

社区识别本文介绍的有两种算法：Louvain 算法和 Infomap 算法。

模块度 (Modularity)

指与随机连接方式的偏离，可以用于度量划分社区的优劣。所以模块度允许我们判断一种社区划分是否强于另一种。

$$M_c = \frac{L_c}{L}-\left ( \frac{k_c}{2L} \right )^2$$

$L_c$是社区内$C_c$的链接数， $k_c$是该社区的节点的度的总和。

重叠社区 (Overlapping communities)

每个社区的成员都属于多个其他社区，构成了有嵌套和重叠的复杂网络。

摘自《巴拉巴西网络科学》[美] 艾伯特-拉斯洛·巴拉巴西（Albert-László Barabási）著，沈华伟 黄俊铭 译