（点击可查看大图）

本文主要阐述：

社交网络的结构特性与演化机理

社交网络群体行为形成与互动规律

社交网络信息传播与演化机理

浏览后四章的内容请见下篇（2017年9月26日二条）。

前言

社交网络在维基百科的定义是“由许多节点构成的一种社会结构。节点通常是指个人或组织，而社交网络代表着各种社会关系。”在互联网诞生前，社交网络分析是社会学和人类学重要的研究分支。早期的社交网络的主要指通过合作关系建立起来的职业网络，如科研合作网络、演员合作网络等。

本文所指的社交网络分析专指在线社交网络分析（Online Social Network Analysis），该门科学的发展是随着在线社交服务（Social Network Service, SNS）的出现而诞生。在线社交服务的种类大致可分为四种：即时消息类应用（QQ、微信、WhatsApp、Skype 等），在线社交类应用（QQ空间、人人网、Facebook、Google+ 等），微博类应用（新浪微博、腾讯微博、Twitter 等），共享空间类应用（论坛、博客、视频分享、评价分享等）。

在线社交网络（下文统称社交网络）有着迅捷性、蔓延性、平等性与自组织性等四大特点。正因为这些特性，其在互联网出现的短短数十年内已经拥有数十亿用户并对现实社会的方方面面产生着影响。在2016年的美国总统大选中，当选总统特朗普就很好地利用了推特作为宣传工具；而在国内，从魏则西事件到和颐酒店事­­­件再到最近的“刺死辱母者”事件，无一不是在社交网络上迅速发酵，并最终对现实社会产生影响。而且这种线上影响线下的趋势越来越明显。

除了社交网络给社会和经济带来许多正面影响之外，也带来了不少负面影响。从Facebook 和 YouTube上的暴力恐怖信息传播到微博微信上大量谣言和假新闻，这些有害信息借助社交网络的特点迅速传播并且往往产生不可控的后果。

为了利用好社交网络的特性，产生价值，消除危害，所以产生了社交网络分析这门科学。它是一种基于信息学、数学、社会学、管理学和心理学等科学的交叉科学。根据社交网络的特性，其主要研究三大内容：结构与演化，群体与互动，信息与传播。

本文简要概述了社交网络分析领域各个研究方向，对于细节性的内容我只列出参考文献，在文章最后提供了一些学习资源。 希望通过阅读本文，对这个领域感兴趣的读者可以对社交网络分析有一个宏观理解并且找到学习的方向。笔者作为社交网络分析的初学者，对某些概念和事实的解释和陈述不免有错误之处，还望各位读者能及时指正，大家共同交流进步。

一． 社交网络的结构特性与演化机理

1. 社交网络结构分析与建模

1.1 统计特性

社交网络模型许多概念来自于图论，因为社交网络模型本质上是一个由节点（人）和边（社交关系）组成的图。笔者将简要介绍社交网络模型中常用的统计概念。

度（Degree）：节点的度定义为与该节点相连的边的数目。在有向图中，所有指向某节点的边的数量叫作该节点的入度，所有从该节点出发指向别的节点的边的数量叫作该节点的出度。网络平均度反应了网络的疏密程度，而通过度分布则可以刻画不同节点的重要性。

网络密度（Density）：网络密度可以用于刻画节点间相互连边的密集程度，定义为网络中实际存在边数与可容纳边数上限的比值，常用来测量社交网络中社交关系的密集程度及演化趋势。

聚类系数（Clustering Coefficient）：用于描述网络中与同一节点相连的节点间也互为相邻节点的程度。其用于刻画社交网络中一个人朋友们之间也互相是朋友的概率，反应了社交网络中的聚集性。

介数（Betweeness）：为图中某节点承载整个图所有最短路径的数量，通常用来评价节点的重要程度，比如在连接不同社群之间的中介节点的介数相对于其他节点来说会非常大，也体现了其在社交网络信息传递中的重要程度。

1.2 网络特性

