社会网络分析之实际应用

互联网，尤其是Web2.0在过去的十年飞速发展，其中社交网络作为Web2.0的重要组成部分极大的拉近了人们之间的举例，产生了新的合作和沟通方式，也变更了传统通过传统媒介的信息传播方式。在传统时代，传统的媒体通过单向传播由大V发声，将信息从单一的生产者传递给广泛的消费者。而社会网络中，一个用户既是消费者也是生产者，这也就是我们口中的UGC(user generated content)，在传播效率上也发生了翻天覆地的变化，据说在Twiiter上的传播速度已经大于了地震波的速度；此外在过去，每个人能建立起的社交关系非常有限，并且极大的受着空间的限制，大多社交关系的产生都是由于用户位于同一区域，例如同一公司，同一学校等等，基于兴趣的社交关系几乎不存在，而社交网络对社交关系产生了极大的影响。所以说社会网络真正的改善了人们的生活，这也是我痴迷于互联网的最大原因。

但是社会网络在过去的十年时间内一直都是以某种产品形态存在，社交网络分析作为数据应用的某一方向，往往被人认为不接地气，并无卵用。例如有一篇很经典的Paper大概是分析Twitter到底是一个社交网络还是一个网络媒体，切不谈产生的结论如何，但是这很难产生真正的商业价值；例如有学者专门研究不同社区的小世界理论/效应，其实也并无真正的生产应用。

社会网络其实是一张大的图结构，而图就是由节点和边之间组成，落实到具体的社会网络分析，节点就是用户，而边就是将他们联系到一起的因子，例如互相关注，例如共同兴趣等等。那么我们就先从节点本身说起。评价一个节点、一个用户、一个人有很多指标，其中最重要的指标就是节点的“重要性”。也就是一个人的重要性。如何说一个人重要呢？学术界有很多关于节点重要性的计算方式，但是在这里，我们更重要的是把这些公式与实际的生产环境联系起来。

计算方式1：节点的度数

这是最常用的计算方式，原因是因为这种计算方式最简单，也最泛化。具体的计算方式就是看一个点的度数，也就是和一个点连接的边数。我们落实到实际的物理意义上，就是将这个人与多少人“相关联”。

其实这一指标有很多的应用价值，但是也有很多的误区。我举个简单的例子，我们希望在微博上去找大V投放广告，那么自然想到最简单的办法就是找到关注数最多的用户去做广告投放。

再做一个稍微复杂的扩展，如果我们希望买一篇软文来推广我们的产品，于是我们需要选一个渠道来做我们的广告投放，但是我们知道网站和网站之间经常会有着“转载”，那么我们就需要把文章和文章之间建立起一个转载的关联，从而希望我们的文章能够最多地覆盖到更广泛的渠道。最简单的办法自然也是找那种最容易被转载的渠道。

再说一个具体的推荐算法的例子。当一个新用户刚刚进入到某一社交网络中时，我们需要为其推荐好友。那么最简单的推荐方式就是推荐被关注数最多的用户，原因无外乎有二：1. 被关注数越多说明质量越高。2.被关注数越多说明兴趣越能被大众所接受于是越有可能为今后的兴趣迁移做准备。(当然，这也是一个很多人都忽略的坑。)

说到度数需要再稍微提一点，我们知道所有的社会网络，无论是新闻、条目还是用户的关注数，都是呈幂率分布的，所以我们在做社会分析的时候要非常注意到头部、中部和尾部的独立分析，并且我们实际应用时可以利用这一实际规律节省大部分的计算资源，提高计算效率。例如我们可以通过删除尾部数据减少目标数，同时在计算相似度时可以将头尾分开，从而避免数据倾斜的问题。

但是所有的这种方式其实都有一种致命的问题，我们都忽略了二次传播以及多次传播的重要性。

计算方式2：PageRank、PeopleRank

PageRank相信每个人都非常清楚，PageRank的最大好处就是通过迭代计算充分地考虑了多次传播的因素。

这一点对于做算法的同学听上去很简单，但是其实有着特别有趣的商业化应用。我们知道，大部分的大V的广告基本都是根据粉丝数来计费的，那么如果你的预算不足以请动Angelababy，这个时候该怎么办呢？Pagerank就是其中的算法之一，虽然说某位用户的粉丝数很少，但是她可能是某电影学院的学生，可能会是某某明星的同学，那么其实会有很多的明星指向她，所以其实她的微博也可能会在一定概率上被其他的明星所转播。这个时候算法就派上用场了，一般情况下我们可以对PageRank做一个略微的改进，在PageRank中，两点之间的权重取决于“出点”的度数，那么这里我们需要把度数换算成某明星可能转发该文章的概率，这个概率会取决于文章内容与明星标签的关联度，取决于这个明星关注的人数(即看到该文章的微博)等等。这就是用算法产生价值的很重要的一个点。

