卡内基梅隆大学(CMU),那些经受住时间考验的机器学习论文–第一弹:互联网拓扑规律研究

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

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

  1. Graphs over time: densification laws, shrinking diameters and possible explanations [.pdf]
    Jure Leskovec, Jon Kleinberg, Christos Faloutsos, Test of Time Award, KDD 2016
  2. Dynamic Topic Models [.pdf]
    John Lafferty, David Blei, Test of Time Award, ICML 2016
  3. 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
  4. Beyond Independent Relevance: Methods and Evaluation Metrics for Subtopic Retrieval [.pdf]
    Cheng Zhai, William Cohen, John Lafferty, Test of Time Award, SIGIR 2014
  5. Diffusion Kernels on Graphs and Other Discrete Input Spaces [.pdf]Risi Kondar and John Lafferty, Test of Time Award, ICML 2012
  6. 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
  7. On Power-Law Relationships of the Internet Topology [.pdf]Michalis Faloutsos, Petros Faloutsos and Christos Faloutsos, Test of Time Award, ACM SIGCOMM 2010
  8. 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
摘自: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库的关系做成了一张关系图, 来看看是不是也有内在的幂次法则:

来自: https://kozikow.com/2016/07/10/visualizing-relationships-between-python-packages-2/
来自: https://kozikow.com/2016/07/10/visualizing-relationships-between-python-packages-2/

完整图片请看这里: http://clustering.kozikow.com/?center=os

 

参考文献:

  1. 卡耐基梅隆大学机器学习专业 历年最佳论文

本文章属于“David 9的博客”原创,如需转载,请联系微信david9ml,或邮箱:yanchao727@gmail.com

发布者

David 9

邮箱:yanchao727@gmail.com 微信: david9ml

发表回复

您的电子邮箱地址不会被公开。 必填项已用 * 标注