小世界现象：小世界现象是指地理位置相距遥远的人可能具有较短的社会关系间隔。早在1967年，哈佛大学心理学教授 Stanley Milgram 通过一个信件投递实验，归纳并提出了“六度分割理论（Six Degrees of Separation）”, 即任意两个都可通过平均五个人熟人相关联起来。1998年，Duncan Watts 和 Steven Strogatz 在《自然》杂志上发表了里程碑式的文章《Collective Dynamics of “Small-World” Networks》，该文章正式提出了小世界网络的概念并建立了小世界模型。

小世界现象在在线社交网络中得到了很好地验证，根据2011年 Facebook 数据分析小组的报告， Facebook 约7.2亿用户中任意两个用户间的平均路径长度仅为4.74，而这一指标在推特中为4.67。可以说，在五步之内，任何两个网络上的个体都可以互相连接。

无标度特性：大多数真实的大规模社交网络都存在着大多数节点有少量边，少数节点有大量边的特点，其网络缺乏一个统一的衡量尺度而呈现出异质性，我们将这种节点度分布不存在有限衡量分布范围的性质称为无标度。无标度网络表现出来的度分布特征为幂律分布，这就是此类网络的无标度特性。

1.3 网络模型

WS 模型：WS 模型即小世界模型，通过小世界模型生成的小世界网络是从规则网络向随机网络过渡的中间形态。

BA 模型：BA模型考虑到现实网络中节点的幂律分布特性，生成无标度网络。

其他模型：森林火灾模型，Kronecker 模型，生产模型。

2. 虚拟社区（社团）及发现技术

2.1 定义

虚拟社区基于子图局部性的定义：社区结构是复杂网络节点集合的若干子集，每个子集内部的节点之间的连接相对非常紧密，而不同子集节点之间的连边相对稀疏。

在社交网络中发现虚拟社区有助于理解网络拓扑结构特点，揭示复杂系统内在功能特性，理解社区内个体关系。为信息检索、信息推荐、信息传播控制和公共事件管控提供有力支撑。虚拟社区发现存在着许多经典的算法，这些算法用于挖掘不同规模的虚拟社区，算法在追求高精度的同时力求提高效率（降低时间复杂度）。

2.2 社区发现算法评价指标

以下评价指标可通过搜索引擎获得详细的介绍：

模块度(Modularity)：通过比较现有网络与基准网络在相同社区划分下的连接密度差来衡量网络社区的优劣。

NMI (Normalized Mutual Information)：利用信息熵来衡量预测社区结构一直社区结构的差异，该值越大，则说明社区结构划分越好，最大值为1时，说明算法划分出的社区结构和一直社区结构一致，算法效果最好。

Rand Index：表示在两个划分中都属于同一社区或者都属于不同社区的节点对的数量的比值。

Jaccard Index：Jaccard 系数用来衡量样本之间的差异性，是经典的衡量指标。

2.3 社区静态发现算法

模块度最优化算法

Mark Newman 提出了针对模块度的最大化的贪心算法FN。可参考文献：Newman,Mark EJ. "Fast algorithm for detecting community structure innetworks." Physical review E 69.6 (2004): 066133.

多目标优化算法

Zhao, Yuxin, et al. "Acellular learning automata based algorithm for detecting community structure incomplex networks." Neurocomputing 151 (2015): 1216-1226.

Du, Jingfei, Jianyang Lai,and Chuan Shi. "Multi-Objective Optimization for Overlapping CommunityDetection." International Conference on Advanced Data Mining andApplications. Springer, Berlin, Heidelberg, 2013.

基于概率模型的算法

Newman, Mark EJ, andElizabeth A. Leicht. "Mixture models and exploratory analysis innetworks." Proceedings of the National Academy of Sciences104.23(2007): 9564-9569.

Ren,Wei, et al. "Simple probabilistic algorithm for detecting communitystructure." Physical Review E 79.3 (2009): 036111.

信息编码算法

Rosvall, Martin, and Carl T.Bergstrom. "Maps of random walks on complex networks reveal communitystructure." Proceedings of the National Academy of Sciences 105.4(2008): 1118-1123.

Kim, Youngdo, and HawoongJeong. "Map equation for link communities." Physical Review E 84.2(2011): 026110.

2.4 社区动态发现算法

派系过滤算法

Palla, Gergely, et al."Uncovering the overlapping community structure of complex networks innature and society." arXiv preprint physics/0506133(2005).

