雷鋒網(wǎng)AI科技評(píng)論按：微信群是目前我們最常用的多人聊天方式之一，不過在習(xí)以為常的建群拉人過程中，一個(gè)有意思的問題是，一個(gè)微信群建立起來了，根據(jù)社會(huì)關(guān)系所構(gòu)建起來的網(wǎng)絡(luò)關(guān)系，誰更可能是下一步被邀請(qǐng)入群的人呢？來自清華大學(xué)的唐杰團(tuán)隊(duì)和騰訊公司一起對(duì)這個(gè)問題進(jìn)行了深入細(xì)致的研究，工作發(fā)表在IJCAI17上，論文題目為《Who to Invite Next? Predicting Invitees of Social Groups》，作者包括韓矞（清華），唐杰（清華），葉浩（騰訊），陳波（騰訊）。雷鋒網(wǎng)邀請(qǐng)第一作者韓矞對(duì)論文進(jìn)行了解讀。

論文地址：https://www.ijcai.org/proceedings/2017/0519.pdf

該工作基于微信平臺(tái)研究群組邀請(qǐng)問題，就是預(yù)測(cè)針對(duì)某一個(gè)群，哪些人會(huì)被邀請(qǐng)至這個(gè)群。針對(duì)這個(gè)問題，我們先來看下面一個(gè)例子。

圖 1

上面這張圖表示某一個(gè)時(shí)刻的一個(gè)社交網(wǎng)絡(luò)的群組及其相關(guān)的用戶，比如我們可以把它看作一個(gè)微信聊天群，每個(gè)頭像表示一個(gè)用戶，用戶之間的邊可以看作微信好友關(guān)系。處于藍(lán)色圓圈內(nèi)的用戶是這個(gè)微信群的成員，我們把不屬于微信群但與群成員有好友關(guān)系的用戶稱為這個(gè)群的「邊緣用戶」，也就是問題中的可能被邀請(qǐng)者。那么根據(jù)這張圖展現(xiàn)的網(wǎng)絡(luò)結(jié)構(gòu)關(guān)系，我們直觀地感覺哪一個(gè)用戶將會(huì)在下一個(gè)時(shí)刻被邀請(qǐng)？也許用戶 A 的可能性大一些，因?yàn)樗腥齻€(gè)好友在群里。那么再提一個(gè)問題，如果用戶 B 在下一個(gè)時(shí)刻被邀請(qǐng)入群，那么誰更可能會(huì)被邀請(qǐng)入群？結(jié)論也許是 C，因?yàn)?B 與 C 有兩個(gè)共同好友。這給我們解決預(yù)測(cè)被邀請(qǐng)者提供了一些思路，不過我們還是需要在實(shí)際數(shù)據(jù)上驗(yàn)證我們的直覺。

我們?cè)谡鎸?shí)的微信社交平臺(tái)上提取了數(shù)據(jù)進(jìn)行觀察。我們提取了微信在半個(gè)小時(shí)內(nèi)新建的有名字的群進(jìn)行研究，共涉及到了 300 多萬個(gè)用戶，400 多萬條邊和將近 100 多萬條邀請(qǐng)記錄。為了分析群組的變化過程，我們?cè)谌航M產(chǎn)生時(shí)刻到一后之間的時(shí)間段中設(shè)置了 7 個(gè)觀察點(diǎn)進(jìn)行觀察，分別是群組新建后的半小時(shí)，1 小時(shí)，3 小時(shí)，24 小時(shí)，1 個(gè)月，3 個(gè)月，6 個(gè)月以及 1 年后。見下圖：

 

圖 2

圖 2（a）表示的是群組成員數(shù)一年的變化情況。我們以最后一個(gè)觀察點(diǎn)為基準(zhǔn)，計(jì)算之前每個(gè)觀察點(diǎn)的群組成員數(shù)的百分比。橫軸是時(shí)間軸，縱軸是百分比。為了更好展示群組在前四個(gè)觀察點(diǎn)的變化情況，我們專門把前四個(gè)觀察點(diǎn)畫在圖 2（b）中。我們可以看到，群組隨著時(shí)間變化呈現(xiàn)出不斷增大的趨勢(shì)，而且時(shí)間越靠前，增大速度越快，時(shí)間過去越久，增大速度越慢。而隨著微信群的增大，用戶被邀請(qǐng)進(jìn)群的概率也隨之變小，如圖 3 所示。

 

圖 3

圖 3（a）表示的是用戶被邀請(qǐng)入群的可能性隨時(shí)間變化的情況。同樣，圖 3（b）是前四個(gè)觀察點(diǎn)的放大版。所以我們可以得出一個(gè)結(jié)論，從群的整體屬性角度講，它會(huì)對(duì)用戶的入群可能性產(chǎn)生影響。

接著，我們進(jìn)一步觀察用戶之間的互相影響。我們先設(shè)想如果兩個(gè)邊緣用戶針對(duì)某一個(gè)群具有某種相近性，那么我們就可以認(rèn)為這兩個(gè)用戶針對(duì)這個(gè)群的被邀請(qǐng)可能性具有某種相關(guān)性。也就是說一個(gè)用戶被邀請(qǐng)后，另一個(gè)用戶隨即也會(huì)被邀請(qǐng)。我們把這種用戶稱為這個(gè)群的「伙伴邊緣用戶」。為了更量化地分析這種相關(guān)性，我們這里定義兩種伙伴用戶。第一種是這個(gè)群的兩個(gè)邊緣用戶具有好友關(guān)系。第二種是這個(gè)群的兩個(gè)邊緣用戶有不止一個(gè)共同好友是這個(gè)群的成員。如圖 4 所示：

