中山大学数据科学与计算机学院在大数据及社交网络研究方面取得重要进展

luyuanhong

中山大学数据科学与计算机学院在大数据及社交网络研究方面取得重要进展

来源：中山大学数据科学与计算机学院

近日以我校为第一完成单位，数据科学与计算机学院胡延庆副教授与其合作者包括纪圣
塨博士生、金瑜亮研究员、冯凌研究员等在国际顶级综合性期刊《PNAS》上发表了题为
“Local structure can identify and quantify influential global spreaders in
large scale social networks”的长达57页研究论文（包括附录），从理论上完整给出
了在线社交网络上信息传播的引爆点（tipping point）。为在线社交网络上的广告推送、
社会感知、谣言控制等构建了理论基础，设计了对应的低代价、高效率并易于执行的算
法。该成果为我院在大数据与交叉学科研究方面取得的重要标志性成果之一。

随着互联网技术的发展，微信、微博等社交平台的大量涌现，在线社交网络正以其强大
的传播功能逐步取代传统媒体。社交媒体不仅是社会思想文化的集散地，也是舆论、谣
言等信息的放大器。研究在线社交网络上信息传播的规律，对社会感知、谣言控制、引
导与干预网络上的信息传播有着非常重要的理论意义和实用价值。 该领域关心的一个核
心的科学问题是，如何选择有限的初始传播用户，使得其全局传播能力最大。以往的研
究虽然在算法设计方面取得一些成果，但一直还是面临着巨大的挑战：其一，该问题是
一个NP难题；其二，今天的社交网络规模十分巨大而且时刻都在变化。由于大家一直坚
信，计算在线社交网络用户的全局影响力必须用到网络的全局信息，这使得大多数的算
法对于规模巨大的在线社交网络是不实用的，因为很多时候我们无法获取网络的全局结
构数据，即使有其计算代价往往也难以承受。

另一方面，基于大量的社会实证数据，耶鲁大学社会科学家们发现，个人的影响力大都
会局限在其朋友的朋友的朋友之内，如抽烟、酗酒和吸食大麻等行为，也就是著名的“
三度影响力”理论。这与需要全局数据的观点恰好相反，“三度影响力”理论表明，可
以从个体的局部网络结构信息来衡量其在全网上的社会影响力。这两者看起来相互矛盾
的结论引起了一个根本的问题：是否真的可以仅仅只根据局部的网络结构信息来准确度
量个体的全局影响力？在该项研究中，胡延庆副教授与其合作者给出了该问题的具体答
案，并且解释清楚了全局和局域之间的联系。并发现一个普适的结论：对于初始条件一
样的传播事件，其传播范围只能以一定概率属于如下两种情况之一，一个是传播不开的
局域态，即信息传播很少几步就终止了；另一个是全局传播，传播范围与网络规模成正
比，等于该传播概率对应的边渗流模型中的巨连通集团大小。并且这两种状态可以非常
明显地区分出来，由此得到三个重要结果：（1）在在线社交网络中，个体的传播力可以
被精确地定义为最大连通渗流集团的大小与个体在该连通集团的概率的乘积。这里第一
次给出了社交网络中个体传播力的简洁数学方程。（2）任何个体的影响力都可以在特征
关联长度内，仅仅通过局部的网络结构信息来精确衡量，其误差会随该长度成指数衰减。
这种现象与物理相变中临界行为之间有着深刻的理论关联。（3）基于上述发现，设计了
一个优化算法来选择最具有影响力的个体。该算法不需要知道网络结构的全局信息，从
而其计算时间复杂度与网络规模无关为一常数。在顶点数量以亿为单位的网络上，该算
法时间复杂度比以往最快的贪心算法快上千万倍，且可以获得质量极高的优化解。

《美国科学院院刊》(PNAS)是与Nature、Science齐名，被引用次数最多的综合学科文献
之一。自1914年创刊至今，PNAS提供具有高水平的前沿研究报告、学术评论、学科回顾
及前瞻、学术论文以及美国国家科学学会学术动态的报道和出版。PNAS收录的文献涵盖
生物、物理和社会科学，近三年平均影响因子为9.7 。

值得一提的是，该成果未发表之前，挂在Arxiv上的版本已经被综述性杂志Physics Reports（IF:22）
上的文章做了详细介绍，评价我们的结果为：“利用SIR家族传播动力学与边渗流的关，
胡等发现了SIR家族传播动力学中的核心规律—传播结果只能为两个状态之一：一个为局
部态,另一个为全局态。这个发现是非常深刻的,而且激动人心,一个节点或者一组节点的
全局影响力只用局部网络信息就可以精确度量。”

该工作主要受国家自然科学基金、广州市科技项目与中山大学超算培育项目支持。