如何来测量一个网络的属性？这里提出了第一个问题，同时也给出了答案，即四种指标：

• 度分布 - p(k)
• 路径长度 - h
• 簇系数 - C
• 连通分量 - s

下面对这四种指标方法做一个详细说明。

路径 是指从图中某一个点到另外一个点的游走序列。一条路径可以循环遍历某一条边多次，例如对下图来说ACBDCDEG就是一条路径。

路径中还有一些基本概念需要介绍，包括距离、直径、平均路径长度等。

• 距离 。也叫 最短路径 ，顾名思义是指两个结点之间所有路径中最短的那条叫做这两个结点之间的距离（如果两个结点不连通，那么距离为∞）。对于有向图，两个结点之间的距离（最短路径）包括两个方向，即从 i 到 j 和从 j 到 i。且往往这两个距离不相等。
• 直径 。即一个图中任意两个结点的距离（最短路径）中最长的那个。例如上图中A-F或A到G是直径，长度为4。
• 平均路径长度 。这是针对连通图或强连通有向图来说的。具体计算方法如下图，Emax我们介绍完全图的时候提到过，它是指完全图的边数。这里分母乘2的原因是，分子在计算距离的时候每个结点间计算了两次。需要注意的是我们在计算平均路径长度时会忽略那些∞的边（例如上图A->X，否则那计算出来h没有意义）。
  

• 簇系数 是针对无向图来说。他表明了某个结点的邻居之间的连通情况，常用作社交网络测度中，例如评估某个人的朋友们之间是否也互为朋友时，可以用簇系数作为评估指标。计算公式如下图，分子为e_i，即结点 i 的邻居之间连接的边的数量；分母为k_i * (k_i - 1)/2，即 k_i 个结点之间的最大边数。
• 平均簇系数 加和除以结点数即可。
  

• 这里主要介绍如何找一个 最大连通分量 。

1. 随机从某个结点开始广度优先搜索；
2. 标记已经访问过的结点；
3. 如果所有结点都被访问了，那么这个图(连通分量)就是连通的；
4. 否则找到任一个未访问的结点重复1-3。

MSN Message是Jeff教授曾经参与过的一个项目，类似于社交网络。他以这个项目的图作为例子来说明上述四种属性在实际应用中的作用。

• 度分布 。最开始用是用一个均匀分布的坐标系来表示度分布，发现很多很多点聚集在度为0附近，效果很不好。然后用一个log坐标系（主要思想就是把较小数的尺度拉大）来表示同样的数据时，就可以清晰的看到大多数结点的度都集中在0-10之间，度超过600的点屈指可数。
  
• 簇系数 。下图表示了对应度的簇系数，这里需要说明的是可能对于一个度k，有Nk个度为k的结点，那么对应度k的簇系数Ck就是这Nk个结点的平均簇系数，用如下公式计算。
  
  可以看到MSN整张图的最终的平均簇系数为0.1140，表示的含义是平均每个结点的邻居之间约有1/10互相认识（有边相连）。
  
• 连通性 。通过上述计算连通分量的算法，可以计算得到一个图的所有连通分量及其大小（这里的大小我认为指的是结点个数）如下图。可以看到只有一个包含了99%结点数的最大连通分量，而有许多只有不到10个结点的连通分量（类似于孤立点，孤岛一样）。
  
• 路径 。这里测量了最大连通分量中，任意两个点之间的距离（最短路径），并统计了他们的数量。发现绝大多数距离都集中在5-10hops之间，并且通过计算过程发现90%的结点可以在8hops之内到达。
  
  然后作者又举了另外一个例子，PPI network。其四个属性和MSN其实差不多，那这就说明很多看似完全不着边的图应用，其实他们具有相类似的本质特征。那么此时我们就自然而然想到是不是可以构建一个模型来表示更一般的图结构，也就是从特殊到一般的思想。因此接着作者提出了一个最简单的模型—— 随机图模型 。

首先什么是随机图模型（Random Graph Model）。RGM是一个有n个结点的无向图，图中的每条边出现的概率都是p，且是独立同分布的。

这里如何来理解呢？我认为可以看作是多次伯努利试验来连接任意两个结点之间的边，每次实验都是独立同分布的，按照概率p来决定是否连接某一条边。这样经过多次实验（准确是n*(n-1)/2次），那么就会生成一个图，这个图就是随机图。

注意这样生成的图是不唯一的，因为以概率p选边，同一条边在多次实验中可能被选，也可能没有被选上。

下面就是来计算一下RGM的四种属性，看他们与MSN和PII网络的属性是否相似。

由第三节的随机图模型的结论可以得出，其簇系数非常低，但是同时平均路径长度很小。通过对比真实世界的图结构会发现，其簇系数较高，且平均路径长度较低。这表明真实世界的图具有局部结构，但同时任意两个结点之间的联系（距离）都不会太远。这里举一个简单的例子来解释上述两个属性。

假如你是一个博学多才、求学海外的青年才俊，你在国内有很多从小玩到大的伙伴，并且大家互相都认识（一个局部结构，簇系数较高）；出国之后，你又认识了许多国外友人，并且你们在一个大学，彼此也都认识（另一个局部结构）。显然你中国的朋友和国外的友人都互不认识，但是这里你就很关键了。如果没有你那么他们八辈子都不会有关系，但是有了你，他们可以通过你很快的认识彼此，相当于他们之间只隔了一个你（具有较短的路径）。这就是我们真实世界的图结构！

那么我们就自然而然地提出这样一个问题：我们是否可以构建一个图模型——具有较高簇系数的同时其平均路径长度较低呢？这样岂不是能够很好地模拟真实世界的图？

按照一般的经验，簇系数和平均路径长度这两个属性是同增长的。即如果簇系数很大，那么也会造成平均路径长度很长；相反如果簇系数很低，那么平均路径长度也很低。如下图所示。

然而通过上面随机图模型的研究，我们可以得到这样两条“经验”——（1）聚合会导致边的局部性；（2）随机会导致较短路径。因此我们可以这样得到一个”小世界图模型“。

1. 从一个低维的环状规则图开始，如下图所示，其具有较高的簇系数（平均路径长度也很高）。
   
2. 然后我们会在上述的图中进行 重新连边 。即对于每一条边，我们固定其中一个端点，以概率p决定将这条边的另一个端点移动到剩余随机的某个结点（重新连的这条边类似于你出国了），这样我们就可以在不降低簇系数的基础上，缩短了结点之间的路径长度。
   
   因此这样我们就能将两种图的优势相结合。
   
   通过改变p的值（即随机程度），我们发现当仅仅引入一点点随机性后（即较小的p）就可以使得平均路径长度明显降低，但簇系数却并没有怎么减小。这完全是我们所预期的！
   

这是本次课程的最后一个图模型，提出的主要动机是如何生成真实世界的较大规模的图结构。

首先要介绍一个新概念，叫做 自相似性 。什么意思呢？回想我们学过化学里面的物质组成，比如晶体结构，都是由一些最基本的元素或结构重复迭代而成的。也就是说很多物体和其本身的一部分是非常相似的。那么对于图也是一样，一些较大规模的图和其部分结构是类似的，或者可以说其实较大规模的图是由很多具有相似结构的小图迭代而成的。例如下图所示。

来看一个Kronecker图生成的例子，他是通过递归的调用相似的子图来生成更大的图。