社交圈子发现

自我网络研究

摘要

人们的自我网络很大，并且很杂乱，目前没有一种有效的方式来对自我网络进行组织。社交网站允许用户把他们的朋友以及亲人手动分配到他们的社交圈子里。（比如在google+，推特或者是脸书上），但是，当网络用户量增加的时候，他们必须对他们自己构建的社交圈子进行更新以及重新构造。在本文中，我们研究了一种自动识别社交圈子的方法，我们提出了一种利用聚类的方法对用户的个人网络中的互相之间的关系进行分析，并且还开发出了一个模型来检测圈的结构以及圈中的用户信息。对于每一个圈子，我们都要了解圈子中的成员以及确定用户的轮廓相似性度量。这个模型允许节点也就是用户存在于多个圈子，也允许圈子的重叠以及分层嵌套。实验表明，我们的模型能够准确的从各种社交网络上准确的识别不同的数据，并且我们所用的都是真实的数据。

1、介绍

线上的社交活动允许我们能够浏览我们的成千上百的朋友以及熟人所发的帖子。这些我们所关注的人能够产生海量的信息，我们必须采用适当的方法来处理这些过量的信息，并且我们应该把我们的这些朋友分类到我们称之为社交圈的圈子中。几乎所有的社交网络都有上述的功能，例如facebook以及推特。一旦用户创建了他的社交圈，他们也就能够对内容过滤、对隐私进行保护、以及与其他希望跟随他们的帖子的人建立交流小组。

一个个人网络的例子如图1所示。这些网络的所有者可以通过与他们所关注的人的共同的节点或者属性来形成一个新的圈子。在这个例子中，社交网络的所有者只是想要与他在科学社的朋友们一起分享TDKK的文章，并且只想与他们的家人分享家里宝宝的照片，同时还不想让他们的高中同学发的内容在主页上显示太多。这些就是我们所谓的社交圈的功能。

图 1 社交网络例子

图1：这是一个带标签个人网络。社交圈的主人与圈中的每一个人都是好友的关系。每个人都可能属于任何一个圈子，也可能没有圈子。我们旨在发现圈中的成员并且找到一个圈中的成员的共同属性。这个网络展示了我们的数据中的一种典型的行为：大约有百分之25的我们的社交圈完全被包括在其他的圈子中，大约有百分之50的圈子与其他的圈子有重叠，还有百分之二十五的圈子与其他的圈子没有任何交集。

现在，这些社交网络上用户通过手动的方式或者天真的通过他们的朋友的共同属性来划分他们的社交圈子。不论哪一种方法，都达不到一个特别令人满意的结果：第一种方法费时费力，而且当用户的朋友增加的时候他没有一种自动更新的机制，而后面一种方法不能补货用户的社交团体信息，并且当信息丢失的时候就可能不能完全的实现他的功能。

在本文中，我们研究自动发现用户社交圈的问题。也就是说，如果给我们提供了一个个人社交网络，我们的目标就是去识别他的圈子，并且每一个圈子都是由他的朋友组成的。

圈子是用户指定的，就像每个用户都会完全独立于其他他们自己不联系的陌生人来组织他们自己的个人网络，这就意味着我们可以完全在他自己的个人社交圈中来讨论这个社交圈检测的问题，而不用考虑其他的陌生人。在实际操作中，这些社交圈可能会重叠，比如说一个同乡的人也可能是你的大学同学，或者是分层嵌套的，比如说在你的大学同学里肯定还有一部分人跟你是一个课题组的。我们把这些所有的情况都要考虑到我们的模型当中。

在图1中，我们了解到了一个个人用户，称为U，并且我们与他的朋友Vi生成了一个网络。我们把这个用户U作为自我，把节点Vi作为变量。接下来的任务就是识别每个Vi属于哪个圈子，换句话说，我们的任务就是找到U的个人网络的社交团体。

