PNAS前沿：你在网络中的位置如何给你带来全局影响力？

导语：

近期由中山大学胡延庆老师、西南交大纪圣塨博士等组成的研究团队在国际顶级综合性期刊《美国科学院院刊》PNAS上发表了一篇研究论文，提出了一个称为PBGA的新算法。

与传统算法不同，该算法只需要网络的局部（local）信息就能精确量化某一用户的全局（global）影响力，并找到影响力最大的群体，其时间复杂度是常数的，与网络规模无关，从而很好地解决了以上难题。

论文题目：

Local structure can identify and quantify influential global spreaders in large scale social networks

论文作者：

Yanqing Hu, Shenggong Ji, Yuliang Jin, Ling Feng, H. Eugene Stanley, and Shlomo Havlin

论文地址：

随着互联网技术的发展，微信、微博、Facebook、Twitter等社交平台的大量涌现，在线社交网络（online social network）正逐步取代传统媒体，成为信息传播的主要源头和平台。在线社交网络的研究中，一个核心的科学问题是：如何在巨大的社交网络中精确并快速地量化某一用户在整个网络中的影响力，并选取有限的初始传播用户，使得其全局传播能力最大（collective influence maximization）。

以往的研究虽然在算法设计方面取得一些成果，但一直还是面临着巨大的挑战：其一，该问题是一个NP难题；其二，今天的社交网络规模十分巨大（数十亿量级）而且时刻都在变化。由于大家一直坚信，计算在线社交网络用户的全局影响力必须用到网络的全局信息，这使得大多数的算法对于规模巨大的在线社交网络是不实用的，因为很多时候网络的全局结构数据是无法获得的，即使可以获得，其计算代价往往也难以承受。

什么是NP难题：

另一方面，基于大量的社会实证数据，耶鲁大学社会科学家们发现，个人的影响力大都会局限在其朋友的朋友的朋友之内，如抽烟、酗酒和吸食大麻等行为，也就是著名的“三度影响力”理论。这与需要全局数据的观点恰好相反，“三度影响力”理论表明，可以从个体的局部网络结构信息来衡量其在全网上的社会影响力。看起来相互矛盾的这两个结论引起了一个根本的问题：是否真的可以仅仅只根据局部的网络结构信息来准确度量个体的全局影响力？

“三度影响力”理论：

近期发表在国际顶级综合性期刊《美国科学院院刊》PNAS上的一篇研究论文给出了肯定的回答。

1. 渗流理论与信息传播

1.1 用户影响力的准确值

研究发现，社交网络中的信息传播能够被SIR族模型（susceptible-infected-susceptible family models）很好地刻画。因此，这篇文章主要研究SIR族模型。

首先，我们可以定义社交网络中的一个用户i的影响力为S(i)：

其中，g(i,s)表示用户i能够最终影响s个人的概率，N代表网络的规模，一个用户影响其邻居的概率为beta。

图1

如图1C所示，我们发现概率分布g(i,s)具有两个重要的性质：(1) g(i,s)包含两个峰。第一个峰出现在非常小的s处，而第二个峰出现在非常大的s处。(2) 这两个峰之间具有一个非常大的间隙，这就意味着我们可以用一个很小的值s*来区分这两个峰。也就是说，一个用户的一次传播的影响力要么非常大，要么非常小，如图1A所示。

通过将SIR传播过程与渗流理论相对应，我们可以把信息传播行为看成网络中的任一连边都有（1-beta）的概率被去掉。去掉连边后的网络形成了大小不同的联通集团（connected clusters），如图1B所示。

已经有理论可以证明，用户i的影响力的概率分布g(i,s)其实就是用户i所在的联通集团大小的概率分布p(i,s)。而根据渗流理论，当传播概率beta大于临界值betac时，就有一个巨大的联通集团出现（如图1B左边的大联通集团），我们记这个巨大的联通集团的大小为s^inf。这样，p(i,s)就分成了两个部分，一部分是有限的pf(i,s)，一部分是巨大的p(i,s^inf)。由于，我们可以将方程1近似为：

这里，；就是说，一个用户的影响力等于最大联通集团大小s^inf乘以这个用户在最大联通集团的概率p(i,s^inf)。对于随机网络，s^inf和p(i,s^inf)都能够通过理论被精确地推导出来，由此，随机网络的用户影响力可以精确地获得。

1.3 用户影响力的第二次近似