计算方式3：最短距离& 集群中心点

在社会分析领域，有个评估节点的指标叫做betweenness，其实就是评估这个点到其他点的距离，他的核心应用在于，如果我从这个点开始传播，有多大的概率可以到达社区中所有的人。有些算法基础的都会知道这个计算量几乎是无法承受的，但是其实这也有很好的应用场景。

集群中心点这个词是我自己定义的，可能不恰当，其实就是整个集群中的Hub点，用图论语言描述，就是如果删除该节点，会将整个图变成若干个独立的子图。用平常的语言描述，就是说这个人可以将若干个不同群体的人联系起来，最简单的现实中的例子就是猎头。

那么他们到底有什么实际的作用呢？

之前罗辑思维中讲过一个案例，大意是说中国传媒有个女学生希望罗胖帮他做宣传，罗胖出了个难题说你要联系到100个人找到我，我就答应你的要求，最后这个女孩果然找到了100个不同的人找到了罗胖，成为了一个非常经典的案例。同理很简单，继续举上面投微博广告的例子，我没有足够的预算又希望能够让某个明星帮我转播微博，我能做什么事情呢？假设说我认为微博的三度衰减已经趋近于0，那么我需要找到的是关注我的，并且在三度以内可达该明星的社交关系，如果我找到所有这样的关系，相当于该明星有非常大的概率能够看到这条微博。这个例子可能还有些复杂，那么举个简单一些的。如果我希望投放某个广告，性价比最高的方式是什么？找到所有我希望触达的人，即目标用户(例如所有喜欢游泳的用户)，然后找到所以可以投广告方(例如某些明星，媒体等)，然后计算广告方和目标用户之间的平均最短距离，作为这些广告方的Betweenness，再通过加权方式与他本身的价钱相结合，就可以计算出这个用户的性价比。

那么对于集群中心点的应用就更加简单了，我在算法1中提到过，对于新用户，我们为他推荐入度最大的用户、推荐好评最多的文章、推荐红心最多的歌曲是最稳妥的方法，但是这都没有考虑到未来用户的兴趣迁移，也就是没有最大化用户的兴趣图谱。那么作为Hub点，最重要的特征是他连接着多个不同的兴趣群体，同时被多个兴趣群体所接受，于是我就可以通过这个Hub用户左右摇摆(即多叉树结构)，从而发散出该用户的最完整的兴趣图谱。

想必2016年的美国大选是有史以来最奇怪的一次大选，而近期纸牌屋里的大数据分析走进现实，让我们重新将目光聚焦在社交网络和大数据分析已经成为助力美国大选不可或缺的渠道和工具。早在08年大选中，奥巴马的竞选团队就让人们见识到了社交网络在竞选中的力量，并且在上任后不再是端正的总统先生，而是“不正经”的表情包奥巴马。奥巴马之于社交网络，就如肯尼迪之于电视。据估计，2016年预计竞选广告费用总计114亿美元，其中有5亿美元会投放在社交媒体上。社交网络上的数据分析，会帮助构建选民的用户画像，画像会帮助指导竞选广告应该投放在哪些网站的哪些年龄层次、哪些偏好的用户身上，这也是精准营销与广告计算的应用领域。

说到社交网络，这个虚拟世界和现实世界的桥梁，不同的社交网络承载着不同的特质。Facebook/微信是基于朋友之间的强关系网络，有助于朋友之间的联系与关系维系；Twitter/微博/豆瓣是基于单向关注的弱关系社交网络，有助于消息的传播和塑造意见领袖；Linkedin是面向工作的职业社交网络，帮助商务交流与求职招聘。这些社交网络每天都会产生大量的用户数据（UGC，User Generated Content），会吸引大量的研究者、商业人员和广告投放商来对这些用户数据进行研究。

对于社交网络的分析和研究范围很广，也存在着许多有意思的研究课题。例如，在社交网络中社区圈子的识别（Community Detection）、 基于好友关系为用户推荐商品或内容、社交网络中人物影响力的计算、信息在社交网络上的传播模型、虚假信息和机器人账号的识别、基于社交网络信息对股市、大选以及互联网金融行业中的反欺诈预测等。社交网络的分析和研究是一个交叉领域的学科，所以在研究过程中，我们通常会利用社会学、心理学、信息论、新闻传播等多种学科基本结论和原理作为指导，通过人工智能领域中使用的机器学习、数据挖掘和图论等算法对社交网络中的行为和未来的趋势进行模拟和预测。

今天我们主要来介绍下社交圈子的识别，也称作社区发现算法。

