蘇曉光 富春巖

摘要：本文對依據(jù)一種新穎的識(shí)別用戶社交圈的方法所建模型進(jìn)行了實(shí)驗(yàn)設(shè)計(jì)及分析。將朋友之間相互網(wǎng)絡(luò)聯(lián)系視為用戶個(gè)人網(wǎng)絡(luò)上的點(diǎn)聚類問題，同時(shí)結(jié)合網(wǎng)絡(luò)結(jié)構(gòu)和用戶資料信息開發(fā)了一種檢測社交圈的模型，對于每個(gè)聚集可分析其成員以及特定用戶信息的相似性度量，通過對多重社交圈建立的點(diǎn)關(guān)系模型，可以發(fā)現(xiàn)重疊和分層嵌套的社交圈。通過真實(shí)數(shù)據(jù)來驗(yàn)證模型的性能，實(shí)驗(yàn)結(jié)果表明，本文所建模型可以準(zhǔn)確識(shí)別社交圈中多樣化數(shù)據(jù)的歸屬集合。

關(guān)鍵詞：社交圈；聚類問題；分層嵌套

中圖分類號(hào)：TP311 文獻(xiàn)標(biāo)志碼：A 文章編號(hào)：1009-3044（2018）15-0045-02

1引言

如何組織龐大而凌亂的個(gè)人社交網(wǎng)絡(luò)是具有挑戰(zhàn)性的問題，社交網(wǎng)站允許用戶手動(dòng)將他們的朋友分配到各社交圈，如微信的“朋友圈”，人人網(wǎng)的“好友”等。用戶借助社交網(wǎng)站來組織網(wǎng)絡(luò)和交流，將朋友分類到所謂的社交朋友圈，幾乎所有的社交網(wǎng)站提供了這樣的功能。構(gòu)建這樣的社交圈不但要耗費(fèi)用戶大量的精力，而且隨著用戶社交圈的擴(kuò)大，隨時(shí)更新的代價(jià)驚人。目前構(gòu)建如上社交圈的方法都不盡如人意，我們項(xiàng)目組在文獻(xiàn)[1]中提出一種自動(dòng)發(fā)現(xiàn)社交網(wǎng)絡(luò)中社交圈的方法，通過在真實(shí)數(shù)據(jù)集上評(píng)估，與Streich等提出的多任務(wù)聚簇算法[2]，Yoshida等提出的低秩嵌入算法[3]，Balasubramanya和Cohen提出的block-LDA算法[4，5]進(jìn)行對比，本方法依靠結(jié)合點(diǎn)和邊的信息來預(yù)測多元朋友圈中的成員，具有良好的性能。

2實(shí)驗(yàn)用數(shù)據(jù)集

為了在真實(shí)數(shù)據(jù)集上評(píng)估非監(jiān)督算法，本文從微信、Google+和人人網(wǎng)等三個(gè)主要社交網(wǎng)絡(luò)獲得個(gè)人網(wǎng)絡(luò)和真實(shí)數(shù)據(jù)，包含193個(gè)朋友圈和4039個(gè)用戶。我們開發(fā)了專門的微信應(yīng)用程序?qū)?0個(gè)用戶進(jìn)行調(diào)查，要求他們手動(dòng)確定其朋友應(yīng)該屬于哪個(gè)朋友圈。平均來說，用戶大概會(huì)確定19個(gè)朋友圈，圈內(nèi)成員平均22個(gè)。

從Google+上獲得了133個(gè)個(gè)人網(wǎng)絡(luò)，包括479個(gè)朋友圈和106674個(gè)用戶。這133個(gè)個(gè)人網(wǎng)絡(luò)代表了所有Google+中至少分享兩個(gè)朋友圈的133個(gè)用戶，并且這些人的網(wǎng)絡(luò)信息是公開的。與微信上的朋友圈不一樣，有些Google+社交圈的創(chuàng)建者已選擇公開它們，Google+是一個(gè)有向網(wǎng)絡(luò)。比如，一個(gè)圈包含2012年最有影響的歌星候選人，他們可能不會(huì)反過來跟隨他們的粉絲。

