师说 | 网络名师博客群 of 电子科技大学

每周工作回顾3--复杂网络上的最优接触过程

周涛 | 2009-01-20 | 科学网 | 395次阅读

忙来忙去，好久都没有写工作回顾了，这次写一个最近的工作——复杂网络上的最优接触过程。

这个文章虽然是2008年底发表出来的，但是折腾的时间很长，实际上07年初就开始做了。在复杂网络的同步问题上，2005年Adilson和昌松兄发表了一篇很著名的Physical Review E的文章（这篇文章截至08年底已经超过100次，是05年>2500篇PRE论文引用第一，是一篇影响力甚至超过Nature论文的文章），讲述的是在网络同步的问题中，如果没有节点受到单个周围节点影响的强度反比于该节点所连接的节点数（也就是该节点的度），则同步能力会比各个点对之间的影响力都相同的情况好很多。我和明姐受这个文章启发，做了一些工作。我06年到埔项参加DDAP4的会议，在食堂遇到Adilson，和他聊到这个问题。我问他为什么想到这个做法呢，他说因为耦合关系的拉普拉斯矩阵本来就应该归一化（我猜想昌松兄应该是提供了最原始的想法，从两者的出身来看，昌松兄一直搞非线性，对耦合映像格子应该非常熟悉），所以这样就归一化了。至于有没有解析的研究呢（在一定约束条件下证明恰好是成反比的时候最优），那个时候还没有。我曾经想过能否有一些解析方面的进展，但是特征值的问题让解析变得困难。

有趣的是，06年的时候，我的两位师兄，王文旭和殷传洋，和我在Physical Letters A上面写了一篇小论文，大致的意思是局部搜索的时候，如果只知道邻点的度，要让交通吞吐量最大，搜索某个邻居的概率应该和这个邻居的度成反比。那篇论文只有数值试验的结果，没有解析。后来在谢彦波的帮助下，王文旭得到了一个唯象的解析，我们又一起写了一篇Physical Review E的论文，两篇论文加起来引用也有六七十次，还不错。实际上，更早的时候，严刚和我做过一个基于最短路的信息包传递的路由问题，我们发现如果把传输的代价定义为和节点度的某个幂次的话，当这个幂指数正好等于1的时候，系统的交通流量最大。这个文章也是06年发表在Physical Review E的，08年一年的引用就超过了30次，我估计在2010年引用就会过100，在圈内也还算不太差的工作。我曾经尝试利用图论里面广度树上路径数的近似算法给出一个解析，但是太过复杂，最终也是没有成功。

这些问题其实都有一个共同的内涵，就是当处理某种网络上的“流的动力学”（dynamics of a kind of flow）的时候，似乎倾向于度小的节点“效果”更好。我曾经幻想一种让人愉快的解析解释，但是一直未能如愿。那么，什么是最简单的“流的动力学”呢，应该是传播！我在06年的时候和刘建国、柏文洁一起为Physical Review E写过一篇每个节点传染能力相同的SI模型的文章，但是那个时候主要的重点是SI模型的平均场问题，没有感觉到该工作和上面那些问题的联系。后来我们组来了一位做本科毕业设计的学生，叫杨锐，很聪明，于是叫他跟踪那篇SI模型的论文，系统研究节点传染能力相同的各类传播问题。本科毕业前，我们一大坨人一起，以杨锐打头，写了一篇Physical Letters A的论文。这个文章研究的是SIS模型，发表在07年初，但是我们做这个工作的时候是06年。我那个时候比较智障，对于接触过程（contact process）不了解，不知道所谓的“节点传染能力一致的SIS模型”和接触过程数学上是等价了。后来胡斑比先生六十寿诞的时候，听到H. Hong还是D. Kim做了一个关于异质网络上接触过程的平均场理论，才知道了这个概念。插一句，H. Hong的工作实际上是comment 06年Claudio的一篇Physical Review Letters，在那篇文章中Claudio认为无标度网络中的接触过程不能作平均场近似。前两个月曾邀请Claudio过来呆过一两天，还聊到此事，他很佩服H. Hong的数学功底（H. Hong是一位漂亮而且酒量惊人的女子）。知道了这个以后，回去就和杨锐讨论，决定试试如果只知道邻居节点的度，而希望接触过程能够感染尽可能多的节点，应该怎么办呢？当然，杨锐立刻就可以做数值实验，让接触概率和邻居节点的度的某个幂次成正比，我们发现，当幂指数为-1的时候（和度成反比），接触过程传染面最广。如果假设传染概率和度的幂次成正比，在远离临界点的地方（那些地方可以用平均场近似），可以解析推导出最优的指数正好在-1。这个结论让我十分兴奋，可以说是围绕我的兴趣和目标的第一步吧，看样子选取一个简单的动力学确实是重要的。后来，谢彦波把结论变得更强，如果接触概率是一个只含有邻居度k的函数，f(k)，那么通过泛函变分的方法，可以证明当f(k)反比于k的时候，传染面最广。