Kumpula,Jussi M., et al. "Sequential algorithm for fast cliquepercolation." Physical Review E 78.2 (2008): 026109.

基于相似度的聚合算法

Shen, Huawei, et al."Detect overlapping and hierarchical community structure innetworks." Physica A: Statistical Mechanics and its Applications388.8(2009): 1706-1712.

Huang,Jianbin, et al. "Density-based shrinkage for revealing hierarchical andoverlapping community structure in networks." Physica A:Statistical Mechanics and its Applications 390.11 (2011): 2160-2171.

标签传播算法

Raghavan, Usha Nandini, RékaAlbert, and Soundar Kumara. "Near linear time algorithm to detectcommunity structures in large-scale networks." Physical review E 76.3(2007): 036106.

Gregory, Steve. "Finding overlapping communitiesin networks by label propagation." New Journal of Physics 12.10(2010): 103018.

局部扩展优化算法

Lancichinetti, Andrea, andSanto Fortunato. "Benchmarks for testing community detection algorithms ondirected and weighted graphs with overlapping communities." PhysicalReview E 80.1 (2009): 016118.

Lee,Conrad, et al. "Detecting highly overlapping community structure by greedyclique expansion." arXiv preprint arXiv:1002.1827 (2010).

3. 虚拟社区演化分析

在线社交网络中存在着大量显性或者隐性的虚拟社区结构，这些虚拟社区结构并不是永恒不变的，随着事件变化，社区结构也在不断演变。分析动态的虚拟社区结构演化有助于理解整个社交网络的演化过程，所以有着重要的研究价值。

3.1 虚拟社区的涌现

虚拟社区涌现即在社交网络中虚拟社区从无到有的过程，其最重要的特征是网络聚集现象。

周期闭包：所谓周期闭包，是指网络节点倾向于和自己在网络中邻居的邻居建立连接关系而形成的结构，该机制是导致虚拟社区形成的主要因素。实验表明三元闭包的出现概率随着两个节点之间测地距离的增减呈指数递减。相反地，焦点闭包和测地距离无关，其生成原因是两个节点之间有共同的兴趣或参与共同的活动。

偏好连接：在很多真实网络中，新增加的边并不是随机连接的，而是倾向于和具有较大度数的连接。

3.2 虚拟社区的演化

在线社交网络虚拟社区演化过程非常复杂，影响因素很多。如何挖掘虚拟社区演化中的关键性因素成为社交网络研究中一个重要而有挑战性的课题， 用户个体的累积效应、结构多样性和结构平衡性三个基本因素对虚拟社区演化都存在影响。

3.3 演化虚拟社区的发现

演化虚拟社区发现目前已有大量的研究资料，以下五种是比较成熟的算法模型，具体细节和根据参考文献进一步了解。

基于相邻时刻相似度直接比较的演化虚拟社区发现

Hopcroft, John, et al."Tracking evolving communities in large linked networks." Proceedingsof the National Academy of Sciences 101.suppl 1 (2004): 5249-5253.

Greene, Derek, Donal Doyle, and PadraigCunningham. "Tracking the evolution of communities in dynamic socialnetworks." Advances in social networks analysis and mining (ASONAM), 2010international conference on. IEEE, 2010.

基于演化聚类分析的演化虚拟社区发现

Chakrabarti, Deepayan, Ravi Kumar,and Andrew Tomkins. "Evolutionary clustering." Proceedings ofthe 12th ACM SIGKDD international conference on Knowledge discovery and datamining. ACM, 2006.

Lin, Yu-Ru, et al."Facetnet: a framework for analyzing communities and their evolutions indynamic networks." Proceedings of the 17th international conference onWorld Wide Web. ACM, 2008.

基于拉普拉斯动力学方法的演化虚拟社区发现

Lambiotte, Renaud, J-C.Delvenne, and Mauricio Barahona. "Laplacian dynamics and multiscalemodular structure in networks." arXiv preprint arXiv:0812.1770 (2008).

基于派系过滤算法的演化虚拟社区发现

Palla, Gergely, Albert-LaszloBarabasi, and Tamas Vicsek. "Quantifying social groupevolution." Nature 446.arXiv: 0704.0744 (2007): 664.

基于节点行为趋势分析的演化虚拟社区发现