其实说到社交圈子，不得不提一下社交网络中的推荐算法，比如说人人网中的好友推荐、应用推荐、个性化推荐（用户偏好、用户兴趣）等，主流的推荐方法是协同过滤、内容过滤，再有就是基于图的方法，也就是这里介绍的通过社交圈子识别后，在社交圈子内为用户做推荐，这时候的准确率和效率都会提升。发现社交圈子作为社会网络分析中一个重要的基础研究，它揭示了社交网络最核心的人与人之间的关系，而且每个人根据与他人关系的不同以及兴趣的不同可以属于多个社交圈子。映射到数据层面来分析用户的亲密度的话，可能会包括共同好友数目、个人资料相似程度、用户互动频度和用户的兴趣。

从学术的角度来阐述这个问题的话，往往会将整个社交网络看作是一个图的结构，每个用户就是图中的节点，人与人之间的关系就是节点之间的边，根据不同类型的社交网络，所构成的图可以是有向图也可以是无向图，关系的强弱也可以利用边上不同的权重来体现。社交网络也是复杂网络的一种，复杂网络是复杂系统的抽象，现实世界中的万维网、食物链、基因网、交通网络、电力电路网络等等都可抽象为复杂网络。对复杂网络的研究一直是许多领域的研究热点，复杂网络有三大特性，无尺度分布（scale-free distribution）、小世界效应（the small-world effect）和强社区结构（strong community structure）。

在大规模网络中，结点的度服从幂率分布（power law distribution）。在社交网络中，结点的度可以理解为一个人连接的朋友的个数。结点的度服从幂率分布，也就是说大部分结点有很低的度，而少数结点有非常高的度。在重对数尺度下，度分布近似线性。由于分布的形状不随尺度而改变，也称为无尺度分布。

所谓小世界网络，在日常生活中有些你觉得遥不可及的人，也许你的朋友就认识他；或者一个陌生人却与你有相同的朋友，会让你感慨“这个世界好小”。用图论来解释的话，小世界网络就是一个由大量节点构成的图，任意两点之间的平均路径长度要远远小于节点数量。其中最被人熟知的就是六度分割理论，即通过不超过六个人就能串联两个人的社交关系。如果你上Facebook的话，Facebook上的15.9亿人中间，仅隔着3.57个朋友而已。

复杂网络的第三大特性，强社区结构，引导我们认知到有别于规则网络和随机网络的真实社交网络是拥有社区结构的，社区内节点与节点之间的关联关系相交于社区与社区间的关联关系更加紧密，也就是说一个社交圈子中的成员之间互动会很频繁，两个社交圈子之间成员之间的互动频率会远远低于一个社交圈子内的互动。对于社交圈子的发现算法来说，社交圈子的质量依赖于圈子内成员的关系的紧致度以及不同圈子间的分离度。

聚类算法可以用于解决社区发现算法的问题，K-means等聚类算法可以充分利用社交网络中的联系的强弱、频繁程度、以及互动的文本内容，可以从更深的层次和视角来研究人与人之间的关系，来研究社区划分，来实现真实场景下的社交圈子识别。K-Means算法的思想是初始随机给定K个聚类中心，按照距离最近原则把待分类的样本点分到各个聚类，然后按平均法重新计算各个聚类的质心，从而确定新的聚类中心，迭代计算，直到聚类中心的移动距离小于某个给定的误差值。使用算法描述语言，只要三个步骤：

聚类和社区发现算法之间最大的不同在于，社区发现中的点被网络连接到了一起，而聚类中的数据点并没有构成网络。所以，在使用K-means算法来发现社区之前，需要先定义好网络中点之间的距离，也可以理解为节点与节点之间的相似度。有三种方法，分别是相同的邻居数，交往的频繁程度和交往内容的情绪色彩。相似度定义好之后，就可以使用K-means算法了。另一个需要考虑的地方就是K-means算法需要预先设定聚类初始节点，在社区发现的场景中，可以选取一些网络中比较重要的节点，例如度比较高的节点，也就是连接边较多的节点，这样的节点更可能是一个社团的中心。

然而实际的社交圈子是一个更为复杂的网络，因为用户会具有多种兴趣，可以属于多个社交圈，发现这种圈子的研究也被称为重叠社区的发现。一种比较简单的启发式方法是，以网络中度很大的节点作为初始的圈子，然后把对圈子贡献最大的邻接节点依次加入到圈子中，直到全局贡献度达到极值，并形成一个圈子。如果存在对多个圈子贡献度都很大的边界节点，则将其加入到多个圈子中。

