于占龙　董丽新　陈玉林　富春岩　周虹　支援　曲思龙

摘要：该文提出一种新颖的识别用户社交圈的机器学习方法，将朋友之间相互网络联系视为用户个人网络上的点聚类问题，开发出一种检测社交圈的模型，对于每个聚集可分析其成员以及特定用户信息的相似性度量，通过对多重社交圈建立的点关系模型，可以发现重叠和分层嵌套的社交圈。

关键词：社交圈；相似性；重叠

中图分类号：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.