一種自動發現社交網絡中社交圈的方法

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

摘要：該文提出一種新穎的識別用戶社交圈的機器學習方法，將朋友之間相互網絡聯系視為用戶個人網絡上的點聚類問題，開發出一種檢測社交圈的模型，對于每個聚集可分析其成員以及特定用戶信息的相似性度量，通過對多重社交圈建立的點關系模型，可以發現重疊和分層嵌套的社交圈。

關鍵詞：社交圈；相似性；重疊

中圖分類號：TP393 文獻標識碼：A 文章編號：1009-3044（2017）36-0166-02

1 概述

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

2 擬解決的關鍵問題

每一個朋友圈都是他的朋友的一個子集，社交圈是特定于用戶的，因為每個用戶社交圈的好友都是獨立于與他沒有聯系的用戶。這就意味著可以把社交圈檢測描述為個人網絡和他朋友之間網絡關系的聚類問題。

本文研究如何自動發現用戶的社交圈問題，特別是給定某個用戶的個人社交網路，如何確定他的社交圈。如圖1所示，指定某用戶個體u，他的朋友vi形成一個網絡，定義節點vi為可變點，本文的任務是確定vi屬于哪個集合，進而發現個人網絡里嵌套和重合的聚類。

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

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

根據可變點之間的潛在變量和相似性構造聚集的從屬關系，并作為共同的配置信息。本文提出一種非監督學習方法來確定哪些維度的相似性會構成緊密聯系的聚集。基本思想是：借鑒Blau空間[5]概念思想，允許不同的聚集有不同的信息相似，因此一個聚集圈可能由一個學校的好友組成，而另一個聚集圈則是由來自同一個區域的好友組成。同時選擇聚集點成員和相似度函數來建模，從而以最佳方式解釋觀測數據。

3 社交網絡中朋友關系的生成模型

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

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

本社交圈模型將圈內成員視為潛在變量。落在公共圈里的節點通常有機會形成邊，這自然會導致社交圈的分層和重疊。本文整合潛在變量和信息相似參數，設計無人監督算法，以便更好地解釋觀測到的網絡數據。

5 結論

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

參考文獻：

[1] 曹懷虎，朱建明，潘耘，等.情景感知的P2P移動社交網絡構造及發現算法[J].計算機學報，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] 李陟，李千目，張宏，等.基于最近社交圈的社交時延容忍網絡路由策略[J].計算機研究與發展，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.