從人人網(wǎng)上得到1000個(gè)個(gè)人網(wǎng)絡(luò)，包括4896個(gè)圈和81362個(gè)用戶，選的個(gè)人網(wǎng)絡(luò)的大小是10到4964個(gè)節(jié)點(diǎn)。全部數(shù)據(jù)共有1143個(gè)個(gè)人網(wǎng)絡(luò)，5541個(gè)社交圈和192075個(gè)用戶。其中微信的數(shù)據(jù)是完全標(biāo)記的，其本質(zhì)上用戶認(rèn)為具有凝聚力的社區(qū)朋友圈，而Google+和人人網(wǎng)上的數(shù)據(jù)只是部分被標(biāo)記，即只能使用公共圈。

3 構(gòu)建特征集

所有的數(shù)據(jù)集信息都可以表示成一個(gè)樹，其中每層編碼表示越來越多的特定信息。對于Google+數(shù)據(jù)，從6個(gè)方面收集數(shù)據(jù)（性別、姓名、頭銜、機(jī)構(gòu)、大學(xué)和居住地）。對于微信上數(shù)據(jù)，從26個(gè)方面收集數(shù)據(jù)，包括籍貫、生日、同事、政治面貌等。對于人人網(wǎng)，簡單地從兩個(gè)方面收集數(shù)據(jù)，即兩周內(nèi)用戶用到的組標(biāo)簽和提示。“類別”對應(yīng)于概要樹里葉子節(jié)點(diǎn)的父節(jié)點(diǎn)。

首先描述如何用一個(gè)差別向量為兩個(gè)用戶之間的關(guān)系編碼。假設(shè)每個(gè)用戶[v∈V]都有一個(gè)相關(guān)的信息樹[Tv]，并且[l∈Tv]是樹中的葉子。定義用戶x和y的差別向量[σx，y]是一個(gè)二進(jìn)制指示器反映x和y之間的差異：

[σx，y[l]=δ（（l∈Tx）≠（l∈Ty））] （1）

上述差別向量在信息編碼粒度方面有一定優(yōu)勢，但是它的不足在于維數(shù)太高（多達(dá)4122維）。解決這個(gè)問題的一種方法是基于葉節(jié)點(diǎn)的父節(jié)點(diǎn)來形成差別向量。對兩個(gè)用戶信息的共同類別進(jìn)行編碼，不考慮具體值。例如，關(guān)注編碼兩個(gè)用戶共同擁有多少個(gè)標(biāo)簽，而不在乎到底是哪一個(gè)標(biāo)簽：

[σ′x，y[p]=l∈children（p）σx，y[l]] （2）

這種方案的優(yōu)勢在于它只需一個(gè)固定數(shù)量的維度，而不管個(gè)人網(wǎng)絡(luò)的大?。ㄈ缟纤?，微信有26個(gè)，Google+有6個(gè)，人人網(wǎng)有2個(gè)）。

現(xiàn)在描述如何根據(jù)差別向量[σx，y]（和[σ′x，y]）得到邊特征[?（x，y）]。希望構(gòu)建的第一個(gè)屬性是圈內(nèi)的成員應(yīng)該彼此有常見的關(guān)系：

[?1（x，y）=（1；-σx，y）] （3）

第二個(gè)屬性是圈內(nèi)成員應(yīng)該與個(gè)人網(wǎng)絡(luò)的擁有常見的關(guān)系：

[?2（x，y）=（1；-|σx，u-σy，u|）] （4）

這兩個(gè)參數(shù)允許評(píng)估哪種機(jī)制更適合捕捉用戶對聚集的主觀定義。兩種屬性都有一個(gè)常量特性“1”，用來控制用戶在同一個(gè)朋友圈的可能性，或者度量哪個(gè)朋友圈在更大程度上由朋友組成。重要的是，即使某用戶沒有個(gè)人信息，仍然可以根據(jù)連接模式簡單地預(yù)測他和其他用戶的關(guān)系。類似地，對于“壓縮”差別向量[σ′x，y]，定義

[ψ1（x，y）=（1；-σ′x，y）]

[ψ2（x，y）=（1；-|σ′x，u-σ′y，u|）] （5）

到此為止確定了四種方式來表示兩個(gè)用戶個(gè)人信息的不同方面。認(rèn)為兩種是構(gòu)造差別向量（[σx，y]和[σ′x，y]），還有兩種是捕捉一對信息的兼容性（[?（x，y）]和[ψ（x，y）]）。

4 實(shí)驗(yàn)內(nèi)容

本文通過真實(shí)數(shù)據(jù)檢測收斂后潛在朋友圈[C={C1...CK}]的極大似然值，對一個(gè)適當(dāng)正則化模型，潛在朋友圈應(yīng)該極大程度上與手工表明的圈[C={C1...CK}]接近。

