社团发现算法研究和在SNS网络中的应用

篇首语：不知道大家有没有用过QQ圈子，或者看过相关新闻，当QQ圈子刚出来时候，很多震撼了，因为把其社会关系很多隐私的部分都挖掘出来。很多人惊呼，QQ圈子利用了腾讯朋友网数据，因为朋友网是实名制网络，和实际社会关系比较接近，只有这样才能解释QQ为什么把其实际社会网络圈子（社团）挖掘出来。其实有这个本能反应很正常，并且相信90%人看到这样推断也不会质疑。这就数学神奇的地方。虽然QQ只是一个虚拟的SNS，但是实际社会关系有掺杂和渗透其中。譬如你的QQ好友中有你虚拟的网友，但是也有你同学或亲人。这些社会关系已经不知不觉隐藏在你的关系链中，利用合适的数学算法，就能把这些关系链准确无误的挖掘出来。

 

最近在研究关于SNS网络中人群分类，发现其中很有趣，对于SNS公司的实际生产来说也是很有用的。现在分享一下技术成果。纯粹从技术上讨论，不会透漏有关商业数据。

 

阿基米德说：“给我一根足够才的棍子，我可以撬起地球”，这句话很好的阐释了杠杠原理。这里我也以这样一句话作为开篇引子：

 

“给我一条关系链，我可以找出你身边各个亲密团体”

 

听起来貌似有点模糊。其实这个条件并不难，目前很多网络公司都有这样关系链，微博，微信，邮箱，IM，存在各种各样的关系链，只需要其中一个产品的数据，就可以算出你这些人中，那些是你的同学，那些事你的同事，那些你的密友。甚至还可以算成那些还未联系上的同学，同事或亲戚。

 

是的，就是这么神奇，“给我一条关系链，我可以找出你身边各个亲密团体”，这就是数学的神奇。你也可以称之为数据挖掘。

 

找出亲密团体。这里用专业一点词来说，就是找出社团，找出聚类。也就是社团发现算法，聚类算法。

 

先说一下我们SNS网络中的模型，在SNS网络中，每个人都有一个关系链，这条关系链是以自己为中心的，属于星形结构。

这个星形结构对我们来说，没有多大用.现在我们对他们进行分类，那些人是一类的。例如，A，B，C是我的同学，E、F、G是我的同事。如果能准确找出这些数据，那是很有商业价值的，对广告推广，信息发布都是相当有用。

慢着！这里要补充一下的是，前面所讲的关系链，是只知道某某和我存在社会关系，至于这个关系是同事，同学，亲戚还是网友。是不需要事先知道和注明的。而是通过我们所说社团算法，能够一一分解出来，算出来的一个个团体。但是这里需要说明的是，社团发现算法也是只知道A，B，C是属于一个类别，但是无法确定他们是属于同学这一类别。至于要找出这个类别的具体属性，就要通过辅助手段，例如通过关系链以外的数据分析，例如A，B，C的名字，出生地，年龄，教育经历，行业。等，有这些数据，就能轻而易举找出该团体的属性名字。

 

一条孤零零的关系链是没有任何价值，当众多关系链凑到一起，就不一样了。

然而，人类的社会关系并不是如上图那样简单结构，上图可以看成是一个辐射状树形结构，实际上存在这样情况：我的朋友也是你的朋友。这条关系太重要了。我称之为“社会三角形”——这个词不知道是不是我首创。

这个社会三角形称之为黄金三角形也当之无愧，因为它太重要了，可以说我们算法就建立于它的存在之上。

因为有这样的社会三角形的存在，前面那个关系图从树状辐射变成下面的网状结构了。

结构一下子复杂好多倍了，实际上社会网络节点很多，看起来像下面一样，像一坨麻线。

好了，如何从这复杂的网络中找出一个个社会团体呢，正是本文要介绍的。本文介绍三种算法。这三种算法可以互为补充，也可以独立应用。

社团亲近度算法：算法基本原理是：判断一个人是否属于某个社团，看这个人和社团内部关系是否比社团外部关系多，如果和社团内部关系比较多，就很可能是属于这个社团。

假如上图使我们SNS网络中部分节点，假设我们已经找出两个部分社团，分别用黄色和绿色圈住的部分。现在我们要继续计算，判断A是否也属于这两个社团中一个。我们计算A的边。A节点的度是 7，和黄色社团度=3，和绿色社团度为2。我们使用一个目标函数来量化社团。Q=    。我们使用这个公式表示社团凝聚度，意思就是Q值越大，越有可能是一个社团。

上图中我们尝试把A分别加入黄色和绿色社团，计算Q值大小，如果Q值在增加，并且增加最多的话。那么A应该属于哪个社团一成员，应该加入该社团。

 

社团密度算法：这是利用几何学原理来计算。前面算法计算出来的社团可能会存在“杂质”，所谓“杂质”，就是在你同学社团里面有可能混入一个不是同学的成员。用这个密度算法可以很好的“去噪”。所以这两种算法结合起来。可以得出很精确的结果。

算法原理是认为，一个社团内部成员必定互相联系多，这个算法是计算联系度的。相信成每个成员是多边形的每个顶点。一个三角形最多有3条边，4边形最多6条边，5边形最多10条边。N边形最多N(N-1)/2条边.

我们假设最大密度是1，那么密度m=实际边数*2/N(N-1); m越大，说明越有可能是一个社团。具体算法如下：

加A加入该社团，计算其m值，如果m增大，说明A应该是该社团成员。或者m值可以控制在0.7大小。大于这个值，应该是属于社团成员。

 

迷宫算法：这个算法是利用游戏迷宫原理。同样，一个社团内部必定互相联系很多，把这些联系看着迷宫的一条条路。这样一个社团必定组成一个复杂的迷宫。

现在判断A是否属于红色社团，就假设一个游戏者，从A点出发，完全随即沿着边走，如果走10次还在红色区域类，说明A应该属于该红色社团成员。当然这个次数10可以自己控制。

 

上面几个算法在实际生产环境中得到验证，并且数据很准确。社团算法多种多样，但是大多数太复杂，学术性太严重。本文介绍的几种算法比较平民化，通俗易懂，这也是我写本文的目的。希望大家能对这块领域有所了解。