近日以我校為第一完成單位，數(shù)據(jù)科學(xué)與計(jì)算機(jī)學(xué)院胡延慶副教授與其合作者包括紀(jì)圣塨博士生、金瑜亮研究員、馮凌研究員等在國(guó)際頂級(jí)綜合性期刊《PNAS》上發(fā)表了題為“Local structure can identify and quantify influential global spreaders in large scale social networks”的長(zhǎng)達(dá)57頁(yè)研究論文（包括附錄），從理論上完整給出了在線(xiàn)社交網(wǎng)絡(luò)上信息傳播的引爆點(diǎn)（tipping point）。為在線(xiàn)社交網(wǎng)絡(luò)上的廣告推送、社會(huì)感知、謠言控制等構(gòu)建了理論基礎(chǔ)，設(shè)計(jì)了對(duì)應(yīng)的低代價(jià)、高效率并易于執(zhí)行的算法。該成果為我院在大數(shù)據(jù)與交叉學(xué)科研究方面取得的重要標(biāo)志性成果之一。
在線(xiàn)社交網(wǎng)絡(luò)上信息傳播的局域態(tài)與全局態(tài)
隨著互聯(lián)網(wǎng)技術(shù)的發(fā)展，微信、微博等社交平臺(tái)的大量涌現(xiàn)，在線(xiàn)社交網(wǎng)絡(luò)正以其強(qiáng)大的傳播功能逐步取代傳統(tǒng)媒體。社交媒體不僅是社會(huì)思想文化的集散地，也是輿論、謠言等信息的放大器。研究在線(xiàn)社交網(wǎng)絡(luò)上信息傳播的規(guī)律，對(duì)社會(huì)感知、謠言控制、引導(dǎo)與干預(yù)網(wǎng)絡(luò)上的信息傳播有著非常重要的理論意義和實(shí)用價(jià)值。 該領(lǐng)域關(guān)心的一個(gè)核心的科學(xué)問(wèn)題是，如何選擇有限的初始傳播用戶(hù)，使得其全局傳播能力最大。以往的研究雖然在算法設(shè)計(jì)方面取得一些成果，但一直還是面臨著巨大的挑戰(zhàn)：其一，該問(wèn)題是一個(gè)NP難題；其二，今天的社交網(wǎng)絡(luò)規(guī)模十分巨大而且時(shí)刻都在變化。由于大家一直堅(jiān)信，計(jì)算在線(xiàn)社交網(wǎng)絡(luò)用戶(hù)的全局影響力必須用到網(wǎng)絡(luò)的全局信息，這使得大多數(shù)的算法對(duì)于規(guī)模巨大的在線(xiàn)社交網(wǎng)絡(luò)是不實(shí)用的，因?yàn)楹芏鄷r(shí)候我們無(wú)法獲取網(wǎng)絡(luò)的全局結(jié)構(gòu)數(shù)據(jù)，即使有，其計(jì)算代價(jià)往往也難以承受。
另一方面，基于大量的社會(huì)實(shí)證數(shù)據(jù)，耶魯大學(xué)社會(huì)科學(xué)家們發(fā)現(xiàn)，個(gè)人的影響力大都會(huì)局限在其朋友的朋友的朋友之內(nèi)，如抽煙、酗酒和吸食大麻等行為，也就是著名的“三度影響力”理論。這與需要全局?jǐn)?shù)據(jù)的觀(guān)點(diǎn)恰好相反，“三度影響力”理論表明，可以從個(gè)體的局部網(wǎng)絡(luò)結(jié)構(gòu)信息來(lái)衡量其在全網(wǎng)上的社會(huì)影響力。這兩者看起來(lái)相互矛盾的結(jié)論引起了一個(gè)根本的問(wèn)題：是否真的可以?xún)H僅只根據(jù)局部的網(wǎng)絡(luò)結(jié)構(gòu)信息來(lái)準(zhǔn)確度量個(gè)體的全局影響力？在該項(xiàng)研究中，胡延慶副教授與其合作者給出了該問(wèn)題的具體答案，并且解釋清楚了全局和局域之間的聯(lián)系。并發(fā)現(xiàn)一個(gè)普適的結(jié)論：對(duì)于初始條件一樣的傳播事件，其傳播范圍只能以一定概率屬于如下兩種情況之一，一個(gè)是傳播不開(kāi)的局域態(tài)，即信息傳播很少幾步就終止了；另一個(gè)是全局傳播，傳播范圍與網(wǎng)絡(luò)規(guī)模成正比，等于該傳播概率對(duì)應(yīng)的邊滲流模型中的巨連通集團(tuán)大小。并且這兩種狀態(tài)可以非常明顯地區(qū)分出來(lái)，由此得到三個(gè)重要結(jié)果：（1）在在線(xiàn)社交網(wǎng)絡(luò)中，個(gè)體的傳播力可以被精確地定義為最大連通滲流集團(tuán)的大小與個(gè)體在該連通集團(tuán)的概率的乘積。這里第一次給出了社交網(wǎng)絡(luò)中個(gè)體傳播力的簡(jiǎn)潔數(shù)學(xué)方程。（2）任何個(gè)體的影響力都可以在特征關(guān)聯(lián)長(zhǎng)度內(nèi)，僅僅通過(guò)局部的網(wǎng)絡(luò)結(jié)構(gòu)信息來(lái)精確衡量，其誤差會(huì)隨該長(zhǎng)度成指數(shù)衰減。這種現(xiàn)象與物理相變中臨界行為之間有著深刻的理論關(guān)聯(lián)。（3）基于上述發(fā)現(xiàn)，設(shè)計(jì)了一個(gè)優(yōu)化算法來(lái)選擇最具有影響力的個(gè)體。該算法不需要知道網(wǎng)絡(luò)結(jié)構(gòu)的全局信息，從而其計(jì)算時(shí)間復(fù)雜度與網(wǎng)絡(luò)規(guī)模無(wú)關(guān)為一常數(shù)。在頂點(diǎn)數(shù)量以?xún)|為單位的網(wǎng)絡(luò)上，該算法時(shí)間復(fù)雜度比以往最快的貪心算法快上千萬(wàn)倍，且可以獲得質(zhì)量極高的優(yōu)化解。
《美國(guó)科學(xué)院院刊》(PNAS)是與Nature、Science齊名，被引用次數(shù)最多的綜合學(xué)科文獻(xiàn)之一。自1914年創(chuàng)刊至今，PNAS提供具有高水平的前沿研究報(bào)告、學(xué)術(shù)評(píng)論、學(xué)科回顧及前瞻、學(xué)術(shù)論文以及美國(guó)國(guó)家科學(xué)學(xué)會(huì)學(xué)術(shù)動(dòng)態(tài)的報(bào)道和出版。PNAS收錄的文獻(xiàn)涵蓋生物、物理和社會(huì)科學(xué)，近三年平均影響因子為9.7 。
值得一提的是，該成果未發(fā)表之前，掛在A(yíng)rxiv上的版本已經(jīng)被綜述性雜志Physics Reports（IF:22）上的文章做了詳細(xì)介紹，評(píng)價(jià)其結(jié)果為：“利用SIR家族傳播動(dòng)力學(xué)與邊滲流的關(guān)，胡等發(fā)現(xiàn)了SIR家族傳播動(dòng)力學(xué)中的核心規(guī)律—傳播結(jié)果只能為兩個(gè)狀態(tài)之一：一個(gè)為局部態(tài),另一個(gè)為全局態(tài)。這個(gè)發(fā)現(xiàn)是非常深刻的,而且激動(dòng)人心,一個(gè)節(jié)點(diǎn)或者一組節(jié)點(diǎn)的全局影響力只用局部網(wǎng)絡(luò)信息就可以精確度量。”
上述研究工作得到國(guó)家自然科學(xué)基金、廣州市科技項(xiàng)目與我校超算培育項(xiàng)目的支持。
論文鏈接：http://www.pnas.org/content/early/2018/07/02/1710547115.short