Hopcroft, John, et al."Tracking evolving communities in large linked networks." Proceedingsof the National Academy of Sciences 101.suppl 1 (2004): 5249-5253.

二． 社交网络群体行为形成与互动规律

1. 用户行为分析

社交网络用户行为是用户对自身需求，社会影响和社交网络技术进行综合评估的基础上做出的使用社交网络服务的意愿，以及由此引起的各种使用活动的总和。用户行为是在线社交网络研究的重要内容。现有研究主要基于如下两种思路展开，一是将在线社交网络作为一种特定的信息技术，研究用户对在线社交网络技术的采纳行为、拒绝行为和用户忠诚；二是将在线社交网络视为提供各种服务和应用的平台，研究用户使用各种服务和应用所表现出的特征与规律。

1.1 用户采纳与忠诚

在线社交网络用户采纳是指用户在对自身需求、社会影响和在线社交网络技术进行综合评估的基础上做出的使用在线社交网络服务的意愿或行为，在线社交网络再出现初期能否被尽可能多的用户采纳和试用对于其后续的扩散至关重要。目前已有多种理论被用于揭示在线社交网络用户采纳行为机理。其中，技术接受模型和计划行为理论是研究者们应用最多的两种理论。

在线社交网络用户忠诚是指用户在使用社交网络服务之后，能够继续保持使用的习惯。各种层出不穷的新型网络服务所带来的竞争压力让保持在线社交网络用户忠诚度愈发困难。目前为止，已经有多种理论被用于在线社交网络的用户忠诚研究。其中，期望确认理论和心流体验理论受到较多研究者青睐。

基于技术接受模型的在线社交网络用户采纳模型

David Fred 提出技术接受模型是目前信息系统研究领域最经典的模型之一。对模型详细了解可参考：

Davis, Fred D. "Perceived usefulness, perceived ease of use, and user acceptance of information technology." MIS quarterly (1989): 319-340.

基于计划行为理论的在线社交网络用户采纳模型

Icek Ajzen 提出的计划行为理论已经被广泛用于人类行为研究。对理论详细了解可参考：

Ajzen, Icek. "From intentions to actions: A theory of planned behavior." Action control. Springer Berlin Heidelberg, 1985. 11-39.

基于期望确认理论的在线社交网络用户忠诚模型

由 Oliver 提出的期望确认理论是研究消费者满意度的基本理论。 Anol Bhattacherjee 再该理论的基础上结合信息系统的特点提出了信息系统持续使用的期望确认模型（ECM-ISC）。对模型详细了解可参考：

Bhattacherjee, Anol. "Understanding information systems continuance: an expectation-confirmation model." MIS quarterly (2001): 351-370.

基于心流体验理论的在线社交网络用户忠诚模型

Mihaly Csikszentmihalyi等提出的心流体验理论是目前关于用户体验研究的重要理论。对理论详细了解可参考:Csikszentmihalyi, Mihaly. Beyond boredom and anxiety. Jossey-Bass, 2000.

1.2 用户个体使用行为

一般使用行为：用户可以在社交网络上执行各种各样的行为，例如浏览，点击，分享，点赞，收藏等等。具体的分类可参考：Benevenuto F, Rodrigues T, Cha M, Almeida V. Characterizing User Behavior in Online Social Networks. New York, New York, USA: ACM; 2009:49-62. doi:10.1145/1644893.1644900.

内容创建行为：用户在社交网络通过写博客微博，发帖评论等行为产生内容，对内容创建行为的研究主要研究创建内容的动机、创建内容时的主题选择偏好以及内容创建时的语言表述等。关于主题，可通过搜索引擎搜索 LDA 模型。

内容消费行为：用户在社交网络中通过浏览，分享和评论来满足他们的社交需求，对社交网络内容的消费可分为主动消费和被动消费。被动消费即“浏览”，有研究表明，社交网络中高达92%的行为都是浏览行为。主动消费即社交搜索，例如搜索朋友的信息以及向社交圈内好友提问等等。

1.3 用户群体互动行为

群体互动关系选择：对群体互动关系的研究主要是识别用户之间的关系，通过制定不同的衡量指标，研究用户之间的关系强弱。

