于占龍　董麗新　陳玉林　富春巖　周虹　支援　曲思龍

摘要：該文提出一種新穎的識別用戶社交圈的機(jī)器學(xué)習(xí)方法，將朋友之間相互網(wǎng)絡(luò)聯(lián)系視為用戶個人網(wǎng)絡(luò)上的點(diǎn)聚類問題，開發(fā)出一種檢測社交圈的模型，對于每個聚集可分析其成員以及特定用戶信息的相似性度量，通過對多重社交圈建立的點(diǎn)關(guān)系模型，可以發(fā)現(xiàn)重疊和分層嵌套的社交圈。

關(guān)鍵詞：社交圈；相似性；重疊

中圖分類號：TP393 文獻(xiàn)標(biāo)識碼：A 文章編號：1009-3044（2017）36-0166-02

1 概述

在線社交網(wǎng)絡(luò)允許用戶跟蹤數(shù)以百計的好友和熟人公布的信息流。用戶的朋友形成大量的信息，導(dǎo)致他們在組織個人社交網(wǎng)絡(luò)時要應(yīng)付信息過載的問題。用戶借助社交網(wǎng)站來組織網(wǎng)絡(luò)和交流內(nèi)容，將朋友分類到所謂的社交朋友圈。目前，在微信、Google和人人網(wǎng)上的用戶要么手動分類他們的社交圈，要么通過共同的屬性確定朋友。兩種方法都不太令人滿意：前者浪費(fèi)時間并且當(dāng)用戶的好友增加時不會自動更新，而后者不能捕捉整個群體的個別方面，當(dāng)個人信息丟失或需要保留時可能會失去確定朋友的效果。

2 擬解決的關(guān)鍵問題

每一個朋友圈都是他的朋友的一個子集，社交圈是特定于用戶的，因為每個用戶社交圈的好友都是獨(dú)立于與他沒有聯(lián)系的用戶。這就意味著可以把社交圈檢測描述為個人網(wǎng)絡(luò)和他朋友之間網(wǎng)絡(luò)關(guān)系的聚類問題。

本文研究如何自動發(fā)現(xiàn)用戶的社交圈問題，特別是給定某個用戶的個人社交網(wǎng)路，如何確定他的社交圈。如圖1所示，指定某用戶個體u，他的朋友vi形成一個網(wǎng)絡(luò)，定義節(jié)點(diǎn)vi為可變點(diǎn)，本文的任務(wù)是確定vi屬于哪個集合，進(jìn)而發(fā)現(xiàn)個人網(wǎng)絡(luò)里嵌套和重合的聚類。

為了解決這一問題，可以采用兩種數(shù)據(jù)資源，首先是個人網(wǎng)絡(luò)的邊集合，我們希望聚集圈是由密集聯(lián)系的可變點(diǎn)集構(gòu)成的[1]。然而實際情況中，不同朋友圈重疊嚴(yán)重，可變點(diǎn)可以同時屬于多個朋友圈[2，3]，并且許多聚集圈是分層嵌套在較大的圈里面（如圖1），因此建立可變點(diǎn)屬于多個聚集圈的模型非常重要。其次，每個圈不僅緊密聯(lián)系，而且它的成員通常有共同的屬性或特性[4]，因此需要對每個聚集圈明確地構(gòu)造不同維度的用戶信息。

圖1中的網(wǎng)絡(luò)顯示了一種可以從數(shù)據(jù)中直接觀察到的典型行為：大約25%的聚集（從微信獲得）完全包含在另一個聚集圈里，50%和另外一個聚集有重疊，還有25%和別的聚集圈沒有交集。本文的目標(biāo)是通過個人朋友之間的網(wǎng)絡(luò)關(guān)系發(fā)現(xiàn)這些聚集，從而發(fā)現(xiàn)聚集成員并找到形成此聚集圈的共同屬性。

根據(jù)可變點(diǎn)之間的潛在變量和相似性構(gòu)造聚集的從屬關(guān)系，并作為共同的配置信息。本文提出一種非監(jiān)督學(xué)習(xí)方法來確定哪些維度的相似性會構(gòu)成緊密聯(lián)系的聚集?；舅枷胧牵航梃bBlau空間[5]概念思想，允許不同的聚集有不同的信息相似，因此一個聚集圈可能由一個學(xué)校的好友組成，而另一個聚集圈則是由來自同一個區(qū)域的好友組成。同時選擇聚集點(diǎn)成員和相似度函數(shù)來建模，從而以最佳方式解釋觀測數(shù)據(jù)。