一般的，有两种有用的数据源对这个任务有所帮助。第一个是这种个人网络的边缘设置。我们希望我们的圈子必须是由与圈子的主人密切联系的变量形成的。然而，不同的圈子重叠的很厉害，而且变量同时属于多个圈子，并且很多圈子都多层嵌套在一个大的圈子里。为一个变量的圈中关系建模是十分重要的。第二，我们希望我们所形成的圈子中的成员不仅要互相之间密切的联系，而且需要有共同的特性。这样我们就需要针对每个圈子准确的建立不同规模的用户轮廓。

我们把重叠的圈子作为一个潜在的变量或者是变量之间共同轮廓功能的相似性。我们建立一种自学习方法去学习能够导致密切联系圈子的相似性规模。在建模解决这个问题之后，我们接下来要处理的问题就是当一个新的朋友被加到这个网络当中时，如何能够准确的更新我们现有的圈子信息。并在根节点的形式下用一个用户弱监督的方法提升分类的效率。对于前一汇总问题，我们展示的方法是已经定义好的用户圈子，而且我们可以准确的预测出每一个用户应该属于那个圈子。对于后一个问题来说，我们展示的方法是用户提供的每一个根节点都提高了分类的准确性，虽然从本质上说，2——3个节点就已经可以使得准确性得到一个很大的提高。

我们的模型有两个创新，第一，在对比混合关系模型时，我们能够预测一个节点应该属于哪几个圈子。第二，通过提出一个相似性轮廓的定义参数，我们可以了解相似性节点的连接显露出来的圈子的规模。这就扩展了一个同质性的概念，具体的方法就是允许不同的圈子形成不同的社交规模。我们通过定义不同的轮廓相似性概念来达到这一目的，这样我们就能形成校友的圈子以及同乡的圈子等等这样的社交圈。我们通过同时选择节点圈子关系以及轮廓相似性功能来了解这个模型，从而能够更好地解释我们得到的数据。

我们从许多社交网站上引入了1143个个人社交网络的数据，我们得到了5636个个人网络的圈子信息。实验结果表明：在同时考虑到个人社交网络的结构以及用户的轮廓信息时，我们的方法比自然选择的方法更加有效。而且由于我们的方法更加准确，这就使得我们能够可以生成对节点为什么属于特定的圈子的自动解释。我们的方法完全是无监督的，并且能够自动决定圈子的数量以及圈子他们自身。我们通过实验证实了相同的模型可以处理弱监督的的问题，而且可以处理对于一个已经存在的个人网络中新节点要加入的情况。

1.1 更深入的相关研究

虽然说一个圈子不能完全说是与社团完全一样，但是我们的工作十分依赖于社团的检测。虽然古典的聚类算法会假设将社团分解开来，但是许多的作者已经发现真实世界中的社团可能会发生十分严重的重叠，或者具有分层嵌套的结构。

主题建模技术已经被用来揭露节点在多个组中的混合成员关系，并且扩展功能允许实体分布于文本信息中。已建模的节点可以作为边缘分布的一个潜在变量，这样每一个属性能够被看作是对于一个团体的局部成员关系。其他的一部分作者延伸了这个想法，使得边信息与节点和边缘所关联。有一个作者用了潜在节点的属性来建模相似节点的边缘信息。

古典的聚类算法倾向于基于节点的特征或者是图表结构来鉴别社会团体，但是都用的不多。我们的工作就形成社交网络数据的积累而言与Yoshida相关，在多团体的成员关系建模方面与Frank等相关。另外一个跟我们类似的实验室Yang和Leskovec，他们明确的对多圈子重叠的节点关系进行了建模，但是它纯粹依赖的是网络信息而不是节点的性质。我们的推理形式与Hastings是类似的，吧节点按照相关节点的最大后验参考问题进行分配至指定的圈子。

最后，这些人都与我们使用了类似的建模方式，就像我们自己的工作一样，他们把两个节点能够形成边缘的可能性进行建模，然而潜在的节点是不能形成团体的，因此他们的方法都不能马上解决圈子探测的问题。