群体互动的内容选择：社交网络中用户对内容选择与其社交关系密不可分。例如有研究表明两位维基百科编辑在互动前后产生的编辑内容的相似性有所不同。

群体互动的时间规律：在线社交网络中人类行为的时间特征研究主要集中于分析行为发生的时间间隔分布。研究发现在线社交网络中用户行为时间间隔分布不同于传统的负指数分布，而是呈现幂律分布，即具有“长尾效应”。对群体互动时间规律的研究可以应用到公共管理和决策等场景中。

2. 社交网络情感分析

随着互联网技术的迅速发展，网络已经成为人们获取信息，发表意见的主要途径，根据文本内容，我们可以将网络中的文本分为两种，一种是客观描述信息，主要针对事件、产品等进行客观描述，另一种是主观性信息，主要产生与用户对人物、事件、产品进行客观性描述；另一种是主观性信息，主要产生于用户对人物、事件、产品等的评价信息。主观性信息表达了人们的各种情感色彩和情感倾向，如“支持”、“反对”、“中立”等。

情感分析，在此等同于意见挖掘，是针对主观性信息进行分析、处理和归纳过程。情感分析最初起源于自然语言处理领域，主要从语法语义规则方面对文本的情感倾向性进行研判。随着社交网络的兴起与发展，情感分析逐渐涉及多个研究领域，如文本挖掘、Web 数据挖掘等，并延伸至管理学及社会科学等学科，并在产品评论、舆情监控、信息预测等多个领域发挥着重要的作用。

2.1 文本情感分析技术

基于语义规则的情感分析技术：我们将一句话中的带有感情的形容词和副词提取出来构成一个情感词典，这些词语可以代表用户的某种倾向性。基于语义规则的分析技术是计算评价词和情感词典中已经标注倾向性词语的距离，从而达到情感分类的目的。其最经典的算法是 SO-PMI 算法。

基于监督学习的情感分析方法：基于监督学习的方法是首先通过人工标注文本的情感极性，然后将此作为训练集，通过机器学习的方法对目标文本进行情感分类。常用方法：朴素贝叶斯，支持向量机。

基于话题模型的情感分析技术：有两个话题模型，PLSA (Probabilistic Latent Semantic Analysis)和 LDA (Latent Dirichlet Allocation) 模型，网络上有大量的学习资料可供读者进一步了解。

2.2 社交网络情感分析技术

面向短文本的情感分析技术：社交网络产生大量的短文本，例如微博和新闻评论，论坛帖子等等，这些短文本不同于新闻报道，其语法不规则，充斥大量噪声，因此对短文本的分析非常重要。

基于群体智能的情感分析技术：用户在社交网络中表达意见会受到其社交关系的影响，情感会沿着社交关系进行传播，因此可以通过研究社交用户之间的关系来提高情感分析的准确度。

社交网络的垃圾意见挖掘技术：社交网络中的垃圾意见，包括水军与广告等信息，通过对垃圾意见的挖掘，能够有效区分有效信息和垃圾信息，从而提高社交网络使用体验。

3. 个体影响力分析

发现社交网络中的有影响力的个体是社交网络研究中非常重要的研究分支，而且其有着重要的应用价值。例如微博营销，谣言检测，舆情管理等等。

1.1 基于网络结构的个体影响力计算

基于社交网络的图结构特性，有几个指标用来衡量网络中节点的中心度，即节点的影响力。除了以下三种外还有 PageRank 中心度等度量方法。

度中心度（Degree Centrality）：度中心度是指与该节点直接相连的节点的数量。

接近中心度 (Closeness Centrality)：指某节点与网络中所有其他节点的最短距离之和。

介数 (Betweenness Centrality)：介数用来衡量某节点在社交网络中中介作用大小。网络中某两个节点所有最短路径的数量除以这些路径中经过 A 节点路径的数量便是 A 节点的介数，也叫中间中心度。

1.2 基于行为的个体影响力计算

社交网络中用户的行为决定用户的影响力，以微博为例，用户主要表现的行为是评论、转发、回复、点赞、复制、阅读等等，基于这些行为特征构建多种网络关系图，可通过随机游走等方法发现网络中的影响力个体。

1.3 基于话题的个体影响力计算

