卡内基梅隆大学（CMU），那些经受住时间考验的机器学习论文--第一弹：互联网拓扑规律研究

这一期，接着上一期，开始我们的卡内基梅隆大学（CMU）机器学习论文之旅。

CMU果然是机器学习的牛叉大学（拥有专门的机器学习专业系）。David 9翻看所有获得“Test of Time Award”（经得住时间考验奖）的论文，没有一篇论文是应用型，全部是奠基类的基础研究文章，不得不赞叹才疏学浅啊。先来获奖看一下列表：

Graphs over time: densification laws, shrinking diameters and possible explanations [.pdf]
Jure Leskovec, Jon Kleinberg, Christos Faloutsos, Test of Time Award, KDD 2016
Dynamic Topic Models [.pdf]
John Lafferty, David Blei, Test of Time Award, ICML 2016
Realistic, Mathematically Tractable Graph Generation and Evolution, Using Krinecker Multiplication [.pdf]Jure Leskovec, Deepayan Chakrabarti, Jon M. Kleinberg, Christos Faloutsos, Test of Time Award, ECML/PKDD 2015
Beyond Independent Relevance: Methods and Evaluation Metrics for Subtopic Retrieval [.pdf]
Cheng Zhai, William Cohen, John Lafferty, Test of Time Award, SIGIR 2014
Diffusion Kernels on Graphs and Other Discrete Input Spaces [.pdf]Risi Kondar and John Lafferty, Test of Time Award, ICML 2012
Conditional Random Fields: Probabilistic Models for Segmenting and Labeling Sequence Data [.pdf]
John Lafferty, Andrew McCallum, and Fernando C. N. Pereira, Test of Time Award, ICML 2011
On Power-Law Relationships of the Internet Topology [.pdf]Michalis Faloutsos, Petros Faloutsos and Christos Faloutsos, Test of Time Award, ACM SIGCOMM 2010
Integration of heterogeneous databases without common domains using queries based on textual similarity [.pdf]William Cohen, Test of Time Award, ACM SIGMOD, 2008

David 9发现一个规律，里面几乎所有论文都和“图”有关系啊，看来CMU对Graph研究很热衷啊？

论文1是研究社交网络、信息图网络的生长规律; 论文2是“动态主题模型”, 和“概率图模型”脱不了关系; 论文3与论文1是一个作者, 可见在图上的研究造诣; 论文4总算和图没有太大关系; 论文5研究也是基于图论的核方法; 论文6是大名顶顶的CRF奠基论文, 也是基于图论; 论文7, 研究互联网拓扑 ; 论文8, 似乎和graph没有太大关系.

看到这里，大家一定知道我们这一弹要将的互联网拓扑规律研究就是这篇论文：

On Power-Law Relationships of the Internet Topology [.pdf]Michalis Faloutsos, Petros Faloutsos and Christos Faloutsos, Test of Time Award, ACM SIGCOMM 2010

没错这是1999年的论文，那时正是互联网爆发的时代，用图论去研究互联网拓扑的工作应该不在少数，所以我打算从当时的研究状态谈起。

我们都知道英特网的前身是ARPANET。

摘自：http://www.cs.cmu.edu/~christos/PUBLICATIONS/sigcomm99.pdf

上图（a）是一个物理上的视图，（b）是一个相互作用图。因特网最简单直观的认识是可以看做一个大网络，里面有许多子网，每个子网都可以叫做一个domain域。对于图论的数学，当时已经有了一定的基础，包括无向图、点、边以及点的出度入度等概念。

但是对于Internet这样真实崛起的网络，在当时90年代是很新的课题，激发了许多学者对这样网络的兴趣。比如对于真实的网络研究，1994年-1995年对于Internet域之间关系的研究发现， 75%的节点出度是小于等于2的，可见当时的网络状况和我们现在的很不一样，当时的互相引用关系与现在相比非常弱。而对于网络生成模型的研究，当时已经有一些研究通过调整一组参数, 来控制人工网络生成后的拓扑, 使得拓扑表现形式不同.

在回到本论文的重头戏, 网络中的幂次法则. 最有名的应该是帕累托分布（Pareto distributions）了, 大家常常听到的幂次分布, 长尾定律, 有许多内在联系.

probability_density_function_of_pareto_distribution-svg — 来自维基百科

这是幂次分布的概率密度图, 概率密度大的地方仅仅局限于一小部分区间, 这就是常人理解的二八定律, 长尾定律的一般含义. 大部分资源总是分配给少数个体.

但是幂次分布如何在互联网拓扑中体现呢? 论文中发现3个法则:

1. 排名幂次法则(rank exponent):

对于一个节点v的出度 $d_v$ , 和节点v的出度排名 $r_v$ , 成幂次关系, 系数为R, 即:

$d_v \propto r_v^R$

其中, 出度排名 $r_v$ 是指把节点按照出度从大到小排名的排名值, 显然出度很多的节点在网络中是很少的(一些门户网站比如hao123), 大多数网站都在长尾那里徘徊. R的实验值大约在-0.81, -0.82, -0.74这些值左右.

2. 出度幂次法则(outdegree exponent):

对于节点的出度频率 $f_d$ , 和节点出度d, 成幂次关系, 系数为O, 即:

$f_d \propto d^O$

其中, 出度频率 $f_d$ 是指出度为d的节点的个数. O的实验值大约在-2.15, -2.16, -2.2这些值左右. 因此有意思的是, 不仅仅在出度排名与出度上网络节点符合幂次法则, 而且在出度与出度频率上, 也符合幂次法则.

类比到大自然方方面面, 都存在这样的幂次法则, 我们说富人与穷人就符合幂次法则. 不仅仅是人数上, 富人只占有很少一部分人群, 而且, 在资源分配上, 极少的那一部分富人, 占有的资源也是占到很大一部分资源, 而庞大的穷人群体占有的是极少的资源.

3. 特征幂次法则(eigen exponent):

对于一个图的的特征值 $\lambda_i$ , 和图的特征排名i, 成幂次关系, 系数为 $\epsilon$ , 即:

$\lambda_i \propto i^\epsilon$

其中, $\epsilon$ 的实验值大约在-0.47, -0.50, -0.48这些值左右. 所有这里有意思的是, 所有经过研究的网络用特征总结来说, 也符合幂次法则. 这些特征包括, 网络的直径, 网络的边数, 网络的连接元素, 等等. 只有那些奇葩的网络只是属于少部分, 大部分网络都是大同小异, 特征值相近的.

因此特征幂次法则也适用于现在互联网的发展规律, 那些占主导作用的网络比如Facebook, Google, amazon, 京东, 微信, 淘宝, 等等, 都是屈指可数的小部分网站, 非常庞大的网站是那些不知名的网站, 博客小站的博主, 做微商的个体经营者, 等等. 但是, 巨大资源都聚集在那些屈指可数的知名网站中. 可见, 这篇论文获得”经得住时间考验奖”是名副其实的.

记得以前有人还把所有python库的关系做成了一张关系图, 来看看是不是也有内在的幂次法则: