【51CTO.com快譯】現(xiàn)實(shí)生活中經(jīng)常有突發(fā)熱點(diǎn)事件，例如突發(fā)熱點(diǎn)新聞，突發(fā)疫情，突發(fā)信息安全事件等等。如果能夠提前預(yù)測(cè)突發(fā)事件，不僅能夠防止重大安全事件的發(fā)生，在某些商業(yè)應(yīng)用場(chǎng)景下還能帶來(lái)高額的商業(yè)收益。不管是在學(xué)術(shù)界還是工業(yè)界，突發(fā)熱點(diǎn)事件都是研究和關(guān)注的重點(diǎn)。

信息瀑布模型(Information Cascades)是近年來(lái)社交網(wǎng)絡(luò)分析的研究熱點(diǎn)。信息瀑布模型主要研究社交網(wǎng)絡(luò)中信息的擴(kuò)散情況，例如豆瓣網(wǎng)對(duì)某本書(shū)點(diǎn)贊行為的擴(kuò)散模型。信息瀑布模型在學(xué)術(shù)界和工業(yè)界引起了廣泛的關(guān)注。Facebook 作為全球***的社交網(wǎng)站，對(duì)信息瀑布模型也非常的重視。本文編譯自知名國(guó)際會(huì)議 WWW 2017 年 Facebook 和弗吉尼亞理工聯(lián)合發(fā)表的論文 Detecting Large Reshare Cascades in Social Networks。

信息瀑布模型可以歸約為如下問(wèn)題：判斷社交網(wǎng)絡(luò)中某個(gè)時(shí)間什么時(shí)候會(huì)產(chǎn)生爆發(fā)式的流行行為。因?yàn)檫@種爆發(fā)式的流行行為非常的少見(jiàn)，并且是爆發(fā)式的，因此傳統(tǒng)的一些算法會(huì)受到極大的影響。如果用分類的方式對(duì)問(wèn)題進(jìn)行預(yù)測(cè)，會(huì)導(dǎo)致不均衡分類問(wèn)題;如果用時(shí)間序列分析的方法來(lái)對(duì)問(wèn)題建模，因?yàn)楸l(fā)式的流行行為與時(shí)間序列的平滑性等要求不符，因此也很難對(duì)問(wèn)題進(jìn)行好的刻畫。而生存分析技術(shù)能夠很好地解決這一問(wèn)題。

Facebook 為了解決這類信息瀑布模型問(wèn)題，提出了 SansNet 方法。問(wèn)題的場(chǎng)景是為了刻畫網(wǎng)站上轉(zhuǎn)播行為(reshare)的信息傳播模式。

首先我們定義一下什么樣的行為被認(rèn)為是爆發(fā)式的流行行為。Facebook 認(rèn)為當(dāng)轉(zhuǎn)播行為超過(guò)了絕對(duì)或者相對(duì)大小的某個(gè)閾值，就認(rèn)為是爆發(fā)式的流行行為，例如某個(gè)帖子被轉(zhuǎn)播了1萬(wàn)次。問(wèn)題的定義如下：

Facebook 用擴(kuò)展 COX 模型對(duì) m 個(gè)轉(zhuǎn)貼時(shí)間序列進(jìn)行預(yù)測(cè)。這個(gè)模型的生存函數(shù)如下：

其中 v(t) 是 t 時(shí)刻信息瀑布的大小。

爆發(fā)式流行行為可以歸約為如下***化問(wèn)題:

該***化問(wèn)題的本質(zhì)是分類問(wèn)題 , 其中 是分類標(biāo)簽( +1 / -1) 用來(lái)標(biāo)記某個(gè)帖子的轉(zhuǎn)播時(shí)間序列是否是爆發(fā)式流行行為。 是每一類的誤分率。這個(gè)問(wèn)題的實(shí)質(zhì)是通過(guò)生存概率來(lái)***化兩個(gè)不同分類之間的***間隔，或者換句話來(lái)說(shuō)，最小化分類問(wèn)題的誤分率。

SansNet 算法的偽代碼如下：

SansNet 的總的時(shí)間復(fù)雜度是 O(m(|R|+T)) 。

Facebook 的研究人員選取了 2015 年 8 月8日上傳到 Facebook 的 25 萬(wàn)個(gè)照片和視頻，統(tǒng)計(jì)了每個(gè)小時(shí)照片/視頻的轉(zhuǎn)發(fā)量，將持續(xù)一周時(shí)間的數(shù)據(jù)作為實(shí)驗(yàn)數(shù)據(jù)集進(jìn)行了算法實(shí)驗(yàn)。SansNet 在照片和視頻上的召回率(紅色線條)如下：

可以看到 SansNet 算法與線形模型、邏輯回歸、樹(shù)模型和隨機(jī)過(guò)程模型相比有明顯的優(yōu)勢(shì)。

SansNet 在 Top 10 熱點(diǎn)的覆蓋率如下所示:

SansNet 在 Top 30 熱點(diǎn)的覆蓋率如下所示:

Facebook 的這篇論文是 2017 年發(fā)表的***成果，具有廣泛的應(yīng)用場(chǎng)景。例如：新聞網(wǎng)站如新浪和網(wǎng)易均把熱點(diǎn)預(yù)測(cè)作為重要的算法研究問(wèn)題。另外針對(duì)社交網(wǎng)站例如 Twitter 上流行微博和流行主題的預(yù)測(cè)也引起了學(xué)術(shù)界和工業(yè)界的廣泛關(guān)注。預(yù)測(cè)問(wèn)題是大數(shù)據(jù)領(lǐng)域具有重要現(xiàn)實(shí)意義的問(wèn)題，特別是長(zhǎng)期預(yù)測(cè)，至今仍是一個(gè)充滿挑戰(zhàn)性的***。

原文標(biāo)題：Detecting Large Reshare Cascades in Social Networks，作者：Karthik Subbian , B. Aditya Prakash , Lada Adamic 

【51CTO譯稿，合作站點(diǎn)轉(zhuǎn)載請(qǐng)注明原文譯者和出處為51CTO.com】