本文剩下的内容主要是包括了以下几个方面：在第二章我们得出了一种社团内边形成的产生算法。在第三章，我们得到了一种有效率的模型参数学习策略。在第四章，我们扩展描述了我们的方法可以在半监督设定的条件下运行，可以帮助用户更新和维持他们的社交圈子。在第五章，我们描述了我们的数据集。我们提出了两种方案针对自动构建从第六章获得的概要数据获得的用户相似性功能。在第七章中，我们展示了怎样去构建一个大的个人网络的模型。最后，在第八章中，我们描述了我们的评价和实验结果。

2、社交圈的朋友关系的产生模型

社交圈模型有以下的性质：

1、 在圈中的节点必须有相似的性质或者方面

2、 不一样的圈子应该是有不一样的方面或者性质形成的，举个例子，一个圈子可能是因为家庭成员的关系形成的，而另外一个圈子是因为大学校友的关系形成的。

3、 圈子应该允许重叠现象的发生，并且更加强壮的圈子应该能够形成弱的圈子，举个例子，一个相同学位项目的同学圈子可以是有相同大学的校友所形成的。

4、 我们将要利用轮廓信息和网络结构去辨别社交圈。

5、 理想情况下，我们应该能够查明每个圈子形成的共同属性或者是共同的方面，以至于用户来书是可说明的。

我们的模型的输入是一个个人网络G=(V,E)，其中的每个用户都属于V。个人网络的中心节点不属于在G中，G完全是由u的朋友也就是那些变量所组成的。我们用这种方式精确的定义个人网络，因为社交圈的建立者不会出现在他们自己的圈子里。对于每个个人网络来说，我们的目标是预测一个圈子的设定C={C1……C2}，Ck属于V，并且将圈子设定与参数向量θk联系起来，这个参数向量可以编码圈子是如何形成的。我们将用户轮廓编码成为成对的属性值φ（x,y），在某种程度上捕获什么样的属性在x和y上是一样的。我们首先描述我们的模型，模型可以用来适用在任何的特征向量φ（x,y），在第六章中，我们提出了几种构建特征向量的方式，来适应我们的特定的应用情况。

我们在本文中描述了一种把圈子中的成员关系作为潜在变量的模型。在一个普通的圈子中的节点有机会形成一个边，这种边可以自然的生成重叠和分层的圈子，我们设计一个无监督的算法来连带的最优化这些潜在的变量，同时，轮廓相似性参数也可以最好的解释我们观察到的数据。

我们的社交圈模型就像下面的公式一样，已知有一个个人网络G和一个K集，包括K个圈子C={C1,C2……Ck}，我们把属于V*V的一对节点（x,y）形成一个边的概率建模为下面的一个公式：

对于每个圈子Ck，θk是我们将要学习的轮廓相似性参数。我们的想法是这样的，（φ（x,y）, θk）的值当两个节点都属于Ck中时高，如果两个节点都不属于Ck中时低。参数αk权衡这两种结果，它权衡边在Ck中和不在Ck中的影响。既然特征向量φ（x,y）编码两个节点x和y的轮廓相似性，而参数向量θk是圈子应该形成什么规模的轮廓相似性的编码，这样就导致了在一个圈子的当中的节点应该依照θk而看起来是类似的。注意在非定向的网络情况下节点对（x，y）应该被当作一对无序对例如fecebook，而在定向网络情况下应该将其看作有序对。例如推特

考虑到边e=(x,y)是独立生成的，我们可以把G的概率写成

Θ={(θk,αk)}的{k=1,2……k}次方是我们模型参数的设定，定义以下速记符号

允许我们可以去写出G的对数似然函数：

而Z=（1+e^φ（e））是一个标准化常量。

下面，我们将要描述怎样使节点圈子关系C最优化以及用户轮廓相似性功能参数，Θ={(θk,αk)} {k=1,2……k}，一旦我们被给了一个图表G和用户轮廓的话。