贡献度的计算方法有很多，最简单的是计算节点与圈子相连边个数与圈子内边个数之比，另一种常用的衡量圈子划分质量的指标是模块度（modularity），由Newman提出的。模块度不仅仅作为优化的目标函数提出，它也是目前是最流行的用来衡量社区结果好坏的标准之一，它的提出被称作社区发现研究历史上的里程碑，这是第一次对社区这个模糊的概念提出了量化的衡量标准。模块度是基于一个思想，社区是节点有意识地紧密联系所造成的，它内部边的紧密程度总比一个随机的网络图来的紧密一些，它表示所有被划分到同一个社区的边所占的比例，再减除掉完全随机情况时被划分到同一个社区的边所占的比例。模块度越大，社区结果越明显。例如工业界优化最多的Louvain算法，初始化每一个节点作为一个社区，通过计算模块度收益来合并社区，并且重复这个过程直到模块度无收益为止，得到社区划分结果。然而，模块度优化问题已经被证明是有解法限制的，尤其是针对大规模网络和较小社区的网络，但仍然有非常多的学者在研究基于模块度的社区发现算法。

但对于数以亿计的节点来说，目前的圈子发现算法还很难处理特大规模的数据，因此很多研究者提出了启发式的方法去减少程序处理的复杂性，对最终结果进行近似的求解。近期使用标签传播算法（Label Propagation Algorithm）来解决重叠社区的发现算法逐渐走上科研舞台。这是一个非常快速且易于扩展的社区发现算法，被广泛应用与大规模网络的社区发现，主要思想是用网络结构来指导社区结构的发现。算法LPA的思想非常简单。网络中的每个节点都有一个标签，经过标签的迭代更新，最终标签一致的节点作为一个社区。这种方式，紧密连接的节点群组会有一个一致的特殊标签，由此快速的构成一个社区。由于算法LPA是近线性的算法，时间复杂度低，并且易于扩展适应于大规模的社区发现。

LPA算法的改进算法SLPA，是基于Speaker-listener模型的标签传播算法，模仿了信息传播的过程，就像人们热衷于传播那些经常热门讨论的信息。借助于SLPA算法的思想，我设计了改进算法HLPA，不会忘记上一次迭代中节点所更新的标签信息，给每个节点设置了一个标签存储列表来存储每次迭代所更新的标签。最终的节点社区从属关系将由标签存储列表中所观察到的标签的概率决定，当一个节点观察到有非常多一样的标签时，很有可能这个节点属于这个社区，而且在传播过程中也很有可能将这个标签传播给别的节点。更有益处的是，这种标签存储列表的设计可以使得算法可以支持划分重叠社区。并且不同于SLPA算法的是，HLPA重新设计了标签传播机制，SLPA为同步更新每一个节点的标签，同步更新模式会导致摇摆现象，而单纯的异步更新模式会导致每次的社区划分结果都会很不同，所有HLPA采用了一种同步+异步的一种混合更新模式。首先，将图的边排列成两边节点的模式，这样可以消除更新过程中摇摆现象。在每次迭代过程中，采用同步更新的方式来更新每一边的节点标签列表。最后，基于存储标签列表中的标签进行后期处理，使用阈值r用于输出社区结果集和。

图1 标签传播算法HLPA中混合更新模式

社交圈子发现算法并不仅局限在用户主动建立起的关系上，其更重要的价值在于对用户非显性的潜在关系发现。从社交圈子发现的结果中，我们能够更加清楚地看出属于一个圈子的人群。比如，喜爱MacTalk的同学也有可能喜欢Smartisan手机，喜欢看小道消息的同学估计也会喜欢吃海底捞。社交圈子还能帮助我们分析信息是如何传播的，例如微信朋友圈中的信息流，都是通过我们的关系圈逐层向外传播的，我们所看的的消息也直接来自我们所关心的人，更外围的消息也必须逐层传播才能接触到我们。与传统媒体依靠内容作为传播的主题形式有所不同，社交网络上的信息传播，更加依赖于发布者的影响力以及社会关系，通过好友或粉丝的关系将信息扩散到社交网络中，这种信息在社交网络中会被好友及粉丝看到，并以一定的概率被分享和转发，从而进行传播。

但一旦我们互相存了对方的手机号，那么从数据的角度来说我们是真实好友的可能性就非常大了。包括微信、Linkedin、telegram、band等产品，如果真的能够做好基于手机通讯录的社交网络，我们就可以通过异构的社交网络对社交圈子进行综合性的判断，其价值不可估量。

我建了一个连接互联网程序员和营销人的圈子（听说可以无上限人数），程序员、互联网营销、运营之人专属，定期分享知识干货。我会持续邀请我认识的技术大咖，营销大神进来，欢迎扫码加入。返回搜狐，查看更多

责任编辑：