集智俱乐部

网络与几何的纠缠

2017-06-12  本文已影响43人  Jake_张江

导语

我们通过感官认识我们周边的世界。于是,眼睛及其视觉系统便识别出来我们所栖居的三维世界。尽管科学试图通过抽象的逻辑思维来超越感官,从而创造出了线性代数、拓扑、分形等概念和学科,但是当我们面对全新而且复杂的概念的时候,我们仍然忍不住要回过头来去抓住几何空间这根救命稻草。

复杂网络的研究正遵循了这样一种发展规律。网络概念的提出最早可以追溯到大数学家欧拉,他为了解决著名的哥尼斯堡七桥问题而将哥尼斯堡当地的地图抽象成一堆节点和连线。从此,人们便可以仅仅关心节点彼此之间的连接关系,而忘掉位置和大小。然而,近年来的复杂网络发展却渐渐浮现出了一种相反的趋势,人们开始热衷于重新找回网络背后的隐含空间,从而站在全新的视角来解决问题。

几何决定网络

例如,为了理解复杂网络中小世界现象的起源,Kleinberg将社交网络重新嵌入到了二维空间中,并发现大部分连边都是局部的联系,而少数的长程连边则是为了让整个网络能够更好地连通,从而让网络上的信息能够有效地到达目的地。这种被称为可导航(Navigation)的性质不仅解释了具有高聚集性和小世界现象,而且还能够很好地解释连边概率随距离呈现幂律衰减的模式。

图1 在二维网格网络上添加长程连边形成小世界网络

进一步,希腊的年轻科学家Papadoplov发现,我们的社交网络所嵌入的空间不是欧几里德空间,而是一个神秘的双曲空间。于是,无标度和小世界现象成为了双曲几何的自然结果。

图2 在双曲空间中的复杂网络

笔者的研究工作发现,欧氏空间加上适当的节点生长方式就能够解释为什么大量的网络都具备的加速生长规律,即连边通常会比节点更快地生长,而节点属性的多样性会比节点更慢地生长。

图3 运用“匹配生长”模型生成的空间网络

 网络塑造空间

另一方面,网络还可以改变空间本身,使得其上的动力学过程更加简单明了。例如,现代交通系统就打破了地理空间的阻隔,让世界更好地链接成为整体。我们可以将一条条航线理解为一个个超时空虫洞,从而让整个地球扭曲成为一个更加紧密的几何体。于是,地球表面上疾病的传播过程就变得更加清晰透明:因为病毒的携带者会坐飞机顺着航空网络遍布全球各地。这样纽约和北京的距离会由于航空流量的巨大而比北京和新西兰的距离更短。

图4

在地理空间中,疾病传播的传播过程。A为全球航空网,B为传染病在全球爆发之后的地理分布情况;C、D、E为疾病在全球传播的情况,横坐标为城市与疾病爆发点的地理距离,纵坐标为该地首次爆发传染病的时间。我们看到,疾病传播在地理空间中没有任何规律性。

图5

在全球航空网络所形成的空间中疾病的传播情况。A、B中疾病发源地为中心的节点,其它地点则按照从发源地到该点的网络空间中的距离而排序,B中红色点为疾病在不同时间的爆发点。C、D、E展示了感染时间与网络空间中到发源地距离之间的关系。我们看到相比较上图,在网络空间中,疾病的传播更有规律性。

网络不仅可以重塑真实空间,还可能直接从无到有地创造出全新的空间,这便使得人们可以重新获得对整个系统的全新认识。例如,我们可以通过大量用户在这些站点上的跳转行为塑造出一个全新的空间,使得任意两个节点在空间上的距离都尽可能地等于用户在这两个站点之间的平均跳转步数。

图6利用印第安纳大学师生上网数据绘制的网络空间图 图7利用CNNIC采集的上万人的上网数据绘制的中国互联网空间图,D为整个图像,A为中心区域的放大图,B、C、E、F为不同分类(综合类、电子商务类、问答类,以及娱乐类)网站的定位图

在这个全新的空间中,我们可以非常清楚地找到每个网站在整个互联网生态系统中的定位。比如,Google、百度这样的搜索引擎虽然流量不一定很大,但是却位于整个图形的中心;不同的空间区域聚集了不同功能的网站。

 网络与词向量

