导语

常用的网络过滤模型，都基于全局的特征，而忽略了局部的相互作用。然而真实世界中的网络，邻近的节点间往往存在着更强的相互作用，因此需要有更好的算法既能保留复杂网络的核心洞见，又能化繁为简实现过滤。一篇近期发表于Nature Communications 的文章提出一种方法，使得二者兼具，下面将对此进行详细解读。

论文题目：

A Pólya urn approach to information filtering in complex networks

论文地址：

https://www.nature.com/articles/s41467-019-08667-3

数据压缩的目的是用更少的比特来尽可能不失真地重现原有的信息。对于以有向加权图为数据结构的复杂网络，要做的是从所有的边中找出一个子集，即网络的骨架（backbone）。从网络中的边中过滤出关键的边，在数据量增加的时代，对于各个用网络建模的应用场景，都是必不可少的。使用过滤后的相对更稀疏的网络，可以用其结合线性模型来做预测，由于使用的特征变少了，预测模型会变得更加不容易死记硬背（过拟合）。

常用的网络过滤模型，都基于全局的特征，而忽略了局部的相互作用，当网络中的两个节点存在正反馈的时候，网络中节点的入度出度的分布就会出现异质性。这时如果按照一个统一的标准来确定那些边该属于网络的backbone，这样选出的网络骨架就无法反映网络原有的性质。

在2月14号NC中的一篇方法学文章中，作者提出了一种全新的网络过滤算法，考虑了节点间的局部作用，在多种网络上都有较好的表现，且新的方法可以通过改变参数，等效于之前的方法，因此是之前方法的扩展（generalization）。

Polya的罐子模型

介绍新方法之前，先看看之前的一种方法，名叫Disparity filter（差异性过滤），该方法先随机生成一个模拟的Null model，再通过对真实网络与模拟网络的边进行统计检验，通过P值，来确定留下来哪些边，该方法由此保证了对不同度数的节点都会考虑。

Disparity filter:

https://en.wikipedia.org/wiki/Disparity_filter_algorithm_of_weighted_network

而Polya的罐子，是统计中一个常见的模型。假设罐子里有黑白两种颜色的球，随机取出一个黑球或白球,然后从罐子外另找和这个球颜色一样的球a个,伴随原来取出的球一起放回去，再随机抽取新的球。

该图展示了原先有2黑1红的polya罐子在参数a取1时系统演化不同状态的概率

而在网络上，对于一条边，也可以按照Polya的罐子模型，去构建一个Null model。

假设对于度数为k，边的权数之和为w的一个节点，这个点的某一条权重为w边边是否存在，可以根据Polya的罐子来确定其存在的概率，这里上面的a越大，正反馈带来的自我增强就越明显，当a=1时，模型等价于之前提到的Disparity filter，下面的公式描述了该边出现的权重。

新过滤算法有何优势？

以美国客运飞行网络为例

下面的图，展示了参数a的不同将如何影响网络的过滤的效果。这里待过滤的网络是美国不同机场间的飞行网络，网络中边的权重，代表了这两个机场之间的飞行旅客数。

好的过滤要能保持网络中核心的洞见。在这个例子中，是美国的客运飞行主要集中在几个大城市之间，例如美国最大的两个城市纽约和洛杉矶，同时东部的城市之间有所联系。

如果将a定为0.4，得到了图a；将a定为1.0，得到了图b；随着参数a的增加，过滤后的网络变得更加稀疏，过滤后的边更少，上图中子图a按照polya的罐子模型，局部相互作用的影响被赋予了相对小的权值，在子图b中，新模型等价于Disparity filter，过滤后的网络最突出的是美国旧金山和洛杉矶到纽约的航线；图d将a定为了4.5，这导致保留的都是只存在极强的正反馈的节点，例如图中的西雅图和阿拉斯加的那条线。

而将a定为2.6这个多次实验后找到的最优值时，能够用最少的边从网络中得出类似的结论，如图c，这里主要保留了洛杉矶和纽约这两个美国最大城市的航线，这是不是很意外？图过滤算法可以通过微调一个值，做到提取网络中按常识看最重要的边。

从这个每个人都可以根据常识找到正确答案的例子中，可以看出新的方法可以通过对a这个参数的调整，做到根据网络中正相关出现的程度，进行相应的边过滤，从而用最少的边代表网络，例如上图的c，说明了美国最重要的航线就是洛杉矶和纽约这两个人口最多的城市之间的那条。

该文还在国际贸易网络，弗罗里达的生态网络，以及中学生之间的社交网络上进行了实验，并和之前的方法进行了对比，在补充材料中，还在美国各州之间的贸易网络上，用过滤后的网络进行了预测。不同于网络上的数据降维，例如通过在网络上的随机行走进行network embedding，本文的方法基于统计物理，更具有解释性，也更具鲁棒性，适用于多种场景。

该文的另一个启发是polya的罐子这个模型，对于存在局部自我增强的系统，不论是正反馈（a > 0 )，还是负反馈（0>a>-1)，都可以用该模型来模拟动力学演化。

ps.

该文在官网上开放下载，且列出了该文投稿后三个审稿人提出的意见，以及作者是如何回应的全过程，对于该如何去写一篇方法型的文章，这份审核记录值得细读，如果想学学如何写方法型文章，这样的对话值得一看。