谁是社交网络最优传播者
■本报记者 袁一雪
如果一个人的想法可以通过社交网络影响到他的朋友、朋友的朋友、朋友的朋友的朋友，而他们之间可能是互不相识的陌生人，那么他们每个人的思想是否有交叉？一个人的思想会在多大范围影响他人？影响的程度如何？这些问题的答案，或许都可以从物理学的理论中找寻到。
近日，一篇题为《局部算法可识别和量化大规模社交网络的最优传播者》的文章发表在《美国国家科学院院刊》（PNAS）上。研究人员提出了一种名为PBGA的计算机算法，如果将此算法应用在大型社交网络中，可以精确并快速地量化某一用户在整个网络中的影响力。
当物理理论遇到计算机编程
PBGA算法的全称是Percolation-Based Greedy Algorithm，中文翻译为“基于渗流相变的贪心算法”。“贪心算法”与“渗流相变”分别是计算机领域与物理学科中的两个概念。
“贪心算法”是计算机学科中一个经典算法。这种算法在对问题求解时，总是作出在当前看来是最好的选择，即不从整体最优上加以考虑，它所做出的是在某种意义上的局部最优解。
而“渗流”的概念在物理学中是解释流体在多孔介质内的运动规律。“渗流本质上就是传播。就好比蓄满水的大坝，当大坝上出现裂缝时，水会从各个细小的裂缝中流出，当细小的裂缝足够多也足够密集后，会形成大的洞口，水也会汇集在一起流出。就好比一个人发了一条消息，然后由朋友们转发，最终形成网络影响力。”论文的通讯作者、中山大学数据科学与计算机学院副教授胡延庆在接受《中国科学报》记者采访时解释道。
其实，社交网络系统、神经网络系统等与传统统计物理研究对象相比有些不一样，其系统内元素之间的作用关系与作用强度不由物理距离唯一确定。所以物理学概念似乎与社交网络风牛马不相及。
但在2002年，密歇根大学的Mark Newman教授提出了网络中的信息传播过程可以与物理学中的“渗流相变”相对应的观点。但如何利用“渗流相变”中的概念来帮助设计高效的优化传播算法，跨领域交叉后又会碰撞出怎样的火花，Newman并没有给出答案。
“我们用3年的时间与新加坡冯凌研究员、西南交大纪圣塨博士等合作，研究出了基于‘渗流相变’理论的PBGA算法。”论文另一位作者、中科院理论物理所副研究员金瑜亮告诉《中国科学报》记者。
在传播半径内计算网络影响力
PBGA算法的出现颠覆了以前受限于网络规模和查找量级的传统算法。
“举个简单例子，如果传统算法要计算某个人在拥有几千或几万个用户的校园网中传播影响力需要1个小时，那么当计算其在拥有几亿用户微博上的时候可能就需要1万个小时。而且随着网络规模越大，所需时间越长。”金瑜亮表示，“而PBGA算法则不受网络规模的影响，不论是校园网还是像类似微博和Facebook等大型社交网站，PBGA算法所需时间都差不多。”
论文中，研究人员也在微博、Facebook、QQ、Twitter等局域社交网络进行了实测，结果表明PBGA算法的时间复杂度确实和网络规模基本无关。基于简单外推估算，对于全球的Facebook网络，PBGA算法比经典贪心算法（NGA）将快约100亿倍。
事实上，随着互联网的发展，社交网络几乎成为人们交流必不可少的一部分。但大型的社交网络使用人数较多，且数据时刻都在变化，“所以原则上我们很难基于整个网络数据提出算法。”金瑜亮说，“但是我们可以根据某一个人所发消息后，他的朋友阅读和转发量以及朋友的朋友阅读和转发量，即某人的传播半径内的信息，来评估其对整个网络的影响力。”研究人员发现在实际网络中的传播半径往往在三层左右（即朋友的朋友的朋友）。
那么，了解某个人的网络影响力有何好处呢？
胡延庆向记者举了一个直观的例子：比如电商平台上的小商家并没有过多资金做广告，但是为了推销自己的产品，他可以通过PBGA算法寻找微博或者微信朋友中哪些人的影响力最大，即消息的转发量和阅读量最高。然后，他将推销信息发送给这些人，再由这些人进行转发，同样可以达到广而告之的目的。而作为一种更广泛的应用，PBGA算法可以在应用层面计算与传播有关的内容，“比如如果它应用在流感的传播中，可以帮助我们寻找传播能力比较强的感染者进行阻断。”
物理学理论更广阔的应用
物理学与计算机的关系源远流长，除了渗流理论，计算机的“模拟退火算法”也来源于物理学的理论。它是一种基于概率的算法，其出发点是物理中玻璃物质的退火过程。由于该算法具有较好的全局优化性能，现在已经在工程中得到了广泛应用。
而物理学除了与计算机科学“纠缠不休”，有时与社会学也会产生关系。金瑜亮表示，在这次论文中他们就提出从物理学和数学角度思考社会学的问题，“论文中提到的‘传播半径’的概念或许可以解释社会学中的‘三度理论’”。
2007年，美国哈佛大学教授Nicholas A. Christakis和加州大学圣地亚哥分校教授James H. Fowler提出，人们在社交网络上的很多社会学属性遵循了“三度影响力原则”，也就是说人们的行为、态度、情绪都会在我们所在的社会网络中三度分隔之内泛起涟漪，即一个人可以影响他的朋友（一度）、朋友的朋友（二度）和朋友的朋友的朋友（三度）。同时，每个人也受到这三度分隔之内的人的影响。如果超过三度分隔，这种影响力就基本可以忽略。
“在互联网中，每个人都会受到来自微博或微信朋友圈的影响，但这种影响是局部的还是全局性的，这点需要思考。而且人的意志和思考能力在这个社交网络盛行的时代是否还具有独立性，也值得思考。”金瑜亮表示。
《中国科学报》 (2018-07-20 第3版 科普)