圖 1 中，用戶 D 和用戶 E 屬于第一種伙伴邊緣用戶，而用戶 B 和用戶 C 屬于第二種伙伴邊緣用戶。圖 4 量化展示了這兩種用戶被邀請(qǐng)入群的可能性。

 

圖 4

圖 4 中，紅色柱體代表用戶的平均入群概率，黃色柱體代表第一種伙伴邊緣用戶在有一個(gè)用戶入群后另一個(gè)用戶入群的可能性，藍(lán)色柱體代表第二種伙伴邊緣用戶在有一個(gè)用戶入群后另一個(gè)用戶入群的可能性，藍(lán)色柱體下面的數(shù)字標(biāo)號(hào)代表這兩個(gè)用戶在群中的共同好友個(gè)數(shù)。我們可以看到，這兩種伙伴邊緣用戶的入群可能性要遠(yuǎn)高于平均可能性。

我們還有一個(gè)假設(shè)是如果一個(gè)用戶和一個(gè)群越「親密」，那么這個(gè)用戶被邀入群的可能性就越大。為了驗(yàn)證這個(gè)假設(shè)，我們先定義兩個(gè)指標(biāo)來衡量這種親密程度。第一種是群成員中用戶的好友數(shù)，第二種是群成員中用戶的鄰接三角形數(shù)（即用戶的鄰接閉三角形中另兩個(gè)節(jié)點(diǎn)在群中）。例如圖 1 中用戶 A 的第一種指標(biāo)值是 3，第二種指標(biāo)值是 2.

圖 5

圖 5（a）所示的是用戶第一種指標(biāo)的可能性。橫軸是用戶的群成員好友數(shù)，縱軸是入群可能性。圖 5（b）展示的是用戶第二種指標(biāo)的可能性。橫軸是用戶群成員鄰接三角形數(shù)，縱軸是入群可能性。很明顯，對(duì)于這兩種指標(biāo)，都是值越大，入群可能性總體上也是增大的趨勢(shì)。

因此，我們可以把影響用戶入群可能性的因素歸結(jié)為三大類，即群整體因素，用戶之間的因素和用戶與群關(guān)系的因素，分別用 g，h 和 f 表示。我們可以為這三種因素分別建模，即：

然后再把它們?nèi)诤系揭粋€(gè)統(tǒng)一框架中。如圖 6 所示。

 

圖 6

根據(jù)因子圖模型理論我們可以將用戶入群可能性分解為這三種因素的乘積，即 

繼而得到目標(biāo)函數(shù)，即

。

我們對(duì)目標(biāo)函數(shù)求偏導(dǎo)，得到

其他兩種因子參數(shù)與其類似，在此省略。此式中，等號(hào)右邊的第一項(xiàng)表示函數(shù)基于數(shù)據(jù)分布的期望，這個(gè)比較好算，因?yàn)閿?shù)據(jù)是有限的。第二項(xiàng)是函數(shù)基于模型參數(shù)的期望，這個(gè)無法計(jì)算。我們采用信念傳播的方法來解決這個(gè)問題。有了偏導(dǎo)值，我們就可以采用梯度更新的方式來優(yōu)化參數(shù)，即

然后用優(yōu)化好的參數(shù)來預(yù)測(cè)用戶是否被邀入群。

我們用兩種基準(zhǔn)方法來評(píng)估模型的性能。第一種是分類方法，第二種是鏈接預(yù)測(cè)方法。實(shí)驗(yàn)結(jié)果如表 1 所示（ML-FGM 是文中所述模型）。

表 1

另外，為了觀察每種因子的對(duì)模型性能的影響，我們分別移除群因子，用戶互相影響因子來做實(shí)驗(yàn)，如圖 7 所示。

 

圖 7

四種顏色柱體分別表示無移除，只移除群因子，只移除用戶互相影響因子和移除這兩種因子的性能?？梢钥吹?，移除用戶互相影響因子對(duì)性能的影響還是比較大的。

本文從影響用戶入群的因素分析著手，采用一個(gè)概率因子圖模型將可能影響用戶被邀入群的三種因素集成到一個(gè)框架中，提高了預(yù)測(cè)用戶入群的概率。群組是社交網(wǎng)絡(luò)中的一個(gè)重要概念，我們可以用用戶網(wǎng)絡(luò)結(jié)構(gòu)來預(yù)測(cè)群組的發(fā)展變化，另一方面，群組的發(fā)展變化也影響著用戶網(wǎng)絡(luò)結(jié)構(gòu)。因此，研究群組對(duì)用戶網(wǎng)絡(luò)結(jié)構(gòu)的影響并利用該信息預(yù)測(cè)網(wǎng)絡(luò)結(jié)構(gòu)的發(fā)展變化也是本領(lǐng)域亟待解決的一個(gè)問題。

雷峰網(wǎng)特約稿件，未經(jīng)授權(quán)禁止轉(zhuǎn)載。詳情見轉(zhuǎn)載須知。