一種自動發(fā)現(xiàn)社交網(wǎng)絡(luò)中社交圈算法的實驗設(shè)計與分析

蘇曉光 富春巖

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

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

中圖分類號：TP311 文獻標志碼：A 文章編號：1009-3044（2018）15-0045-02

1引言

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

2實驗用數(shù)據(jù)集

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

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

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

3 構(gòu)建特征集

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

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

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

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

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

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

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

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

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

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

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

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

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

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

4 實驗內(nèi)容

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

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

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

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

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

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

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

5 結(jié)論

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

參考文獻：

[1] 于占龍，董麗新，陳玉林，等. 一種自動發(fā)現(xiàn)社交網(wǎng)絡(luò)中社交圈的方法[J]. 電腦知識與技術(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.