在社交网络中用户在不同话题下的影响力不同，可以根据用户的关注网络和用户兴趣相似性来计算用户在每个话题上的影响力。

4. 群体聚集及影响机制分析

本部分主要介绍群体极化的概念。群体极化是指在群体决策的情境中，个体意见或决定往往会受到群体间的彼此讨论的影响，而产生一个群体性的结果。群体极化往往表现为群体内的个体不经过个人思考而同意大多数人的观点。群体极化是一个社会心理学概念，在社会学名著《乌合之众》中提到的大众心理状态就是群体极化的体现。

群体极化产生的条件可概括为四点：第一，必须有激发事件出现；第二，群体内的个人能看到前人的选择；第三，群体信息缺乏；第四，群体有一定的同质性。

在在线社交网络分析中，人们通过建立分析模型和仿真来研究在线社交网络中的群体极化现象。主要的分析模型有基于博弈论和委托—代理理论的从众行为模型，基于信息瀑的群体一致性模型和基于元胞自动机群决策和行为仿真。

Twitter 中政治观点的极化[4]

三． 社交网络信息传播与演化机理

1. 在线社交网络信息检索

信息检索(Information Retrieval) 是从大规模非结构化数据中获取信息的过程，例如搜索引擎就是典型的信息检索技术的应用。在线社交网络数据结构有其特殊性，以微博的“话题”（#话题名称#）为例，这种新型的信息组织方式是传统信息检索研究没有涉及的，所以对社交网络信息的检索成为了一门研究课题。

1.1 社交网络内容搜索

内容搜索是指给定查询，从大量信息中返回相关信息的过程。例如在微博上搜索相关热点事件名称，能够返回关于热点事件的微博。内容搜索是信息检索最经典的应用形式。经典的信息检索模型有向量空间模型（VSM），概率模型及 BM25检索公式，基于统计建模检索模型及查询拟然模型，基于统计语言建模的检索模型等。

针对微博的内容检索建模，目前有两种主要的方法:

时间先验方法：时间先验是由于语料库中的文档具有不同的重要性，考虑语料库背景定义不同的计算公式，再将计算结果用于检索模型以期得到更好的检索效果的一种检索方法。目前考虑时间信息计算文档先验的研究工作可分为两种：一种定义文档的时间变化关系；另一种为修改 PageRank 的方法，在其中加入时间关系。具体细节可参考：

Li, Xiaoyan, and W. Bruce Croft. "Time-based language models." Proceedings of the twelfth international conference on Information and knowledge management. ACM, 2003.

Yu, Philip S., Xin Li, and Bing Liu. "On the temporal dimension of search." Proceedings of the 13th international World Wide Web conference on Alternate track papers & posters. ACM, 2004.

多特征组合的方法：多特征组合方法是通过组合多个微博特性来检索微博内容。下面的参考文献中提到的微博特性有：微博个数，关注数，粉丝数，微博长度，微博是否含有外链。具体细节可参考：

Li, Nagmoti, Rinkesh, Ankur Teredesai, and Martine De Cock. "Ranking approaches for microblog search." Web Intelligence and Intelligent Agent Technology (WI-IAT), 2010 IEEE/WIC/ACM International Conference on. Vol. 1. IEEE, 2010.

1.2 社交网络内容分类

面向文本的分类称为文本分类。分类包括训练和测试两阶段，简单地说，训练是根据已标注类别的语料来学习分类规则或规律的过程。而测试是将已训练好的分类器用于新文本的过程。不管是训练还是测试，都需要将分类对象进行特征表示，然后利用分类算法进行学习或者分类。以下社交网络中内容主题分类的相关参考文献，读者可自行查阅。

Liu, Zitao, et al. "Short text feature selection for micro-blog mining." Computational Intelligence and Software Engineering (CiSE), 2010 International Conference on. IEEE, 2010.

Yuan, Quan, Gao Cong, and Nadia Magnenat Thalmann. "Enhancing naive bayes with various smoothing methods for short text classification." Proceedings of the 21st International Conference on World Wide Web. ACM, 2012.

Ling, Xiao, et al. "Can chinese web pages be classified with english data source?." Proceedings of the 17th international conference on World Wide Web. ACM, 2008.

