一种自动发现社交网络中社交圈算法的实验设计与分析

苏晓光 富春岩

摘要：本文对依据一种新颖的识别用户社交圈的方法所建模型進行了实验设计及分析。将朋友之间相互网络联系视为用户个人网络上的点聚类问题，同时结合网络结构和用户资料信息开发了一种检测社交圈的模型，对于每个聚集可分析其成员以及特定用户信息的相似性度量，通过对多重社交圈建立的点关系模型，可以发现重叠和分层嵌套的社交圈。通过真实数据来验证模型的性能，实验结果表明，本文所建模型可以准确识别社交圈中多样化数据的归属集合。

关键词：社交圈；聚类问题；分层嵌套

中图分类号：TP311 文献标志码：A 文章编号：1009-3044（2018）15-0045-02

1引言

如何组织庞大而凌乱的个人社交网络是具有挑战性的问题，社交网站允许用户手动将他们的朋友分配到各社交圈，如微信的“朋友圈”，人人网的“好友”等。用户借助社交网站来组织网络和交流，将朋友分类到所谓的社交朋友圈，几乎所有的社交网站提供了这样的功能。构建这样的社交圈不但要耗费用户大量的精力，而且随着用户社交圈的扩大，随时更新的代价惊人。目前构建如上社交圈的方法都不尽如人意，我们项目组在文献[1]中提出一种自动发现社交网络中社交圈的方法，通过在真实数据集上评估，与Streich等提出的多任务聚簇算法[2]，Yoshida等提出的低秩嵌入算法[3]，Balasubramanya和Cohen提出的block-LDA算法[4，5]进行对比，本方法依靠结合点和边的信息来预测多元朋友圈中的成员，具有良好的性能。

2实验用数据集

为了在真实数据集上评估非监督算法，本文从微信、Google+和人人网等三个主要社交网络获得个人网络和真实数据，包含193个朋友圈和4039个用户。我们开发了专门的微信应用程序对10个用户进行调查，要求他们手动确定其朋友应该属于哪个朋友圈。平均来说，用户大概会确定19个朋友圈，圈内成员平均22个。

从Google+上获得了133个个人网络，包括479个朋友圈和106674个用户。这133个个人网络代表了所有Google+中至少分享两个朋友圈的133个用户，并且这些人的网络信息是公开的。与微信上的朋友圈不一样，有些Google+社交圈的创建者已选择公开它们，Google+是一个有向网络。比如，一个圈包含2012年最有影响的歌星候选人，他们可能不会反过来跟随他们的粉丝。

从人人网上得到1000个个人网络，包括4896个圈和81362个用户，选的个人网络的大小是10到4964个节点。全部数据共有1143个个人网络，5541个社交圈和192075个用户。其中微信的数据是完全标记的，其本质上用户认为具有凝聚力的社区朋友圈，而Google+和人人网上的数据只是部分被标记，即只能使用公共圈。

3 构建特征集

所有的数据集信息都可以表示成一个树，其中每层编码表示越来越多的特定信息。对于Google+数据，从6个方面收集数据（性别、姓名、头衔、机构、大学和居住地）。对于微信上数据，从26个方面收集数据，包括籍贯、生日、同事、政治面貌等。对于人人网，简单地从两个方面收集数据，即两周内用户用到的组标签和提示。“类别”对应于概要树里叶子节点的父节点。

首先描述如何用一个差别向量为两个用户之间的关系编码。假设每个用户[v∈V]都有一个相关的信息树[Tv]，并且[l∈Tv]是树中的叶子。定义用户x和y的差别向量[σx，y]是一个二进制指示器反映x和y之间的差异：

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

上述差别向量在信息编码粒度方面有一定优势，但是它的不足在于维数太高（多达4122维）。解决这个问题的一种方法是基于叶节点的父节点来形成差别向量。对两个用户信息的共同类别进行编码，不考虑具体值。例如，关注编码两个用户共同拥有多少个标签，而不在乎到底是哪一个标签：

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

这种方案的优势在于它只需一个固定数量的维度，而不管个人网络的大小（如上所述，微信有26个，Google+有6个，人人网有2个）。

现在描述如何根据差别向量[σx，y]（和[σ′x，y]）得到边特征[?（x，y）]。希望构建的第一个属性是圈内的成员应该彼此有常见的关系：

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

第二个属性是圈内成员应该与个人网络的拥有常见的关系：

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

这两个参数允许评估哪种机制更适合捕捉用户对聚集的主观定义。两种属性都有一个常量特性“1”，用来控制用户在同一个朋友圈的可能性，或者度量哪个朋友圈在更大程度上由朋友组成。重要的是，即使某用户没有个人信息，仍然可以根据连接模式简单地预测他和其他用户的关系。类似地，对于“压缩”差别向量[σ′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 实验内容

本文通过真实数据检测收敛后潜在朋友圈[C={C1...CK}]的极大似然值，对一个适当正则化模型，潜在朋友圈应该极大程度上与手工表明的圈[C={C1...CK}]接近。

为了衡量[C]和[C_]的接近度，计算两个集合的平衡误码率（BER），[BER（C，C）=12（|C＼C|C+|C＼C|C）]。这种方法使伪真和伪假处于同等重要地位，所以细微或随机预测造成的误差平均在0.5。

由于不知道[C]和[C]的吻合度，通過计算线性最大值来得到最优匹配：

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

这里f是[C]和[C]的对应，即如果[C]的个数[|C|]小于[C]的个数|[C]|，那么对于每个c[∈C]，一定会有一个匹配的[c∈C]，但是如果[|C|]>|[C]|，则没有额外的匹配。另外可以利用最大似然等成熟技术估计朋友圈的个数。

将本文的方法与三种方法进行对比，第1种是Streich等提出的多任务聚簇算法，记为“聚簇”；第2种是Yoshida等提出的低秩嵌入算法，记为“低秩”；第3种是Balasubramanya和Cohen提出的block-LDA算法，记为“LDA”。本方法在朋友对朋友特征情况下的运行（?1=12），记为“F2F12”，本方法在朋友对用户特征情况下的运行（?2=13），记为“F2U13”，本方法在压缩特征情况下的运行（ψ1=14），记为“C114”，本方法在压缩特征情况下的运行（ψ2=14），记为“C214”。图1给出了各算法在微信、Google+、人人网数据集上检测社区精度的对比结果。

根据式（6）描述朋友圈，并计算圈子的个数，平衡错误率值（BER）越高性能越好，图1中柱状条表示标准错误率。本方法在最好特征值?情况下的运行精度与最接近的竞争者的差异为1%，此时BER的得分情况是：微信为0.84，Google+为0.72，人人网为0.70。在Google+和人人网上得分较低的原因是：由于最初创建用户，没有保持许多社交圈，可达到较高的回忆值（在每个圈里重新获得朋友），但是预测的精度较低（在朋友圈已建立后出现的额外的好友）。从实验结果可以看出，本方法良好的性能主要依靠结合点和边的信息来预测多元朋友圈中的成员，目前还未见其他方法应用到这种结合。

5 结论

实验结果表明，依据提出方法所建模型可以准确识别社交圈中多样化数据的归属集合。模型根据前述方法确定社会维度。通过实验发现，所有的算法在微信上操作都要比在Google+和人人网上要好。不仅提高了检测精度，还可以对某个节点为什么是属于某个聚集的进行解释。

参考文献：

[1] 于占龙，董丽新，陈玉林，等. 一种自动发现社交网络中社交圈的方法[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.