如何描述一个网络
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