对于真实的在线社交网络，由于其网络结构极其复杂，我们无法获得其理论的影响力。但是，基于图1C的发现（影响力呈双峰分布），我们可以运用一个参数m来区分这两个峰。具体来说，当用户i在一次传播信息过程中，一旦其影响到的人数超过m个，我们就可以认为用户i在这次信息传播中可以传播到最大联通集团，从而提前终止这次信息传播过程（极大地减少了运算量，将O(N)减少到O(m)）。

图1

因此，更近一步，我们可以得到用户i的影响力的第二次估计：

其中，，虽然公式4中的比公式2中的p(i,s^inf)略大，但是我们可以证明，这个误差完全可以忽略不计。这是因为，如图1D所示，pf(i,s)有一个快速下降的尾巴因此只要m>=s，pf(i,s)在m之后的值就非常之小，就可以忽略不计。

利用真实的Facebook和微博的社交网络数据，如图2A所示，我们可以发现方程4得到的用户影响力估计值与方程1得到的用户影响力真实值相当逼近。并且，当m取值超过s*时，例如m取100时，方程4的相对误差可以降到0.01%（图2B）。

图2

2. PBGA算法

2.1 PBGA算法的过程

通过上述的理论支持，我们已经可以快速并精确地量化某个用户的影响力了。现在，我们运用这些理论来解决第二个问题：如何从给定的L个候选用户中选取最好的M个初始传播用户，使得其全局传播能力最大。

为此，我们提出基于渗流理论的贪心算法PBGA（percolation-based greedy algorithm）。PBGA算法是建立在原有的贪心算法之上的。具体来说，PBGA算法包含以下三个步骤：(1) 根据方程4的得到每个用户的影响力，找到影响力最大的用户v1；(2) 固定v1，找到边际影响力最大的用户v2；(3) 重复步骤(2)，每次找边际影响力最大的用户，直到找到M个用户。

2.2 PBGA算法的时间复杂度

很显然，PBGA算法的时间复杂度是与网络规模无关的，这是因为在运用方程4估计某一用户的影响力所需要的时间是常数的。

图3

而传统的贪心算法在估计某一用户的影响力所需要的时间与网络规模成正比（方程1）。如图3所示，实验结果也验证了PBGA算法具有常数项的时间复杂度，其中左图是随机网络的结果，右图是真实网络的结果。特别需要注意的是，如果用传统的贪心算法NGA在全网的Twitter或者Facebook网络中寻找影响力最大的M个用户，其所需要的时间复杂度是10^14~10^16量级的，而运用我们的PBGA算法，时间复杂度却与任何一个小网络相差无几，只需要10^5左右的时间。

2.3 PBGA算法的性能

图4

PBGA算法的性能可以由图4得到说明。可以看出PBGA算法与传统的贪心算法NGA、遗传算法GA都是最好的，所找到的M个用户的影响力都是最大的，但是NGA、GA的算法复杂度都是与网络规模成正比的。并且，在选取的用户数量M值比较小的时候，我们发现PBGA算法的结果与暴力算法（brute-force）效果完全一致。

2.4 PBGA算法的扩展能力

图5（原文图4D）

同时，我们也通过实验证明了，如图5所示，PBGA算法在某个传播概率beta0下选取的M个用户，其在其他的传播概率beta下的影响力仍然非常大。这说明，我们的算法并不需要切确地知道某次信息传播的真实传播概率beta就能够选取到影响力很高的M个用户。这在现实应用中非常关键，因为在实际应用中，我们可能需要在传播刚开始的时候就找到影响力最大的M个用户（投放广告等），这个时候传播概率beta可能还未知。

PBGA算法可以运用到任意一个社交网络中，来精确快速量化一个用户的影响力，获取影响力最大的个体或群体。举了个直观的例子，电商平台上的小商家并没有过多资金做广告，但是为了推销自己的产品，他可以通过PBGA算法寻找微博或者微信朋友中哪些人的影响力最大，即消息的转发量和阅读量最高。然后，他可以将推销信息发送给这些人，再由这些人进行转发，最终达到广而告之的目的。

而作为一种更广泛的应用，PBGA算法也可以在应用层面计算所有与传播有关的内容。例如在流感的传播中，PBGA算法可以帮助我们寻找传播能比较强的感染者进行及时阻断，降低病毒的传播。

集智QQ群｜292641157

商务合作及投稿转载｜[e-mail]

加入“没有围墙的研究所”

让苹果砸得更猛烈些吧！