博文
复杂网络观察：为什么网络会加速增长？
精选
|||
许多实际的网络具有加速增长特征。通过对万维网、因特网、科学家合作网、引文网络等的实证研究发现，在观测的生长期内，这些网络的平均度是随时间增加的，即边的数量比节点的数量增长更快，这种现象一般被称为加速增长[1]。过去十年间，已有不少文献对加速增长网络的拓扑性质（主要是度分布）进行了模拟、解析或数值的分析[2-5]，但对网络为何会加速增长这一问题还较少受到关注。本篇博文中，我将根据自己的理解对这一问题进行粗浅的探讨，作为博文大赛的参赛题目，希望得到论坛中各位前辈的指点和批评。
网络规模的增长通常会表现在两个方面：一是节点数量的增加，二是边数量的增加。当有新的个体进入网络时，网络的节点数量会增加，同时至少会有一条边加入网络中。如果每个节点进入网络的同时，伴随有m条边连接到网络中（无论是优先连接还是随机连接），那么网络的边增长速度与节点增长速度是相同的。但实际观测中，多数网络边的增长速度比节点增长速度更快，如果将节点数量理解为网络的演化时刻t，则每个时刻网络边增加的数量可以表示为m(t)，m(t)是一个增函数，它可能（近似）具有线性、指数或对数等多种形式。
需要注意的是，每个时刻增加的m(t)条边并不一定都是连接新加入节点的。更普遍的情况是，在节点增加的同时，网络中的“老”节点之间也在产生新的连接。例如对于因特网，一个新设备通常是用一条线路而不是多条线路接入网络的。网络边数量较节点数量增加的快，更多的原因是网络中既有的设备之间为了增加吞吐量（或提高速度）在增加新的线路。这种现象在合作网络中存在的更普遍，例如科学家论文合作网络，相当规模的论文是由已发表过论文的作者完成的，这种情况下网络甚至没有增加节点，而只是增加了边（或提高了边的权值）。
根据上述分析，我们可以初步归纳出，网络中边的增加主要有两种形式：一是连接新加入的节点，二是是在老节点之间建立新的连接。如果认同这一点，我们是否可以这样理解网络加速增长现象：在网络“年轻”时，边增加的驱动力主要是新节点的加入；而随着网络年龄的增长，越来越多的边会在老节点之间产生。老节点之间产生新边的原因可能是为了缩短节点间距离，也可能是为了增加网络的容量，这会依网络类型不同而有所不同。
那么，如果解释上述现象产生的原因呢？在我去年完成的一篇论文中[6]，我用随机效用理论对其进行了解释。在这篇论文中我对几个不同规模城市的公交网络增长速度进行了横向比较，从已有的文献中按城市规模从小到大分别取了廊坊、扬州、济宁、大连、杭州、南京、北京和上海八个城市的公交网络数据，这些网络的节点度是按城市规模增加的。也就是说，规模越大的城市公交网络增长速度越快，而规模越小的城市公交网络增长速度越慢。如果我们把这些数据看作是同一个城市的，那么可以认为，在城市发展早期公交网络增长速度慢，而随着城市规模扩大，公交网络会加速增长。我相信这种规律在大多数城市的公交网络中都是存在的，但城市公交历史数据不太好收集，所以只能说是推测。
随机效用是经济学中一个概念，因为在学交通规划中的离散选择模型时接触过这一理论，所以就套用在这里（可能并不是太合适，我不熟悉物理学中是否有类似的理论）。这种理论认为，消费者选择某件消费品的概率取决于该消费品带给消费者的效用（即对其需求的满足程度），效用越大的消费品被选择的概率也越大。如果我们认为网络是自组织的，那么可以尝试把网络自身理解为一个消费者，把网络演化过程中边的增加理解为一次消费行为，而把边连接新节点还是老节点理解为两种消费品。
在网络增加边的一次“消费行为”中，是选择新节点连接还是选择老节点连接，取决于这二者中的哪个会带给网络自身更大的“效用”。对于公交网络而言，当网络发展早期，新辟公交线路的主要目的是覆盖公交服务盲区，那么连接新站点对实现这一目的的效用显然比旧站点更大，因此线路倾向于连接更多的新站点，节点相对增加较快；而随着网络发展，服务盲区会越来越少，新辟线路的主要目的会演变为减少既有站点间的换乘次数，提高各站点间交通的便利程度，因此线路倾向于在更多的既有站点间连接，网络节点增速降低，而边的增速提高，网络整体呈现加速增长的趋势。
我们可以把上边的分析方法推广到因特网和科研合作网络。对于因特网而言，早期会更倾向于接入那些没联网的设备；而随着网络成熟，已有用户对速度或能力的追求将会变为主流，这样更多的连线会在老节点之间产生。对于科研合作网络，当新出现一个研究方向时，发表论文的“门槛”可能较低，也就是说新节点进入网络的“成本”（成本可以理解为负效用）较低；但随着这一方向研究的不断深入，新研究者发表论文的“成本”会越来越高，而“老”研究者由于有了更多的积累，发表论文的“成本”会越来越低，这样网络节点增加会减速，网络呈现边加速生长趋势。就像复杂网络领域，十年前发表一篇论文，可能只需要对一个实际网络的数据做做统计分析，谈谈它是scale-free或small-world的就可以了；而现在呢，不作出点数学模型都不好意思去投稿：）剩下的都是“硬骨头”了，像我一样的新研究者要发一篇论文，难度不知提高了多少倍。
在我的那篇论文中，对网络增长速度的讨论就到此为止了，当时我认为自组织网络对全局效用最大化的追求可能是驱动网络加速增长的内在机制之一。后来我又对此问题进行了断断续续的思考（因为网络研究是副业，一直没能投入太多精力去做，今年希望改观，把杂事扔一些，专心做网络：），试图构造一个网络自组织演化模型再现加速网络的过程。
目前的想法是用经济学中的边际效用递减理论（又是经济学，因为对物理实在不熟，我估计物理学中肯定会有一些类似的理论，希望哪位前辈能给点提示：）。这一理论的一个著名的直观解释是：当你很饿时，吃第一个馒头时可能会狼吞虎咽，吃第二个时就慢条斯理了…………等你吃到第十个的时候，估计快要呕了…………也就是说，同样是一个馒头，带给你的“效用”是递减的。
在我构造的网络模型中，首先会生成足够数量的零度节点，然后为每个节点构造一个随度递减的效用函数。在每一个演化步长中增加1条边，这条边在选择两个端点时，会遵循不同的规则：一头按效用函数优先连接（效用越大，被连接的概率越大），另一头按度优先连接（即BA模型的连接方式），这样经过调整（主要是调节点的边际效用函数形式，如果边际效用恒定，则等同于BA模型），能够再现网络加速生长的过程。不过现在我还没办法对它的度分布进行解析，正在尝试用史定华老师的马尔可夫链方法[3]做数值分析。不过实在太难了，一直没什么进展。准备这个难关攻克了就投稿了（实在攻克不了就先投个仿真模型的：）。
到这呢，我自己感觉是初步解释了加速生长现象的原因（可能不对，欢迎批评），但是我使用的递减效用函数依旧是个外生因素，我能感觉到网络加速肯定有更深层次的原因，但限于水平，暂时还找不出来。
可能有的朋友会说：你折腾这个玩意有什么实际意义啊？我倒真觉得研究网络加速现象实际意义还挺大的，至少对交通网络是如此。目前我能想到的应用有两个：一是用于预测，二是用于优化（这也是多数复杂网络理论应用的着力点吧）。
首先是预测，还是以我比较熟悉的公交网络为例。两年前，石家庄交通研究中心的一个朋友给我发邮件，她当时在做石家庄远期的轨道交通规划，要进行轨道与公交的联合客流分配。但遇到一个小小难题：十年后的轨道交通网络是他们规划出来的，但十年后石家庄的公交网络会是什么样子的呢？我当时给她的一个解决方案是：公交网络往往会有比较明显的层次结构，即市中心会有一个大的集散点向外围辐射多条线路，到近郊又会形成新的集散点，进一步向外辐射……，这是公交的骨干，然后在一些大的客流点上会有支线进行连接、加密等等。依照这种规律，人工铺画一个远期的公交网络，虽然不会很准，但至少不会很离谱。当时提出这个方案，是基于我对很多城市公交网络结构的直观认识，因为我一直教交通方面的课，看过的城市公交线网构图比较多，发现很多城市公交网络的确存在这种规律（或称模式）。那时还没接触复杂网络的东西，现在想想其实就是典型的无标度网络。如果我们能够提出一个接近实用的公交网络演化模型，把现有的网络作为一个演化中间状态输入进去，让它去自然生长出符合实际的公交网络来，那将是多么美妙的一件事情！当然现有文献中提出的公交网络演化模型有不少了，但对空间限制、客流需求的影响等因素考虑的还是不足，远不能实用化，这也是我打算进一步去做的一些工作。另外，我看到论坛里有些朋友是搞链路预测的，不知道在该领域是否已经有了这类研究成果。因为精力实在有限，链路预测的文献基本没看过，但愿我不是坐井观天，有时间一定恶补。
其次是优化，对于公交网络这类技术网络，很明显不是完全自组织的，“他组织”的成分会更多。此时我们可能会关注这样一个问题：如何设定合理的网络增长速度，才能实现网络的全局效用最大化？解决这一问题对于优化或引导网络结构合理发展具有实际意义。例如，在城市公交建设投资水平一定的前提下，规划者应如何（通过技术或经济手段等）控制合理的公交网络增长速度，才能实现网络覆盖率与平均换乘次数的综合优化？又比如在制订科学基金资助政策的过程中，在基金总量有限的前提下，是应优先使更多的研究者能受到资助？还是优先加大对已受资助高水平研究者的资助力度？这实际上也是一个根据不同学科特点及发展水平合理配置科研资源，引导科研网络规模合理增长的问题。
扯得有点远了，不过这种加速增长的现象在社会领域的确是非常普遍的存在的。我们现在会经常听到“外延式增长”和“内涵式增长”这两个词。我有时会想：网络早期靠增加节点规模实现的增长可否理解为“外延式增长”？而成熟网络靠增加内部连边的方式实现的增长可否理解为“内涵式增长”呢？
参考文献：
[1] SN Dorogovtsev, JFF Mendes. Evolution of networks, Adv. Phys, 2002
[2] MJ Gagen, JS Mattick. Accelerating, hyperaccelerating, and decelerating networks, Phys. Rev. E, 2005
[3] DH Shi, QH Chen, LM Liu. Markov chain-based numerical method for degree distributions of growing networks, Phys. Rev. E, 2005
[4] DMD Smith, JP Onnela, NS Jones. Master-equation analysis of accelerating networks, Phys. Rev. E, 2009
[5] ZZ Zhang, LJ Fang, SG Zhou, JH Guan. Effects of accelerating growth on the evolution of weighted complex networks, Physica A, 2009
[6] 闫小勇, 王明生. 增长速度对合作网络参与者节点度分布的影响, 物理学报, 2010
[1] SN Dorogovtsev, JFF Mendes. Evolution of networks, Adv. Phys, 2002
[2] MJ Gagen, JS Mattick. Accelerating, hyperaccelerating, and decelerating networks, Phys. Rev. E, 2005
[3] DH Shi, QH Chen, LM Liu. Markov chain-based numerical method for degree distributions of growing networks, Phys. Rev. E, 2005
[4] DMD Smith, JP Onnela, NS Jones. Master-equation analysis of accelerating networks, Phys. Rev. E, 2009
[5] ZZ Zhang, LJ Fang, SG Zhou, JH Guan. Effects of accelerating growth on the evolution of weighted complex networks, Physica A, 2009
[6] 闫小勇, 王明生. 增长速度对合作网络参与者节点度分布的影响, 物理学报, 2010
复杂网络研究
https://blog.sciencenet.cn/blog-404069-313897.html
上一篇：从C#到Python (pdf整理版)
下一篇：GISDK典型程序实例之：线数据重采样
