近日以我校為第一完成單位，數據科學與計算機學院胡延慶副教授與其合作者包括紀圣塨博士生、金瑜亮研究員、馮凌研究員等在國際頂級綜合性期刊《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家族傳播動力學中的核心規律—傳播結果只能為兩個狀態之一：一個為局部態,另一個為全局態。這個發現是非常深刻的,而且激動人心,一個節點或者一組節點的全局影響力只用局部網絡信息就可以精確度量?！?/p>

上述研究工作得到國家自然科學基金、廣州市科技項目與我校超算培育項目的支持。

論文鏈接：http://www.pnas.org/content/early/2018/07/02/1710547115.short