3 社交網(wǎng)絡(luò)中朋友關(guān)系的生成模型

朋友圈模型應(yīng)遵循以下性質(zhì)：1）集群里的節(jié)點(diǎn)應(yīng)該有共同的屬性或特征；2）不同的集群應(yīng)該由不同的特征構(gòu)成，比如，一個聚集可能由家庭成員組成，另一個聚集可能由一個大學(xué)的同學(xué)組成。3）集群應(yīng)該允許重疊，并且可以在“弱”集中形成“強(qiáng)”集，例如，相同學(xué)位人員組成的朋友圈可以包含在同一大學(xué)的朋友圈里，如圖1所示。4）應(yīng)該利用個人信息和網(wǎng)絡(luò)結(jié)構(gòu)一起來確定集群。理想情況下，應(yīng)該能夠精確地知道利用信息的哪個方面構(gòu)成了這個集群，這樣這個模型對于用戶才是可說明的。本文根據(jù)上述分析提出一種描述社交網(wǎng)絡(luò)中朋友關(guān)系的生成模型。

本模型的輸入是個人網(wǎng)絡(luò)G=（V，E），以及每個用戶v（v[∈]V）的信息。個人網(wǎng)絡(luò)的中心點(diǎn)u不包含在G里，且G只包含u的好友（可變點(diǎn)）。之所以用這個方式定義個人網(wǎng)絡(luò)，是因為朋友圈的創(chuàng)建者自己并不在這些圈里。個人網(wǎng)絡(luò)中每個聚集集合為C={C1…Ck}，Ck [?]V，相關(guān)參數(shù)向量[θk]表示每個聚集如何出現(xiàn)，把用戶信息編碼成二元組特征[?（x，y）]，以某種方式捕捉用戶x和y一些共同的屬性。

本社交圈模型將圈內(nèi)成員視為潛在變量。落在公共圈里的節(jié)點(diǎn)通常有機(jī)會形成邊，這自然會導(dǎo)致社交圈的分層和重疊。本文整合潛在變量和信息相似參數(shù)，設(shè)計無人監(jiān)督算法，以便更好地解釋觀測到的網(wǎng)絡(luò)數(shù)據(jù)。

5 結(jié)論

本文提出一種在社交數(shù)據(jù)上執(zhí)行聚集操作的方法，可以完成完全無監(jiān)督的學(xué)習(xí)，并且能自動確定聚集的個數(shù)以及各自的聚集成員。我們從微信、Google和人人網(wǎng)收集了1143個個人網(wǎng)絡(luò)數(shù)據(jù)集，得到了5636個不同社交圈的手動真實分類。通過對這些網(wǎng)絡(luò)數(shù)據(jù)集上的實驗結(jié)果分析，結(jié)果表明本文提出的同時考慮社交網(wǎng)絡(luò)結(jié)構(gòu)和用戶個人信息的方法明顯比自然選擇和目前流行的方法要好，在檢測精度提高的同時，還可以解釋節(jié)點(diǎn)為什么屬于某個聚集。對本方法進(jìn)一步的研究將適于移動互聯(lián)網(wǎng)的社群網(wǎng)絡(luò)數(shù)據(jù)模型。

參考文獻(xiàn)：

[1] 曹懷虎，朱建明，潘耘，等.情景感知的P2P移動社交網(wǎng)絡(luò)構(gòu)造及發(fā)現(xiàn)算法[J].計算機(jī)學(xué)報，2012，35（6）：1223-1234.

[2] J. Yang and J. Leskovec. Community-affiliation graph model for overlapping community detection. In ICDM， 2012.

[3] G. Palla， I. Derenyi， I. Farkas， and T. Vicsek. Uncovering the overlapping community structure of complex networks in nature and society. Nature， 2005.

[4] 李陟，李千目，張宏，等.基于最近社交圈的社交時延容忍網(wǎng)絡(luò)路由策略[J].計算機(jī)研究與發(fā)展，2012， 49（6）：1185-1195.

[6] McPherson M. An ecology of affiliation. American Sociological Review， 1983.

[7] Rother C， V. Kolmogorov V， Lempitsky V， et al. Optimizing binary MRFs via extended roof duality. In CVPR， 2007.

[8] Handcock M， Raftery A， Tantrum J. Model-based clustering for social networks. Journal of the Royal Statistical Society Series A， 2007.

[9] Volinsky C， Raftery A. Bayesian information criterion for censored survival models. Biometrics， 2000.