度分布(Degree Distribution)

  • Properties of Networks and Random Graph Models - 图1：在一个图中任意一个顶点的度取值为k的概率，即Properties of Networks and Random Graph Models - 图2，很容易

image.png

网络直径(Network Diameter)

  • 直径：即图中任意两个结点间最大的距离

  • 平均路径：针对连通图或强连通图而言，Properties of Networks and Random Graph Models - 图4

    • h即点i到点j的距离
    • Emax即边的最大数量，n(n-1)/2
    • 只考虑连通的点对

      聚类系数(Clustering Coefficient)

  • 针对无向图而言

  • 就是为了表明一个结点i的邻居连通程度的系数
  • Properties of Networks and Random Graph Models - 图5，其中e是结点i邻居之间边的条数，k为结点i的度
  • 显然聚类系数的取值介于[0,1]
  • 一个图的平均聚类系数Properties of Networks and Random Graph Models - 图6

image.png

连通度

  • 即最大连通分量的大小

image.png

Random Graph Model

  • 两个变量：
    • Properties of Networks and Random Graph Models - 图9即给定n个顶点，每条边存在概率为p的无向图。通过确定n以及p不能确定一个唯一的图，这很简单啦
    • Properties of Networks and Random Graph Models - 图10即给定n个顶点以及m条边，这些边均匀随机地选择依附的顶点
  • 度分布Properties of Networks and Random Graph Models - 图11（即计算图中有多少比例的结点度是k）：
    • 它服从二项分布

image.png

  • 上式中第一部分是从n-1个结点中取出k的结点的所有组合方法数量（二项式系数），再乘以这些结点与当前结点相连的概率，以及其余结点与当前结点不相连的概率。其实就是二项分布的标准形式。细想其实比较好理解，因为P(k)是指任意一个顶点度为k的概率，所以只要分析一个点就好了
  • 从二项分布的参数可以看出，只要图的顶点数够多，其顶点度的分布也就越稳定，方差带来的影响也相应减小，因为Properties of Networks and Random Graph Models - 图13是收敛的

image.png

  • 聚类系数Properties of Networks and Random Graph Models - 图15(图中每个结点期望的聚类系数):
    • 回忆一下，聚类系数计算公式是Properties of Networks and Random Graph Models - 图16，其中e是结点i邻居之间边的条数，k为结点i的度
    • 那么我们先求Properties of Networks and Random Graph Models - 图17，很显然Properties of Networks and Random Graph Models - 图18，原因不说也应该知道。。
    • 然后我们惊喜地发现：

image.png

  • 所以，如果我们按照一定的连通度生成节点数越来越大的图，聚类系数就会趋于0
    • ExpansionProperties of Networks and Random Graph Models - 图20：若对于任意一个结点子集，分割出这个子集损失的边数量大于系数Properties of Networks and Random Graph Models - 图21

  • edges leaving S的意思实际上就是图中S与V\S连接着的边集

image.png

  • 如何理解Properties of Networks and Random Graph Models - 图23？其实就是一个扩张系数。我们从结点集中分割出一个子集，从这个子集连接着另一个补集的边可以确定下一次扩张新加入的点。这样只要是一个连通图，任意点集经过若干次扩张一定可以可以将点集变为所有结点的集合。每次扩张都可以算出一个比例，Properties of Networks and Random Graph Models - 图24就对应所有扩张中最小的比例值。那么借由Properties of Networks and Random Graph Models - 图25，就可以计算出由一对结点延伸出的最长路径
  • 所以，图的直径，或者说最长路径一定是对数级的，至于下面这个公式是怎么推出来的，我不知道。。

image.png

  • 所以，Gnp的路径长度为Properties of Networks and Random Graph Models - 图27
    • 模型的问题：
  • 度分布与真实网络不同
  • 现实中最大连通分量规模（p(n-1)与规模大小的函数）不会呈阶段型（当p(n-1)>1时具有最大连通分量）
  • 没有社群结构，因为聚类系数太低

    Small World Model

  • 是否存在具有高聚类系数同时直径较短的图？

image.png

  • 若最短路径大小为Properties of Networks and Random Graph Models - 图29，但聚类系数太低；若网络具有社团结构，那样直径又会太大
  • 模型要点：
    • 首先建立一个低维数栅格模型（圆环状），使其具有很高的聚类系数
    • 随后进行重连线的操作，即随机去除模型中的边并与远处的点进行连接。对于每个边，它具有p的概率将另一个节点设为图中任何一个随机结点

image.png

  • 只需稍稍增加概率p，若干捷径就会打通，图的直径就会迅速变小，但聚类系数基本不受影响

image.png

  • 该模型与真实世界更为相似，但它的度分布仍然有误

    Kronecker Graph Model

  • 构造递归的生成图，网络的整体的形状与它的一部分相似。克罗内克图模型是一种生成自我相似的矩阵的模型。

image.png

  • 克罗内克图（Kronecker graph）就是对初始邻接矩阵K_1不断与自己进行克罗内克內积得到的图。

image.png
image.png

  • 随机克罗内克图（Stochastic Kronecker Graph）
    • 第一步：创建N_1 x N_1的可能性矩阵O_1
    • 第二步：计算O_1进行k次克罗内克內积的结果O_k
    • 第三步：对于O中任意的任意元素p_uv，以可能性p_uv决定矩阵K_k中是否存在该条边

image.png

  • 快速克罗内克图生成算法：每次投入一条边，递归地决定投入在什么位置。如果重复则重新插入

image.png

  • 跟真实世界最接近的模型