网络属性的度量 network properties

考虑一个图 G(V,E)有n个顶点和m条边

1. degree distribution 顶点度的分布
p(k) = |{图中度为k的顶点数}| / n
对于大多数复杂网络，研究表明这个分布一般都满足指数形式，也就是：
p(k) = c k ^ (-r)
r是一个重要的参数，对于不同的复杂网络有不同的值。



2. clustring coefficient(cc)
对于图中的一个顶点，它的cc是用来度量这个点附近顶点的连通程度。定义cc首先要定义一个顶点处的三角形，对于一个顶点v，假设(v,x)(v,y)是图中的两条边，如果(x,y)也是图中的边，那么vxy就形成了一个三角形。
假设一个顶点v处的三角形数是 triangle(v),那么
cc(v) = triangle(v) / (deg(v)(deg(v)-1) / 2)
其中deg(v)是顶点v的度
其实这个度量表示,如果x,y和v相连，那么xy相连的概率

下面的图是一个示例


对于整个图，假设图中度大于等于2的顶点是 V' = {v1,v2,...,vs}，那么图的cc定义为
cc(G) = [c(v1)+c(v2)+...+c(vs)]/s

3.eccentricity radius(半径) and diameter(直径)
顶点v的eccentricity表示v到图中其他顶点的最远距离
ecc(v) = max{d(v,u) | u in V}
其中d(u,v)表示u到v的最短路径

图的半径rad(G)和直径diam(G)定义如下
rad(G) = min{ecc(v) | v in V}
diam(G) = max{d(u,v) | u,v in V}

4.顶点的邻居
顶点的h-邻域定义为
neigh(v,h) = {u in V | d(u,v) <= h}