近年来线上社交网络（ online social network ）的规模不断扩大。比如 微信和 Facebook 等的用户 已经超过了十亿量级。在如此巨大的网络中如何精确并快速地量化某一用户在整个网络中的影响力，从而识别最有影响力的个体或群体，成为一个具有挑战性的问题。目前为止，大部分现有算法的时间复杂度至少为 O(N) 。也就是说，这些算法所花的时间随着网络规模的增大而迅速地增加。

最近， 中国科学院理论物理研究所金瑜亮副研究员（共同一作）及其合作者（中山大学胡延庆副教授、西南交通大学纪圣塨博士生、新加坡高性能计算所冯凌研究员、美国波士顿大学 Gene Stanley 教授、以色列巴依兰大学 Shlomo Havlin 教授）在国际顶级综合性期刊《美国科学院院刊》 PNAS 上发表了题为 “Local structure can identify and quantify influential global spreaders in large scale social networks” 的研究论文。该论文提出了一个称为 PBGA 的新算法，其理论时间复杂度与网络规模无关，从而解决了以上难题。

PBGA 算法的提出受到了物理学中临界现象的启发：早在 2002 年， Newman 就提出网络中的信息传播过程可以对应到一个经典的物理学问题 -- 渗流相变（ percolation transition ）。渗流相变是一个标准的临界相变。对应于临界相变中的关联长度，该研究提出了 “ 传播半径 ” 的概念。基于网络中每个节点在传播半径范围内的局域网络结构信息，可以精确地度量该节点的传播能力。传播半径只与距离临界点的距离有关，而与网络规模无关。

在微博、 Facebook 、 QQ 、 Twitter 等实际网络上的测试结果表明（见图一）， PBGA 算法的时间复杂度确实和网络规模基本无关。 基于简单外推估算， 对于全局的 Facebook 网络， PBGA 算法比经典贪心算法（ NGA ）将快约 10 ¹⁰ 倍。 该算法不仅高效，而且克服了在规模较大的网络上无法得到完整的全局信息的困难，在病毒式营销（ viral marketing ）等电子商务领域有重要应用前景。

上图 : PBGA 算法和 NGA 算法在实际网络上（每个数据点代表一个网络）时间复杂度的测试结果。

文章链接 ： http://www.pnas.org/content/early/2018/07/02/1710547115