想必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个点作为初始聚类中心；
-
计算每个样本点到聚类中心的距离，将每个样本点划分到离该点最近的聚类中去；
-
计算每个聚类中所有点的坐标平均值，并将这个平均值作为新的聚类中心。
-
反复执行2、3，直到聚类中心的移动小于某误差值或者聚类次数达到要求为止。
聚类和社区发现算法之间最大的不同在于，社区发现中的点被网络连接到了一起，而聚类中的数据点并没有构成网络。所以，在使用K-means算法来发现社区之前，需要先定义好网络中点之间的距离，也可以理解为节点与节点之间的相似度。有三种方法，分别是相同的邻居数，交往的频繁程度和交往内容的情绪色彩。相似度定义好之后，就可以使用K-means算法了。另一个需要考虑的地方就是K-means算法需要预先设定聚类初始节点，在社区发现的场景中，可以选取一些网络中比较重要的节点，例如度比较高的节点，也就是连接边较多的节点，这样的节点更可能是一个社团的中心。