為了衡量[C]和[C_]的接近度，計(jì)算兩個(gè)集合的平衡誤碼率（BER），[BER（C，C）=12（|C＼C|C+|C＼C|C）]。這種方法使偽真和偽假處于同等重要地位，所以細(xì)微或隨機(jī)預(yù)測造成的誤差平均在0.5。

由于不知道[C]和[C]的吻合度，通過計(jì)算線性最大值來得到最優(yōu)匹配：

[maxf：C→C1fC∈dom（f）（1-BER（C，f（C）））] （6）

這里f是[C]和[C]的對應(yīng)，即如果[C]的個(gè)數(shù)[|C|]小于[C]的個(gè)數(shù)|[C]|，那么對于每個(gè)c[∈C]，一定會(huì)有一個(gè)匹配的[c∈C]，但是如果[|C|]>|[C]|，則沒有額外的匹配。另外可以利用最大似然等成熟技術(shù)估計(jì)朋友圈的個(gè)數(shù)。

將本文的方法與三種方法進(jìn)行對比，第1種是Streich等提出的多任務(wù)聚簇算法，記為“聚簇”；第2種是Yoshida等提出的低秩嵌入算法，記為“低秩”；第3種是Balasubramanya和Cohen提出的block-LDA算法，記為“LDA”。本方法在朋友對朋友特征情況下的運(yùn)行（?1=12），記為“F2F12”，本方法在朋友對用戶特征情況下的運(yùn)行（?2=13），記為“F2U13”，本方法在壓縮特征情況下的運(yùn)行（ψ1=14），記為“C114”，本方法在壓縮特征情況下的運(yùn)行（ψ2=14），記為“C214”。圖1給出了各算法在微信、Google+、人人網(wǎng)數(shù)據(jù)集上檢測社區(qū)精度的對比結(jié)果。

根據(jù)式（6）描述朋友圈，并計(jì)算圈子的個(gè)數(shù)，平衡錯(cuò)誤率值（BER）越高性能越好，圖1中柱狀條表示標(biāo)準(zhǔn)錯(cuò)誤率。本方法在最好特征值?情況下的運(yùn)行精度與最接近的競爭者的差異為1%，此時(shí)BER的得分情況是：微信為0.84，Google+為0.72，人人網(wǎng)為0.70。在Google+和人人網(wǎng)上得分較低的原因是：由于最初創(chuàng)建用戶，沒有保持許多社交圈，可達(dá)到較高的回憶值（在每個(gè)圈里重新獲得朋友），但是預(yù)測的精度較低（在朋友圈已建立后出現(xiàn)的額外的好友）。從實(shí)驗(yàn)結(jié)果可以看出，本方法良好的性能主要依靠結(jié)合點(diǎn)和邊的信息來預(yù)測多元朋友圈中的成員，目前還未見其他方法應(yīng)用到這種結(jié)合。

5 結(jié)論

實(shí)驗(yàn)結(jié)果表明，依據(jù)提出方法所建模型可以準(zhǔn)確識(shí)別社交圈中多樣化數(shù)據(jù)的歸屬集合。模型根據(jù)前述方法確定社會(huì)維度。通過實(shí)驗(yàn)發(fā)現(xiàn)，所有的算法在微信上操作都要比在Google+和人人網(wǎng)上要好。不僅提高了檢測精度，還可以對某個(gè)節(jié)點(diǎn)為什么是屬于某個(gè)聚集的進(jìn)行解釋。

參考文獻(xiàn)：

[1] 于占龍，董麗新，陳玉林，等. 一種自動(dòng)發(fā)現(xiàn)社交網(wǎng)絡(luò)中社交圈的方法[J]. 電腦知識(shí)與技術(shù)， 2017，13（36）：166-167.

[2] A. Streich， M. Frank， D. Basin， and J. Buhmann. Multi-assignment clustering for boolean data[C]. JMLR， 2012.

[3] T. Yoshida. Toward finding hidden communities based on user profiles[C]. In ICDM Workshops， 2010.

[4] R. Balasubramanyan andW. Cohen. Block-LDA： Jointly modeling entity-annotated text and entity-entity links[C]. In SDM， 2011.

[5] S. Wu， J. Hofman， W. Mason， D. Watts. Who says what to whom on twitter[C]. In WWW， 2011.