Zhang, Dan, et al. "Transfer Latent Semantic Learning: Microblog Mining with Less Supervision." AAAI. 2011.

1.3 社交网络推荐

推荐系统的出现早于社交网络，从亚马逊将其用于推荐商品，推荐系统一直在蓬勃发展。社交网络的推荐，我们常见的就是推荐好友，这是一种显性推荐。根据社交关系和社交行为进行的推荐属于隐性推荐，例如根据你微博的内容或者你好友的行为来给你推荐广告和商品。下面我们介绍几种基本的推荐方法：

协同过滤推荐：传统的协同过滤根据用户（user）和物品（item）信息构建矩阵，根本的原则是相似用户的选择也相似，例如 a 和 b 都喜欢 m，其中 a 还喜欢 n，那么 b 也有可能喜欢 m。在社会化协同过滤推荐中，我们可以利用用户之间的社交关系，弥补协同过滤矩阵中缺失的内容，从而使协同过滤的结果更加精准。

基于模型的推荐：

邻居模型：

Ma, Hao, et al. "Sorec: social recommendation using probabilistic matrix factorization." Proceedings of the 17th ACM conference on Information and knowledge management. ACM, 2008.

矩阵分解模型：

Funk, Simon. "Netflix update: Try this at home." (2006).

融入社交网络信息:

Jamali, Mohsen, and Martin Ester. "A matrix factorization technique with trust propagation for recommendation in social networks." Proceedings of the fourth ACM conference on Recommender systems. ACM, 2010.

2. 社交网络信息传播规律

信息传播是人们通过符号、信号、传递、接收与反馈信息的活动，是人们彼此交换意见、思想、情感，已达到互相了解和影响的过程。社交网络信息传播是指以社交网络为媒介进行信息传播的过程。研究社交网络信息传播的规律，有助于我们加深对社交系统的认识，理解社交现象。也有助于模式发现，大影响力节点识别和个性化推荐。下面主要介绍几种社交网络信息传播模型。

2.1 基于网络结构的传播模型

线性阈值模型（ Linear Threshold）：

Granovetter, Mark. "Threshold models of collective behavior." American journal of sociology 83.6 (1978): 1420-1443.

独立级联模型（ Independent Cascade）：

Goldenberg, Jacob, Barak Libai, and Eitan Muller. "Talk of the network: A complex systems look at the underlying process of word-of-mouth." Marketing letters 12.3 (2001): 211-223.

2.2 基于群体状态的传播模型

传染病模型（SI, SIS, SIR）, 传染病模型是经典的信息传播模型，网上有丰富的参考资料。

线性影响力模型（ Linear Influence Model）：

Yang, Jaewon, and Jure Leskovec. "Modeling information diffusion in implicit networks." Data Mining (ICDM), 2010 IEEE 10th International Conference on. IEEE, 2010.

2.3 基于信息特性的传播模型

在线社交网络中的信息承载着用户网上活动的所有记录，在信息传播分析时起着不可或缺的重要作用。信息本身也具有一些特性，例如时效性，主体多样性，多源触发，信息合作与竞争等。依据这些特征，可建立不同的模型。

Myers, Seth A., Chenguang Zhu, and Jure Leskovec. "Information diffusion and external influence in networks." Proceedings of the 18th ACM SIGKDD international conference on Knowledge discovery and data mining. ACM, 2012.

Beutel, Alex, et al. "Interacting viruses in networks: can both survive?." Proceedings of the 18th ACM SIGKDD international conference on Knowledge discovery and data mining. ACM, 2012.

此外，对社交网络信息传播规律的研究还包括热度预测和信息溯源。感兴趣的读者可自行查阅了解。

3. 话题发现与演化

在话题发现和演化的大部分研究中，话题是指一个引起关注的事件或活动，及其所有相关事件和活动。其中，事件或者活动是指在一个特定的时间和地点，发生的一些事情。社交网络语料库中的数据和传统话题发现语料库的数据区别较大，所以我们必须使用新的方法或对传统方法进行改进来适应社交网络数据特点。

一般社交网络例如 Twitter 的数据有以下特点：数据规模大、内容简短、噪声多、数据特征丰富等。下面介绍几种主要的话题发现和演化模型。