3、模型参数的无监督学习

将圈子C作为一个潜在的变量，我们旨在找到使得G的似然函数最大化

（4）

我们解决这个问题用的上升坐标：

（6）

我们用L-BFGS使（6）最优化，L-BFGS是一个类似牛顿的过程，这个过程可以使得许多变量的函数尽可能的平滑。局部的中间变量如以下所示：

对于固定的C\Ci，我们要注意解决以下问题：能够被表达为伪布尔数学体系在成对的图解体系中的最优化问题。伪布尔数学体系最优化指的是把问题定义在布尔变量之上（在这种情况下，无论节点是否被设定在一个特定的圈子里都要这么定义），在关系被定义在一个图表的边之上的情况下，变量的最优化是互相影响的。简而言之，我们的最优化问题可以被写成以下形式：

虽然说这个问题一般情况下是NP问题，但是有效地估计算法也是很容易得到的。在我们的设定中，我们想要让高权重的边出现在Ck中，权重低的边不出现在Ck中。定义如下：

通过用这种形式表达这个问题，我们能够在伪布尔数学体系最优解上利用我们现有的工作。我们用现有的叫做“QPBO”的软件以及工具算法，他们可以准确的近似Ck的近似问题。本质上，上面的Ck的等式的问题呗减少为最大限度跟随的问题，在这个问题上每个节点的布尔标签是被他的源节点和下面的节点设定的。这种算法的时间复杂度为O（N^3），虽然这种算法的平均状况下的运行时间是远远好于这个数量级的。我们以随机的算徐解决上述的Ck等式问题。

最优化的两个步骤C^t和（6）在聚合之前是一直重复的，直到C^(t+1)=C^t。整个程序被呈现在算法一中，我们用L1规范调整（4），即：

这就导致了稀疏的和易说明的参数。我们的算法可以轻易的处理所有的情况除了我们在个人网络当中能够观察到的最大尺寸的情况：例如facebook，平均的个人网络有190个节点，然而我们所观察到的最大的节点数量为4964个。而后，在第七节中，我们将会利用许多节点共享相同的特征以及我们所讨论的特征是二进制的这一事实来提出一个更有效的算法基于MCMC理论。注意由于方法是无监督的，每一个个人网络的推论是独立推演的。这就意味着我们的方法能够在全部facebook的图表上运行，就好像对于每个用户来说，圈子都是独立探测的，个人网络的圈子一般只包含几百个节点而已。在第四节，我们描述了我们的方法是如何在半监督的情况下工作的。

3.1 Hyper参数估计

为了选择最佳的圈子数量，我们选择K作为一个最小的近似值。BIC作为一个定义如下：

在这其中是预测什么时候出现K个圈子的参数值，而是这个参数的值，这个值随着K的增长呈线性增长，然后我们要选择一个可以使得如下值最小的K值：

（11）

算法一如下所示：

换句话说，如果将某一个额外的圈子添加到模型中可以对对数似然函数产生比较明显的影响的话，这样的圈子才能够被添加进去。

规定的参数是由交叉验证的方法来确认的，虽然在我们的经验中这些参数之间是不会有十分明显的影响的。

4、扩展

至今为止，我们已经考虑了在只有节点属性和边缘信息的情况下预测整个圈子设定的冷启动问题。换句话说，我们已经把圈子预测变为一种无监督的任务模式。一方面这种设定是现实的，在用户只在他们的个人网络被定义了之后再进行圈子的构建。另一方面，在用户不断递增的建造他们的社交圈子的设定中，我们用这种方法是不切实际的。我们必须注意我们的这些设定都必须在我们所讨论的三种个人网络中。