最近,深度学习成为了科学界的新宠。人们将大量的数据扔进了神经网络中,以期待它能够自己学习到数据中蕴藏的模式。然而,目前的深度学习处理的数据大多仅仅局限在图像和文本,但却不包括网络。这是因为,网络的本质在于节点之间的连接信息,而这种信息很难被结构化为标准的数据。怎么办呢?

答案就在于空间。只要我们将网络嵌入到了一个几何空间中,我们就可以将每个节点的坐标视作该节点的特征,从而放到神经网络中进行学习和训练。那么,针对一个一般性的网络,我们又如何计算每一个节点的空间坐标呢?

答案就在于DeepWalk算法。它首先在网络上释放大量的随机游走粒子,这些粒子在给定的时间内就会走出一个节点构成的序列。我们不妨将节点视作单词,于是它们生成的序列就构成了句子,我们便可以得到一种节点由序列构成的“语言”。接下来,我们就可以应用强大的Word2Vec算法,计算出每个节点“单词”的向量表示,也就是空间坐标了。

图8DeepWalk算法示意图,红色节点表示从任意一点开始的随机游走

这种节点嵌入的算法可以很好地反映节点之间的连接信息,或者我们可以将DeepWalk算法得到的节点坐标视作对每个节点连接信息的编码。那些连接结构上相似的节点会在空间中彼此靠近。

图9利用DeepWalk算法将“跆拳道俱乐部”网络(左图)做二维空间的嵌入(右图)

有了从结构到空间的这种转换,我们便可以利用普通的聚类和分类算法来对复杂网络进行处理。

 神经网络的几何特征

既然任何复杂网络都可以转化为一组空间坐标,而显然神经网络本身也是一种网络,那么我们自然可以得到神经网络的几何表征。这样,每个神经元就变成了空间中的一个点,整个网络就形成了空间中的一片云,不同的网络对应了不同形态的云。有了这样的对应,我们便可以开一系列脑洞了。

例如,我们可以将整个神经网络的训练过程可视化为云的飘移过程;我们可以通过分析云的几何特征来分析不同神经网络的运行特性;我们可以通过对云进行分类,从而区分出分类良好的神经网络;我们甚至还可以将这片云(图片)喂给一个神经网络从而生成一个神经网络(图片),这样我们的神经网络就可以自己生成自己了。

 参考文献和课程

几何空间与小世界:

J.Kleiberg: Navigation on small world, Nature 406, 845,2000

双曲空间中的网络生长模型:

Papadopoulos F, Kitsak M, Serrano M Á, et al. Popularity versus similarity in growing networks[J]. Nature, 2012, 489(7417): 537-540.

匹配生长模型:

Jiang Zhang, Xintong Li, Xinran Wang, Wen-xu Wang, Lingfei Wu: Scaling behaviours in the growth of networked systems and their geometric origins; SCIENTIFIC REPORTS 2015, 5: 9767

粘性纽扣与社区生长:http://mp.weixin.qq.com/s/tOTO6Bs8PZAUlgUhCqo81g

关于疾病传播与全球航空网

Brockmann D, Helbing D. The hidden geometry of complex, network-driven contagion phenomena[J]. Science, 2013, 342(6164): 1337-1342.

互联网背后的几何空间:

Peiteng Shi,Xiaohan Huang,Jun Wang, Jiang Zhang: A Geometric Representation of Collective Attention Flows; PLoS ONE 10(9): e0136243, 2015

XiaoDan Lou, Yong Li, Wei Wei Gu, J. Zhang, The Atlas of Chinese World Wide Web Ecosystem Shaped by the Collective Attention Flows. PLoS One, 2016, 11(11): e0165240

Word2Vec算法:

T. Miklov: Efficient Estimation of Word Representations in Vector Space, 2013

谷伟伟的“浅谈Word2Vec“课程

DeepWalk算法:

Bryan Perozzi, Rami Al-Rfou', Steven Skiena. DeepWalk: online learning of social representations. KDD 2014.

 

集智QQ群|292641157

集智俱乐部

英文名: Swarma Club ,

成立于 2008 年 ,

是一个从事学术研究、

享受科学乐趣的探索者的团体 。

力图搭建一个中国的

“ 没有围墙的研究所 ”。

搜索公众号:集智俱乐部

让苹果砸得更猛烈些吧!

长按识别二维码,关注集智俱乐部,

让我们离科学探索更近一步。

上一篇下一篇

猜你喜欢

热点阅读