Press "Enter" to skip to content

图网络基本属性

本站内容均来自兴趣收集,如不慎侵害的您的相关权益,请留言告知,我们将尽快删除.谢谢.

如何描述一个网络

 

Degree Distribution

 

P(k): 随机选择的节点, 度为k的的概率分布, 使用直方图来描述

其中 表示度为k的节点数, 比如上图中,度为1的节点数有6, 所有节点数为10, 所以

 

Path Length

 

Path: path是指每个节点连接下一个节点的序列,其中,一个path能够重复多次相同的边, : ACBDCDEG

Distance: 连接节点对最少数量的边,称为两个节点间的distance,如下图,其中 , 若图中两节点无连接,或中间连接断开,则distance为无穷,在有向图中,distance的计算应该考虑两个节点间的方向,如下图 ,不是对称的:

Diameter 在graph中,所有节点对当中最长distance; Average path length 针对graph来说, average path length计算公式如下:

 

 

其中 是node i到node j的distance, 是指图最多可存在的边数:

 

Cluster coefficient

 

cluster coefficient 对于无向图,用来描述节点i与他的邻居的链接情况, 其中节点i的度为 ,clustering coefficient计算公式如下:

 

 

如下图, 图的node i的cluster coefficient计算如下:

 

Average clustering coefficient:

 

 

 

 

 

 

 

 

avg. clustering: C= (1+1/3+1/3+1)/8=1/3

 

Connected components

 

Connectivity 图当中最大的可连接的component:能够通过path链接的任意两个几点的最大的集合; 如何找到图当中的connect components,从图中随机节点开始,按广度优先策略遍历,标记遍历过的节点,如果,所有的节点均被遍历,那幺这个未connected component, 否则从未遍历的节点中随机开始,重复广度优先策略遍历;

描述实际中的图:MSN Messenger

 

msn一个月的相关的数据,如下:

Degree Distribution

x坐标log之后:

可见大部分的节点degress在个位数。

 

Clustering

 

将所有的节点的k与c绘制在如下图中,整个graph的avg culstering coefficient约为0.1140

Connected Components

Diameter

 

msn的graph中平均path length为6.6, 90% 的节点能够触及在8个链接后触及到另一节点;

图的核心属性如何使用?

 

这些graph的属性是意外的还是在我们本身预料之中?

PPI Network

Random Graph Model

 

Simplest Model of Graph

 

ER Random Graphs 两个变种:

 

1. : n个节点的无向图,其中每一条边是概率为p的独立同分布;

 

2. : n个节点的无向图,其中m个边均匀随机生成;

 

需要说明的是,n, p 无法唯一地的决定graph,如下图,相同的n,p下, 我们有不同的图:

Degree Distribution of

 

假定 表示度为k在所有节点中的占比, 则

 

 

很明显的binomial distribution, 所以均值、方差为:

 

 

 

标准差率为: ,当图无限大的时候,则标准差为0, 所有的节点都为

 

Clustering Coefficient of

 

已知 边为概率为p的独立同步分, 其中 , 故

 

Expansion

 

定义 : 如果一个graph的任意的子集S,子集中边的条数大于alpha乘以子集或者graph去除子集之后的节点数量, Expansion通常用来衡量图的鲁棒性:

 

这张ppt没理解清楚,

中,n*p为常数,所以avg deg k也为常数:

Connected Components

 

,Largest CC中节点占图中所有节点的比例

Random Graph Model vs. MSN

 

在Random Graph Model 和实际的MNS的4个核心属性对比:

真实网络和Random Graph类似吗 ?

Giant Connected component: yes
Average path length: yes
Clustering Coefficient: No
Degree Distribution: No

The Small-World Model–能同时保证high clustering且短path的图吗?

回顾下前面MSN network,clustering coef为0.11, 而 的clustering coef为 。 另外一个例子, IMDB数据集、Electrical power grid, Network of nerons中:

其中h:average shortest path length, C: avg clustering coefficient, random,是保证相同avg degree,相同节点下的图的情况。

下图左边:高clustering coefficient: 朋友的朋友是我的朋友;

Small-World同时保证high cluster and low diameter; 如下图,从high clustering/high diameter, 到low clustering/low diameter, 增加随机性(p变大): 即随机的将一条边的另一个端点连接到任意较远的节点上,这样可以保持high clustering,low diameter;

下图中的p区域保证保证high clustering 和low path length:

Kronecker Graph Model: Generating large realistic graphs

 

递归的graph的生成: Self-similarity

Kronecker Produce 是一种生成self-similar矩阵的方法:

Kronecker Product 定义如下:

举个例子:


构建一个 的初始概率矩阵;
计算k阶Kronecker
遍历k阶矩阵,按 构建edge(u, v)链接

如上图最后, 需要模拟 次,耗时太高, 是否有更高效方法(利用其递归结构)?

真实网络与Kronecker网络很相似, 右上角为其初始矩阵:

Be First to Comment

发表评论

电子邮件地址不会被公开。 必填项已用*标注