在这个部分，我们所描述的技术将会有一部分去观察圈子的信息来帮助用户更新以及控制他们的社交圈子。换句话说，在用户将要改变或者改进他们的社交圈子的时候我们将会提供给他们我们的模型。既然我们的模型是概率性的，那么我们就可以通过我们的模型的潜在变量来设定调节从而使得我们的模型可以将我们观察到的数据运用充分。通过这种方式，我们可以将我们的模型运用于半监督的设定，在我们检测一类用户或者是他们的圈子成员时。然后，在第七节，我们描述了我们模型的改动，改动之后模型可以适应很大的个人网络，原理是许多用户设定共同的圈子都有相同的属性。

4.1 圈子维护

首先，我们处理了一个新的节点如何加入一个已经建立完成的个人网络，这个个人网络的圈子已经被定义好了。这样，在一直一个完整的圈子设定之后，我们的目标是预测一个新的节点的团体成员，基于这个节点的特征以及这个节点与这个圈子中的其他节点的连通性。

既然圈子在这个设定下是完全被观察到的，我们可以简单的自适应一个最能够解释真实圈子的模型参数：

就像（6）式中一样，这个等式是用L-BFGS技术解决的，虽然优化过程在没有更多的潜在团体需要推导的情况下更快，并且这样的协调上升不是必须的。

下一步，我们必须预测新加入的节点u是属于哪个圈子的。我们需要预测，其中每一个都是一个可以表明是否一个用户u应该属于这个圈子Ck的二进制变量。实际上，为了估计，我们会废除一个单独的用户从G中以及中，并且尝试着覆盖他们的成员关系。

这个过程可以通过选择在u被加入到图表中时使得C的对数似然函数最大化的C^u来完成。我们定义增加的社团成员关系为，在这其中

更新的团体成员关系是根据以下等式得出的：

上面的表述可以独立并且有效的计算对于不同的C^u的值，对数似然函数只有在包括u的情况下才会改变，这就意味着我们只有在x=u,或者y=u的情况下才计算（x,y）∈E的概率。换句话说，我们我们仅仅需要考虑新加入的阶段与现有的节点有什么关系，而不是考虑原先存在的节点之间是如何互相影响的。这样，计算对数似然函数是一个线性的时间，而不是几何倍数增长的时间。为了能够找到最理想的C^u，我们可以简单的列举所有的2^k种可能性，在我们又小于等于20个圈子的时候，这种方法是可行的。如果对于更多的圈子，我们就必须依照在第三部分提出的迭代的方法了。

4.2 半监督圈子的预测

下面，我们考虑一种以种子节点的形式来协助预测的弱监督问题，在这种设定下，用户手动的从他们想要创建的圈子里标记一些用户，叫做{S1,S2……Sk}，我们的目标是预测K个圈子使得圈子服从Sk∈Ck的约束。

同时，既然我们的模型是概率性的，这样的过程就可以通过调节我们模型中的隐藏变量来完成。我们简单的最优化使得服从Sk∈Ck的条件。在图表形式的模型的说法中，这就意味着我们不是将种子节点当做需要被预测的隐藏变量，而是将他们作为我们决定的条件。我们也能够保罗否定的证据：即用户提供肯定不会包括在圈子中的节点，或者我们能够让用户提供更多的交互式的标签，虽然被描述的设定是与实际应用中最相像的。

图2：圈子之间的重叠柱状图。零值代表了该圈子与其他的圈子完全没有任何交叉，而百分之百的值代表了一个圈子与另外的一个圈子完全重合。大约有百分之25的圈子会有后面的一种情况。

5．数据集描述

我们的目标是评估我们的方法在实际数据上的效果。我们花费了很多时间，经历还有资源来得到高质量的数据。这些数据我们已经放在了网上供大家下载。我们能够从上面提到的三个社交网站上获得我们所需要的数据。

从facebook上我们获得了轮廓和网络数据从10个个人网络中，包括193个圈子和4039个用户。为了获得圈子信息，我们发布了我们自己的facebook应用并且对这十个用户做了调查，他们被要求手动的分配好他们的朋友圈。这花费了他们每个人2到三个小时。平均状况下，用户会将他们的个人网络分配19个圈子，每个圈子的大小大约在22个朋友的样子。这些圈子包括大学同学圈子，亲人圈子等等。

