网络度量

1、路径

路径是任意顶点序列，序列中每一对连续的顶点都由网络中的一条边连接。对于定向：在正确的方向上穿越的边缘。路径可以多次访问自身（顶点或边）.自我回避的路径不会相互相交。路径长度r是路径上的边数；步长用hop跳来表示；

如果使用矩阵A来表示网络，

Aij=1，存在一条边从结点j到结点i；

AikAkj =1，从j通过k到i存在一条等于2的路径；

Nij（2）表示从结点j到结点i有多少hop等于1路径可以到达

Nij（3）表示从结点j到结点i有多少hop等于2的路径可以到达

Tr-矩阵的迹：一个n*n矩阵中A的主对角线（从左上方至右下方的对角线）上各个元素的总和称为矩阵A的迹；Tr(A)；

2、最短路径（又称测地线）

复杂网络4-1

如图复杂网络4-1，A和C之间有两个最短路径连接。

A-E-B-C和A-E-D-C，得出最短路径是3；

如果结点之间是断开的，则测地线距离是无限大的；

直径：图中最大的测地线距离；

3、度分布

如果使用矩阵A来表示网络，出度是邻接矩阵中行i中各个列的和；入库是邻接矩阵中行j中各个行的和；P（k）是结点度的分布直方图，描述了分布在平均值周围的分布。

复杂网络4-2

4、图的密度

在n个节点之间可能存在的连接中

走向图 Lmax = n*(n-1)

无向图 Lmax = n*(n-1)/2

存在哪些部分？

密度=L/Lmax

在真实的网络中，L<<Lmax

例如，在12个可能的连接中，这个图有7个边，密度为7/12=0.583

当n趋于无穷大，一个密度达到：

0是一个稀疏矩阵；

一个常量是一个密度较大的图；

5、分量

如果从网络中的每个顶点到其他顶点都有一条路径，则网络是连接的；否则，他是不连通的；

连通分支：顶点的子集，从子集的每个成员到其他成员至少存在一条路径，并且网络中不存在另一个连接到子集中任何顶点的顶点；

复杂网络4-3

6、巨大分量

如果最大的分量包含了图的重要一部分，它被称为巨大分量；

7、连通分量

弱连通分支

每个节点都可以从其他节点通过任意方向的链接到达

强连通分支

组件中的每个节点都可以从组件中的每个其他节点通过以下定向链接到达；将有向图的所有的有向边替换为无向边，所得到的图称为原图的基图。如果一个有向图的基图是连通图，则有向图是弱连通图。

多个顶点的每个强连通分量至少有一个圈；

外组件：通过从特定顶点v开始的有向路径可到达的所有顶点的集合；一个强连接组件的所有成员的外组件都是相同的

内组件：有到顶点v的直接路径的所有顶点的集合；强连接组件的所有成员的内组件都是相同的

8、聚集系数

聚类系数捕获了一个给定节点的邻居相互链接的程度 。

C=2L/（Ki（Ki-1））

Ci=0 如果结点i的邻居中没有结点能互相连接；

Ci=1 如果结点i的邻居组成一个完全图。

Ci是两个结点中一个结点和另外一个结点互相链接的概率。

集聚系数

测量传递性三元组的比率 ，结点i的ki个邻居结点之间存在的边数和总的可能边数之比。

一个连接的三月组是一个包括三个结点ABC的有序集合。如，A->B,B->C

集聚系数的均值：网络的传递性=网络中三角形的数目/（网络中联通三元组的数目/3）

平均聚集系数和全局聚集系数是不同的：

在一些极端的情况下，差别可能会非常大。

复杂网络4-4

复杂网络4-5

<C>代表网络的平均聚集系数，等于各节点聚集系数平均值；

C三角=网络中三角形的数目/（网络中联通三元组的数目/3）