学习论文
Maximum matchings in scale-free networks with identical degree distribution - By Huan Li, Zhongzhi Zhang
学习笔记
背景知识
Valiant proved that enumerating perfect matchings in general graphs is formidable, it is #P-complete even in bipartite graph.
在图中枚举完美匹配的数量是很困难的，即使在二分图上也是一个#P-complete问题
度分布P(k)：网络中度值为k的所有节点与总节点数量的分数，如果一个网络中有n个节点，且其中nk个节点的度值为k，那么 P(k) = nk/n。度分布就是P(k)的整体分布。
无标度网络（Scale-free Networks）：度分布（即对复杂网络中节点度数的总体描述）服从或者接近幂律分布的复杂网络。
无标度网络中某节点与另外k个节点相连接（度数为𝑘）的概率是：P(k) ~ k-γ，其中γ是一个通常位于2和3之间的参数，但偶尔也会在这个区间之外。
无标度网络的特点：
Hubs (枢纽节点)： 存在极少数拥有海量连接的节点（如 Google, Amazon，或者社交网络里的明星）。
长尾效应： 绝大多数节点只有寥寥几个连接。
For example, in the Barabási–Albert (BA) scale-free network, a perfect matching is almost sure not to exist, and the size of a maximum matching is much less than half the number of vertices. The same phenomenon was also observed in a lot of real scale-free networks, which are far from being perfectly matched as the BA network.
在BA无标度网络模型中，特殊的“顶点度数不均匀分布”的特性，使得完美匹配几乎必然不存在。（我的直观理解：每一个hub顶点都是类似“星形”结构，一个hub顶点与许多个度数很低的顶点（甚至是悬挂点）邻接。这就导致了取一条关联hub的边加入匹配之后，其他大量度数低的顶点就无法被M饱和了）
本文核心议题：无标度网络中的度分布（服从幂律分布）不能决定网络中最大匹配的特性！
Preliminaries
Graph and operation
设G = (V(G), E(G)) 有N个顶点，E条边, V(G) 是顶点集 {v1, v2, ··· , vN } ，E(G) 是边集
边的细分（Subdividing an edge）：将边e = {u, v} ∈ E(G)用长度为2的路 u–w–v 替代的过程，w 是一个新加的顶点。
细分图（subdivision graph）：对E(G)中的每一条边做边的细分，得到的图B(G)称为G的细分图。
线图（line graph）：G的线图L(G)的点集就是G的边集E(G)，L(G)中的两个点相邻，当且仅当这两个点在G中对应的两条边存在公共顶点。
细分线图（subdivided-line graph）：G的细分线图Γ(G)是G的细分图的线图，换言之，Γ(G) = L(B(G))。Γ称为细分线图操作。
g-迭代细分线图（g-iterated subdivided-line graph） (g ≥ 1) Γg(G) 是在G上迭代地使用g次细分线图操作得到的图。
Structural properties of a graph
距离（distance）：两个顶点之间的距离是连接它们的最短路的长度（即边的数目）
网络的平均距离（average distance of the network）：网络中所有顶点对(u, v)的距离的算术平均。
网络的直径（diameter of the network）：网络中所有顶点对(u, v)的距离的最大值。
小世界网络（ small-world network）：如果一个网络的平均距离随顶点数量呈对数增长，或者增长得更慢，则称该网络具有小世界特性。
幂律分布（power law distribution）：如果随机变量X的概率密度函数P(x)满足形式 P(x) ~ x-γ ，称X服从幂律分布
无标度网络（Scale-free Networks）：如果一个网络的度分布满足（至少在渐近意义上满足）幂律分布 P(d) ~ d-γ，则称该网络为无标度网络。
累积度分布函数（Cumulative Degree Distribution）：Pcum(d) = Σd'≥dP(d')
如果一个无标度网络的度分布 P(d) ~ d-γ ，则它的累计度分布函数也是幂律形式：Pcum(d) ~ d-(γ-1)
衡量度相关性（Degree Correlations）的方式
平均邻居度knn(d)：度数为d的顶点的最近邻居顶点的平均度数。
同配（assortative）：当knn(d)是d的递增函数时，称网络是同配的。这意味着网络中，顶点倾向于和具有相近或更大度数的顶点相连。
异配（disassortative）：当knn(d)是d的递减函数时，称网络是异配的。这意味着网络中，度数较大的顶点倾向于和度数较小的顶点相连。
如果knn(d)是常量，网络无相关性（uncorrelated）
皮尔逊相关系数（Pearson correlation coefficient）：
ji , ki 是第i条边的两个端点的度数, i = 1, 2, ··· , E. 皮尔逊相关系数r(G)满足−1 ≤ r(G) ≤ 1，如果r(G) = 0，G无相关性；如果r(G) < 0，G是异配的；如果 r(G) > 0，G是同配的。
分形网络（fractal network）：若一个网络 G 具有有限的分形维数，则称其为分形网络；否则，称其为非分形网络。
分形维数的计算方式：盒覆盖法（box-covering approach）
称一个顶点集B是一个大小为lB的盒子，如果B中任意一对顶点之间的距离小于lB ，我们用大小为lB的盒子覆盖G中的顶点，并用NB表示覆盖G中所有顶点所需的最小盒子数。如果NB满足NB ~ lB-dB (0 < dB < ∞)，则G是分形的，G的分形维数是dB
粗粒化 (Coarse-graining) 的过程：用尺寸为 lB 的盒子把网络盖住，每一个盒子里的所有顶点，全部合并成一个新顶点，如果原来的两个盒子里有顶点相连，那么这两个新顶点之间就建立连接。
网络的自相似性（Self-similarity）是指在不同盒子尺寸 lB 的粗粒化（coarse-graining）下，或者在固定 lB 的迭代粗粒化操作下，网络的度分布保持尺度不变性。
分形网络一定是自相似的，但自相似网络未必是分形的。
Matchings in a graph
匹配（Matching）：图G的边集的子集M ⊆ E(G)称为一个匹配，如果M中的任意两条边在G中不存在公共的顶点。M中边的数量称为M的大小。和M中的边关联的顶点称为M饱和点，否则称为M非饱和点。
最大匹配（Maximum matching）：设M是图G的一个匹配，如果G中不存在匹配M'，使得|M'| > |M|，称M是G的最大匹配。最大匹配的边数称为G的边独立数或匹配数。
完美匹配（perfect matching）：饱和了G中所有顶点的匹配称为G的一个完美匹配。显然完美匹配一定是最大匹配。我们用 ψ(G) 表示G中完美匹配的数目。
Lemma 2.1. 设连通图 G 有 N 个顶点，E 条边（E是偶数），G的线图的完美匹配数量ψ(L(G))满足： ψ(L(G)) ≥ 2E−N+1, 其中，当G中所有顶点的度数小于等于3时，等号成立。
设Ge是G的定向图（即对G的每一条无向边定一个方向成为有向边后的图），那么Ge的斜对称邻接矩阵（skew adjacency matrix）A(Ge)定义如下：
设C是一个偶回路，称C是在Ge中奇（偶）定向的，如果在C上沿一个方向（顺时针/逆时针）行走时，同向边的数目是奇（偶）数。同样的，称路P是在Ge中奇（偶）定向的，如果在P上从起点行走到终点时，同向边的数目是奇（偶）数。
称回路C是一个nice cycle，如果G \ C中存在一个完美匹配。G \ C表示G删去C上的所有点及关联边后的导出子图。
如果G中的每一个nice cycle在Ge中都是奇定向的，则称Ge是一个 Pfaffian定向图。
Lemma 2.2. 设Ge是G的一个 Pfaffian定向图，则：
对于一个顶点数N充分大的网络G来说，定义完美匹配的熵如下：
在介绍完基础知识后，作者构造了两个拥有相同度数序列的无标度网络，一个是分形且大世界的，另一个是非分形且小世界的。它们证明了这两个网络的最大匹配的特性是迥异的。
Maximum matchings in a fractal and scale-free network
本节研究一个分形无标度网络的最大匹配的大小和数目
构造方式
Definition 3.1. 设Fg = (V(Fg ), E(Fg )), g ≥ 1 是一个g次迭代过程后的分形无标度网络，V(Fg)和 E(Fg) 分别是顶点集和边集。构造方式如下：
g = 1 时，F1是一个有着4个顶点和4条边的四边形。
g > 1 时，Fg是由Fg-1的每一条边在右手处（right-hand side）用一个四边形代替产生的。
图中的v1, v2, v3, v4正是4个枢纽节点Hubs
用Ng和Eg分别代表Fg的顶点数和边数，可以计算得到：
Proposition 3.3. 网络Fg的累积度分布函数服从幂律分布：Pcum(d) ~ d-2
推导思路如下（通过研究每一轮迭代的特征）：
上述定理证明了网络Fg是一个无标度网络
定理3.4说明，网络Fg是一个大世界网络（因为平均距离随顶点数量呈平方根级增长，比对数级来得快）
Proposition 3.5. 网络Fg是一个分形维数为2的分形网络。
下面的定理给出了网络Fg的平均邻居度
下面的定理给出了网络Fg的皮尔逊相关系数，也能反映出Fg的异配性。
最大匹配的大小
上述定理中构建了三个量：ag表示Fg \ {v1, v2}的最大匹配大小，bg表示Fg \ {v1}的最大匹配大小，cg表示Fg本身的最大匹配大小。然后可以构建出递推公式。
下面是ag+1的递推公式构建过程
图中虚线框起的hub点是被删去的/构建匹配的时候没有饱和的部分。显然ag+1 只有上述4种情形，得到的答案相同。
下面是bg+1的递推公式构建过程
显然bg+1 有上述8种情形，得到2种不同的答案，取较大值作为最大匹配的大小。
下面是cg+1的递推公式构建过程
显然cg+1 有上述16种情形，得到3种不同的答案，取最大值作为最大匹配的大小。
最后解方程组得到解析解。
最大匹配的数目
这一小节中定义了三个量，θg是Fg的最大匹配的数目，也就是我们要求的。Φg是Fg \ {v1, v2}的最大匹配数目，φg是Fg \ {v1}的最大匹配数目。这种定义方式和上面一个小节求解最大匹配大小的时候有异曲同工之妙。
下面是证明过程：
证明过程很有意思。通过定理3.8中求解出来的ag，bg，cg的解析解，代入后可以发现，事实上，推导过程中的每一类情况都是一种最大匹配。这样的话，运用乘法原理就能轻松得到θg，Φg，φg的递推公式。
上述定理表明，Fg 的最大匹配数目可以在O(ln Ng )的时间复杂度下求解出来。
至此，作者将他们构造出来的第一个网络的特性研究完毕了。
Pfaffian orientation and perfect matchings of a non-fractal scale-free network
本节研究一个非分形图Hg，为了控制变量，需要保证Hg和Fg的度数序列相同。
构造方式
依然是迭代构造方式，构造方法和Fg也是非常相似。
图示如下：
可以看到，Fg和Hg的构造方式差别仅仅在于，迭代过程中，Fg是每一条边变成四边形的对角线，而Hg是每一条边变成四边形的一条边。
因此很显然，Hg与Fg有着相同的度数序列。
然而，Hg的分形维数是无限的，因此Hg是非分形图。
此外，我们还能类似的给出Hg的平均距离，平均邻居度，皮尔逊相关系数等等。
上述定理表明，Hg的平均距离随着顶点数量Ng对数级增长，因此是小世界的。
上述定理4.4 和 4.5 说明，网络Hg无相关性。
Pfaffian 定向图
按照如下方式做定向：
首先，用数学归纳法，对g做归纳，可以证明网络Hg存在完美匹配。
其次，可以证明v1和v2之间的任意一条nice path，在上述定向图中都是奇定向的。如下引理所述：
其中，SHg (u1, u2, ··· , um)描述了一类“只通过u1, u2, ··· , um这些指定的hub顶点和其他度数较低的非hub顶点，不通过任何其他没有指定的hub顶点的path/cycle集合”，形式化定义如下：
最后用数学归纳法，对g做归纳，证明上述定向图就是一个Pfaffian 定向图：
完美匹配的数目
上述结论是通过复杂的行列式解法求解得出的。
结论
通过分析可以知道，对于两个度数序列相同的无标度网络Fg和Hg，前者没有完美匹配，后者的完美匹配数目非常大。因此对于无标度网络而言，度分布并不能充分决定最大匹配的性质，而需要在结构细节上面加以细致的分析。