图2中展示了我们的样本中的193个用户标记的圈子的重叠程度。大约有四分之一的圈子是完全独立于其他的圈子的，然而有相同数量的圈子是完全包含在其他的圈子里面的，举个例子，在同一个导师下的学生圈子是完全包括在大学校友圈子中的。剩下的百分之五十是与其他的圈子有部分重叠的情况。

另外两种数据源的情况：从GOOGle+，我们得到了133个个人网络的数据，包括479个圈子以及106674个用户。这133个个人网络代表了这133个用户至少会重叠两个圈子，并且这些网络信息都是可以再网上下载的。Google+的圈子是与fecebook有很大差别的，因为GOoogle+的建立者都将他们公开的释放出来，并且Google+是一个直接网络（注意，我们的模型可以运用在直接网络和间接网络山）。最后，从推特上我们获得了1000个个人网络的数据，包括4869个圈子，以及81362个用户。我们得到的个人网络的大小从10个到4964个节点不等。

总的来说，我们手头共有1143个不同的个人网络，5541个圈子还有192075个用户。这些数据源的大小不同反映了数据获得的难易程度不同。我们的facebook数据时全标记的，意味着我们得到的每一个社交圈子都是一个紧密结合的团体，然而，我们的Google+以及推特的数据仅仅是部分标记的，这意味着我们仅仅有公共社交圈子的进入权限。我们将我们的评估过程的设计展示在第八节中，这样部分标记的技术就不会引起争议了。

6 从用户资料中构造特征

在我们的数据源的资料信息中，所有的信息都可以被表示成为一个信息树，树的每一级都会被编码成为更加明明确的信息，换句话说，用户文件被组织成为更加明确的分类，举个例子，一个用户的信息中可能包含有教育分类的信息，这些有关教育的信息可以更加明确的分类依照姓名、地点或者是类型等方面。而这个信息树的叶子可以看做是这些分类的精确值，举例：清华和北大都是大学的分类下面的值。某些工作是可以从结构树的数据中自动处理构造特征的，但是为了理解圈子和用户信息的关系我们将要构建我们自己的特征表示形式。

对于用户怎么组织他们的社交圈子，我们现在又两个假设：其中一种是他们可能从用户周围的圈子中选出用户与这些圈子中的共同属性来构造新的圈子，另外一种是他们会从用户周围的圈子中找出这些圈子之间的共同属性来构造圈子。举个例子，如果一个用户有许多的斯坦福大学的朋友，那么他们可能会形成一个斯坦福的圈子。另外一方面，如果他们自己没有在斯坦福大学，那么他们可能就不会把斯坦福大学作为一个显著地特征来考虑。这种特征构建计划可以让我们明白哪一种假说对于我们所得到的数据来说是最好的。

从Google+，我们从六类数据中收集数据，分别是：性别，形式，工作主题，体系，大学以及住址。从Facebook上我们从26类数据上收集数据，包括用户的家乡，生日以及同行，政治立场以及宗教等等。作为一个数据源的代表，我们从推特上收集的数据是从两类数据中中收集的，即用户的标签以及用户在过去两周提到的关键词。分类的情况应该与结构树种的父亲节点以及叶子节点想符合。

我们首先会假设一个不同的向量来表示两个用户文件之间的关系。有关这一点，figure3中有个非技术性的描述。本质上说，我们想要描述两个用户的相似程度，比如说小明和小红在同一所大学上学，还有他们的不同的程度，比如说他们的名字不一样。假定用户每一个v∈V都与文件结构树Tv有关联，同时l∈Tv是这个树上的叶子节点。我们定义不同的向量在x和y之间作为一个二进制的指示值来表示用户x和用户y不同的方面：

