图数据挖掘（二）：网络的常见度量属性 - orion-orion - 博客园

网络的度分布p(k)p(k)表示了一个随机选择的节点拥有度kk的概率。我们设度为kk的节点数目Nk=♯ nodes with degree kNk=♯ nodes with degree k，除以节点数量NN则可得到归一化后的概率质量分布：

我们有：∑k∈NP(k)=1∑k∈NP(k)=1。
对于下面这个网络：

其归一化后的度分布直方图可表示如下：

2.1 图的路径

图的路径(path)指一个节点序列，使得序列中的每个节点都链接到序列中的下一个节点(注意：这里的术语不同教材不一样，有的教材把这里的路径定义为漫游(walk)，而将术语“路径”保留给简单路径)。路径可以用以下方式进行表示：

一个路径可以通过经过同一条边多次而和它自身相交。如下面这个图中更多路径ABDCDEG就和自身相交。

注意，在有向图中路径只能沿着边的方向。

2.2 路径的条数

路径的条数定义为节点uu和vv之间的路径数量。我们发现邻接矩阵的幂和路径的条数之间有着关系。

• 长度 h=1h=1(这里的h可理解为跳数hops)的路径计数矩阵: 只需要考察uu和vv之间是否存在长度为11的链接，即
  H(1)uv=AuvHuv(1)=Auv
• 长度 h=2h=2的路径计数矩阵： 需要考察uu和vv之间是否存在长度为22的路径，即对满足AukAkv=1AukAkv=1的kk进行计数。
  H(2)uv=∑k=1NAukAkv=[A2]uvHuv(2)=∑k=1NAukAkv=[A2]uv
• 长度 hh的路径计数矩阵： 需要考察uu和vv之间是否存在长度为hh的路径，即对满足Auk1Ak1k2….Akh−1v=1Auk1Ak1k2….Akh−1v=1的所有⟨k1,k2,⋯,kh−1⟩⟨k1,k2,⋯,kh−1⟩序列进行计数。
  H(h)uv=[Ah]uvHuv(h)=[Ah]uv

上述结论对有向图和无向图都成立。上述定理解释了如果uu和vv之间存在最短路径，那么它的长度就是使AkuvAuvk非零的最小的kk。
进一步推论可知，在一个nn个节点的图中找到所有最短路径的一个简单方法是一个接一个地对图的邻接矩阵AA做连续的幂计算，知道第n−1n−1次，观察使得每一个元素首次变为正值的幂计算。这个思想在Folyd-Warshall最短路径算法中有着重要应用应用。

2.3 距离

图中两个节点之间的距离(distance)定义为两个点最短路径中的边数（如果两个点没有连通，距离通常定义为无穷大）。
如对下面这个图我们有BB、DD之间的距离HB,D=2HB,D=2，AA、XX之间的距离hA,X=∞hA,X=∞。

注意，在有向图中距离必须沿着边的方向。这导致有向图中的距离不具有对称性。比如下面这个图中我们就有hA,C≠hC,AhA,C≠hC,A。

我们定义两两节点之间距离的最大值为图的直径（diameter）。

2.4 平均路径长度

无向连通图（连通分量）或有向强连通图（强连通分量）的平均路径长度（average path length）定义为：

这里hijhij是节点ii到jj的距离。Emax=n(n−1)2Emax=n(n−1)2，这里2Emax2Emax中的系数22可要可不要，不同教材定义方法不一样。
在计算平均路径长度时，我们通常只计算连通节点之间的距离（也即忽略长度为“无穷”的路径）

2.5 寻找最短路径

对于无权图，我们可以由宽度优先搜索(BFS)搜寻图的最短路径。

• 从节点uu开始，将其标注为hu(u)=0hu(u)=0，并将其加入队列。
• 当队列不为空时：
  • 将队首元素vv移出队列，将其未标注的邻居加入队列并标注为hu(w)=hu(v)+1hu(w)=hu(v)+1。
  • 循环往复。

对于带权图，我们当然就得寻求Dijkstra、Bellman-Ford等算法啦,此处不再赘述.

3 聚类系数

节点ii的聚类系数(clustering coefficient)可以直观地理解为节点ii的邻居有多大比例是互相连接的。设节点ii的度为kiki，则其聚类系数CiCi定义为

这里eiei为节点ii邻居之间的边数，我们有Ci∈[0,1]Ci∈[0,1]。下面展示了聚类系数的一些实例：

图的平均聚类系数（average clustering coefficient）定义为：

4 真实世界网络的属性

接下来我们来看一MSN收发信息网络(有向)的实例。

该网络中245 million用户注册，180 million用户参与了聊天，拥有超过30 billion个回话。超过 255 billion条交互信息。
连通性

度分布

其度分布高度倾斜，平均度为14.414.4。

log-log度分布

聚类系数

这里为了方便出图，我们定义横坐标为度kk，对应的纵坐标CkCk为度为kk的节点的聚类系数CiCi的平均值，即Ck=1Nk∑i:ki=kCiCk=1Nk∑i:ki=kCi。

整个网络的平均聚类系数为0.110.11。

距离分布

其中平均路径长度为6.66.6，90%90%的节点可以在88跳之内到达。

[1] http://web.stanford.edu/class/cs224w/
[2] Easley D, Kleinberg J. Networks, crowds, and markets: Reasoning about a highly connected world[M]. Cambridge university press, 2010.
[3] Barabási A L. Network science[J]. Philosophical Transactions of the Royal Society A: Mathematical, Physical and Engineering Sciences, 2013, 371(1987): 20120375.
[4] 《图论概念梳理》

__EOF__