3.1 基于主题模型的话题发现

最具有代表性的主题发现模型——LDA

Blei, David M., Andrew Y. Ng, and Michael I. Jordan. "Latent dirichlet allocation." Journal of machine Learning research 3.Jan (2003): 993-1022.

3.2 基于向量空间模型的话题发现

Salton, Gerard, Anita Wong, and Chung-Shu Yang. "A vector space model for automatic indexing." Communications of the ACM 18.11 (1975): 613-620.

Becker, Hila, Mor Naaman, and Luis Gravano. "Beyond Trending Topics: Real-World Event Identification on Twitter." ICWSM 11.2011 (2011): 438-441.

3.3 基于词项关系图的话题发现

词项共现是自然语言处理技术在信息检索中的成功应用之一。它的核心思想是词项之间的共现频率在某种程度上反映了词项的语义关联。最初学者们利用词项共现来计算文档的相似性，随后学者们利用该方法来完成话题词提取，话题句提取和摘要生成任务。

Sayyadi, Hassan, Matthew Hurst, and Alexey Maykov. "Event detection and tracking in social streams." Icwsm. 2009.

3.4 基于主题模型的话题演化

Yin, Zhijun, et al. "LPTA: A probabilistic model for latent periodic topic analysis." Data Mining (ICDM), 2011 IEEE 11th International Conference on. IEEE, 2011.

Wang, Xiaolong, Chengxiang Zhai, and Dan Roth. "Understanding evolution of research themes: a probabilistic generative model for citations." Proceedings of the 19th ACM SIGKDD international conference on Knowledge discovery and data mining. ACM, 2013.

3.5 基于相邻时间片关联的话题演化

Lin, Cindy Xide, et al. "The joint inference of topic diffusion and evolution in social communities." Data Mining (ICDM), 2011 IEEE 11th International Conference on. IEEE, 2011.

Saha, Ankan, and Vikas Sindhwani. "Learning evolving and emerging topics in social media: a dynamic nmf approach with temporal regularization." Proceedings of the fifth ACM international conference on Web search and data mining. ACM, 2012.

4. 影响力最大化

影响力最大化是在社交网络中选定信息初始传播用户，使得信息的传播范围能达到最大，即影响力最大。影响力最大化算法的目的就是找出一定数量的用户作为影响力传播的初始节点。对影响力最大化的问题的建模是基于社交网络信息传播模型的。其中最经典的模型是线性阈值和独立级联模型。

影响力最大化算法被证明为 NP-hard问题，下面主要介绍两种典型的影响力最大化算法。

4.1 贪心算法

贪心算法从单个节点开始，计算每选一个新节点作为初始节点对每个节点带来的边际收益，取能造成边际收益最大的点加入初始节点集合。贪心算法的缺点是计算时间成本较大，但是计算精度较高。

Kempe, David, Jon Kleinberg, and Éva Tardos. "Maximizing the spread of influence through a social network." Proceedings of the ninth ACM SIGKDD international conference on Knowledge discovery and data mining. ACM, 2003.

Chen, Wei, Yajun Wang, and Siyu Yang. "Efficient influence maximization in social networks." Proceedings of the 15th ACM SIGKDD international conference on Knowledge discovery and data mining. ACM, 2009.

4.2 启发式算法

不同于贪心算法选择任何一个点作为初始节点开始计算，启发式算法先通过一定策略选取一定数量的初始节点，然后计算其影响力传播。其优点是速度快，缺点是精度低。

Chen, Wei, Yajun Wang, and Siyu Yang. "Efficient influence maximization in social networks." Proceedings of the 15th ACM SIGKDD international conference on Knowledge discovery and data mining. ACM, 2009.

Chen, Wei, Yifei Yuan, and Li Zhang. "Scalable influence maximization in social networks under the linear threshold model." Data Mining (ICDM), 2010 IEEE 10th International Conference on. IEEE, 2010.

本文主要阐述目录前三章部分，后四章的内容（社交网络分析的应用、社交网络前沿研究、学习资料及参考资料）请见下篇（2017年9月26日二条）。

更多精彩请关注清华-青岛数据科学研究院官方微信公众号“THU数据派”