注意，这种特征描述只定义在每一个个人网络中：虽然成千上万的高中存在于所有的fecebook的用户上，但是仅仅有一小部分是所有用户的朋友。

虽然上述的差异向量有将文件信息编码成一个好的粒度的好处，但是同时他的缺点在于他的规模比较大，我们认为最多能够达到4122的分布规模。解决这个问题的一种方法是我们依照叶子节点的父亲节点来形成我们的差异向量：通过这种方式，我们编码了两个用户相同的文件类别，但是却忽视了特定的值。举个例子：我们统计了两个用户有多少次发了同样的微博，但是不统计他们发的微博是什么：

这种计划有明显的优势在于：他有一个恒定的分布规模，不管个人网络的大小如何。（facebook有26个，Google+有6个，推特有两个）。

基于差异向量，我们接下来描述怎么样构建边的特征，称作。我们想要建模的第一条性质是权重的成员应该与彼此有共同的关系：

我们想要建模的第二条性质是圈子中的成员应该与个人网络的主人有共同的关系。在这样的条件下我们再从个人网络中的主人u中考虑文件树Tu。然后，我们会依照用户的以下关系来定义特征：

这两个参数化的形式可以使得我们了解哪一种原理能够更好的捕获用户对于一个圈子的主观定义。在这两种情况下，我们包含了一个恒定的特征（l），表示了一个边在圈内形成的概率，或者相当于他表示了圈子由朋友形成的程度。尤其注意：这种方式使得我们可以预测没有用户文件信息的关系，依靠的仅仅是他们的连通模式。

类似的，对于压缩的差异向量，我们定义：

总的来说，我们已经定义了四中方式来表示两种用户的用户文件的不同的方面。我们形成了两种构建差异向量的方法以及两种捕获用户文件之间的兼容性的方法。我们设计的特征来建模以下的行为：

1. 个人用户围绕他们的朋友之间的共同关系建造圈子。

2. 个人用户围绕他们的朋友与他们自己的共同关系来建立圈子。

在我们的试验中，我们探究了哪一种假设在实践中更实际。

7.大的个人网络的快速推理

虽然我们的算法可以处理我们在个人网络上典型的网络规模的数据（少于1000个朋友），现在扩展到更大的网络规模成为摆在我们面前的一道难题，我们需要几何倍数的存储器来保证我们能够每一个节点之间的兼容性（这个问题在第八节也是我们要考虑的一个问题）。在本节，我们假设一个更具可扩展性的网络，证明属于共同团体的很多节点同样也共享共同属性。

在第六节中我们描述的，是个二进制的变量，正如团体中的成员关系，如果有K个团体并且有F大小特征，那么最多就可能有2^(K+F)种节点类型。换句话说，每一个节点的社团成员关系都是依照{0,1}^K得来的，并且每一个节点的特征向量是由{0,1}^F得来的，因此，有最多2^(K+F)明显的团体或者特征组合。当然，节点类型的数量也是由V来限制的，V是图表中节点的个数。

然而在实际操作中，节点类型的个数往往是比较少的，因为属于同一个团体的节点往往具有共同的特征。团体的成员关系也不是独立的：在Figure2中，我们同时观察了不相交的以及分层嵌套的团体，这就意味着会有2^K这么多的成员关系，结果只会有其中的一部分出现在实际操作中。

在本节中，我们假定了一个马尔科夫链取样器，这个取样器可以通过压缩有共同的特征以及成员关系的节点来有效地更新节点团体成员关系。注意这种改编可以针对所有形式的特征而不仅仅是二进制的特征，我们需要的条件是有很多的用户共享相同的特征；我们设定二进制的特征仅仅为了展示的目的。

我们用二进制的字符串来表示节点的团体成员关系以及他的特征。每一个节点的团体成员关系式用来代表的，

类似的，每一个节点的特征是用二进制字符串Q来表示的，而既然我们的特征都已经用二进制来表示了，这个Q值就与我们的特征规模相互联系起来了。

