0
| 本文作者： 奕欣 | 2017-09-20 10:36 |
雷锋网AI科技评论按：微信群是目前我们最常用的多人聊天方式之一，不过在习以为常的建群拉人过程中，一个有意思的问题是，一个微信群建立起来了，根据社会关系所构建起来的网络关系，谁更可能是下一步被邀请入群的人呢？来自清华大学的唐杰团队和腾讯公司一起对这个问题进行了深入细致的研究，工作发表在IJCAI17上，论文题目为《Who to Invite Next? Predicting Invitees of Social Groups》，作者包括韩矞（清华），唐杰（清华），叶浩（腾讯），陈波（腾讯）。雷锋网邀请第一作者韩矞对论文进行了解读。
论文地址：https://www.ijcai.org/proceedings/2017/0519.pdf
该工作基于微信平台研究群组邀请问题，就是预测针对某一个群，哪些人会被邀请至这个群。针对这个问题，我们先来看下面一个例子。
图 1
上面这张图表示某一个时刻的一个社交网络的群组及其相关的用户，比如我们可以把它看作一个微信聊天群，每个头像表示一个用户，用户之间的边可以看作微信好友关系。处于蓝色圆圈内的用户是这个微信群的成员，我们把不属于微信群但与群成员有好友关系的用户称为这个群的「边缘用户」，也就是问题中的可能被邀请者。那么根据这张图展现的网络结构关系，我们直观地感觉哪一个用户将会在下一个时刻被邀请？也许用户 A 的可能性大一些，因为他有三个好友在群里。那么再提一个问题，如果用户 B 在下一个时刻被邀请入群，那么谁更可能会被邀请入群？结论也许是 C，因为 B 与 C 有两个共同好友。这给我们解决预测被邀请者提供了一些思路，不过我们还是需要在实际数据上验证我们的直觉。
我们在真实的微信社交平台上提取了数据进行观察。我们提取了微信在半个小时内新建的有名字的群进行研究，共涉及到了 300 多万个用户，400 多万条边和将近 100 多万条邀请记录。为了分析群组的变化过程，我们在群组产生时刻到一后之间的时间段中设置了 7 个观察点进行观察，分别是群组新建后的半小时，1 小时，3 小时，24 小时，1 个月，3 个月，6 个月以及 1 年后。见下图：
图 2
图 2（a）表示的是群组成员数一年的变化情况。我们以最后一个观察点为基准，计算之前每个观察点的群组成员数的百分比。横轴是时间轴，纵轴是百分比。为了更好展示群组在前四个观察点的变化情况，我们专门把前四个观察点画在图 2（b）中。我们可以看到，群组随着时间变化呈现出不断增大的趋势，而且时间越靠前，增大速度越快，时间过去越久，增大速度越慢。而随着微信群的增大，用户被邀请进群的概率也随之变小，如图 3 所示。
图 3
图 3（a）表示的是用户被邀请入群的可能性随时间变化的情况。同样，图 3（b）是前四个观察点的放大版。所以我们可以得出一个结论，从群的整体属性角度讲，它会对用户的入群可能性产生影响。
接着，我们进一步观察用户之间的互相影响。我们先设想如果两个边缘用户针对某一个群具有某种相近性，那么我们就可以认为这两个用户针对这个群的被邀请可能性具有某种相关性。也就是说一个用户被邀请后，另一个用户随即也会被邀请。我们把这种用户称为这个群的「伙伴边缘用户」。为了更量化地分析这种相关性，我们这里定义两种伙伴用户。第一种是这个群的两个边缘用户具有好友关系。第二种是这个群的两个边缘用户有不止一个共同好友是这个群的成员。如图 4 所示：
图 1 中，用户 D 和用户 E 属于第一种伙伴边缘用户，而用户 B 和用户 C 属于第二种伙伴边缘用户。图 4 量化展示了这两种用户被邀请入群的可能性。
图 4
图 4 中，红色柱体代表用户的平均入群概率，黄色柱体代表第一种伙伴边缘用户在有一个用户入群后另一个用户入群的可能性，蓝色柱体代表第二种伙伴边缘用户在有一个用户入群后另一个用户入群的可能性，蓝色柱体下面的数字标号代表这两个用户在群中的共同好友个数。我们可以看到，这两种伙伴边缘用户的入群可能性要远高于平均可能性。
我们还有一个假设是如果一个用户和一个群越「亲密」，那么这个用户被邀入群的可能性就越大。为了验证这个假设，我们先定义两个指标来衡量这种亲密程度。第一种是群成员中用户的好友数，第二种是群成员中用户的邻接三角形数（即用户的邻接闭三角形中另两个节点在群中）。例如图 1 中用户 A 的第一种指标值是 3，第二种指标值是 2.
图 5
图 5（a）所示的是用户第一种指标的可能性。横轴是用户的群成员好友数，纵轴是入群可能性。图 5（b）展示的是用户第二种指标的可能性。横轴是用户群成员邻接三角形数，纵轴是入群可能性。很明显，对于这两种指标，都是值越大，入群可能性总体上也是增大的趋势。
因此，我们可以把影响用户入群可能性的因素归结为三大类，即群整体因素，用户之间的因素和用户与群关系的因素，分别用 g，h 和 f 表示。我们可以为这三种因素分别建模，即：
然后再把它们融合到一个统一框架中。如图 6 所示。
图 6
根据因子图模型理论我们可以将用户入群可能性分解为这三种因素的乘积，即
继而得到目标函数，即
。
我们对目标函数求偏导，得到
其他两种因子参数与其类似，在此省略。此式中，等号右边的第一项表示函数基于数据分布的期望，这个比较好算，因为数据是有限的。第二项是函数基于模型参数的期望，这个无法计算。我们采用信念传播的方法来解决这个问题。有了偏导值，我们就可以采用梯度更新的方式来优化参数，即
然后用优化好的参数来预测用户是否被邀入群。
我们用两种基准方法来评估模型的性能。第一种是分类方法，第二种是链接预测方法。实验结果如表 1 所示（ML-FGM 是文中所述模型）。
表 1
另外，为了观察每种因子的对模型性能的影响，我们分别移除群因子，用户互相影响因子来做实验，如图 7 所示。
图 7
四种颜色柱体分别表示无移除，只移除群因子，只移除用户互相影响因子和移除这两种因子的性能。可以看到，移除用户互相影响因子对性能的影响还是比较大的。
本文从影响用户入群的因素分析着手，采用一个概率因子图模型将可能影响用户被邀入群的三种因素集成到一个框架中，提高了预测用户入群的概率。群组是社交网络中的一个重要概念，我们可以用用户网络结构来预测群组的发展变化，另一方面，群组的发展变化也影响着用户网络结构。因此，研究群组对用户网络结构的影响并利用该信息预测网络结构的发展变化也是本领域亟待解决的一个问题。
雷峰网特约稿件，未经授权禁止转载。详情见转载须知。
