蘇曉光 富春巖

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

關鍵詞：社交圈；聚類問題；分層嵌套

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

1引言

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

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

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

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

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

3 構建特征集

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

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

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

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

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

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

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

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

第二個屬性是圈內成員應該與個人網(wǎng)絡的擁有常見的關系：

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

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

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

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

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

4 實驗內容

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

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

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

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

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

將本文的方法與三種方法進行對比，第1種是Streich等提出的多任務聚簇算法，記為“聚簇”；第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ū)精度的對比結果。

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

5 結論

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

參考文獻：

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