现在我们要说明的是一个节点X的类型是他的团体字符串以及它的特征字符串的连接点，（S(x);Q(x)），并且我们建立了一个系数表格类型：，这个值表示在每个类型下面有多少节点存在。

在我们设定下，MCMC包括反复的更新在一个特定团体换种的每个节点的二进制标签。明确的，如果一个节点x属于k团体的边缘可能性是由给出的，然后节点的新标签是通过抽样选择的，并且在T是一个温度参数并随着每一次反复是回降低的地方进行更新。

这样我们就更可能选择到使得模型变量的标签。

计算（节点x在团体K中得到0或者1标签的概率）需要。但是我们要注意如果两个节点y和y’有相同的类型（即他们有相同的团体和相同的特征），那么p((x,y)∈E)=p((x,y’)∈E)。为了观察得到数据的似然函数，我们也必须考虑是否（x,y）和（x,y’）是图表中真正的边。为了能够达到这个目标，我们首先在假定没有任何一条边穿过x的条件下计算。在这之后我们再为那些穿过x的边进行适当的调整。这样个人网络的更新就与明显节点类型的数量是一个线性的关系了，在加上平均节点的密集程度，以上提到的两点都是由节点数量限制的。

整个的程序在下面的算法解释中演示出来：

当我们计算部分似然函数的时候也会运用相同的观察方法，我们首先会在图中不包括边的情况下有效地计算推算结果，然后再依照图中所有的边逐个修改结果。

8.讨论和未来展望

在本文中，我们模拟了用户社交圈子检测的问题，我们的方法可以适用于任何一个独立用户。这种思路使当我们要处理数以百万计的用户节点时，我们可以提出一种假设，即我们可以把一个比较大的课题分为独立的几个小问题来单独处理。但是，如果可以考虑到多个圈子之间的关系那么我们的圈子检测技术将会更加精确。举个例子：有一个斯坦福大学圈子中的用户节点，那么这个节点自身的个人网络也可能会有一个叫做斯坦福大学的圈子。通过重复这种操作，如果能够在整个社交网络上探测斯坦福大学这个社区，那么每个用户的斯坦福大学这个社交圈子就可以简单确定了。虽然实现这样一个模型是十分诱人的，但是很遗憾的是，我们不肯能得到全网范围内所有斯坦福大学的圈子，这样的数据量太庞大了。

虽然我们的模型可以使用在任何规模的社交网络中，但是经过试验发现，模型在几百规模的数据量下可以很好的发回作用，而在几千规模的数据量下会有一个明显的效率下降。这仍然是我们的模型算法的一个缺点，我们的算法在大规模的数据量下会崩溃，这都是因为对大规模数据量的最优化处理十分困难。在这里我们只能假设所有的用户社交圈子都是由若干个几百规模的社交圈子组成的。

我们还同时发现，对于超过1000个节点的大数据量，我们的模型方法在Facebook上表现的比另外两种主流的社交网站上更好。这就说明影响我们的方法效率的不仅仅是数据量的大小，社交网站的不同也是一个非常重要的因素。我们在FaceBook上获取的数据时跟另外两种平台上获取到的数据完全不同。所以未来我们需要设计一种算法来适应不对称的社交关系。

9.结论

虽然构建起来很费时费力，但是社交网络圈子使得我们可以处理由我们的社交网络而产生的巨大数据量。我们设计了一种可以检测个人网络的社交圈子的算法，可以处理1143个个人社交网络以及5541个圈子，这些数据都是从FaceBook或者谷歌推特上获取的。并且，我们发现这些社交圈子有分离、重叠或者是层次嵌套的行为。我们的方法是无监督的，但是同样可以使用含有标签的数据。实验表明，我们能够结合社交网络和轮廓信息两方面的信息来准确预测社交圈子。

本文来源：https://www.2haoxitong.net/k/doc/3c8e8b7052ea551811a6870a.html