社交网络挖掘-Note1

1-概论

从社会的角度去分析和理解个人的行为。

“人的本质并不是单个人所固有的抽象物。在其现实性上，它是一切社会关系的总和”——马克思《关于费尔巴哈的提纲》

“社会不是由个人构成，而是表示这些个人彼此发生的那些联系和关系的总和”—— 《马克思恩格斯全集》V.46, P.220, 人民出版社, 1979年

社交网络概述

由英国⽜津⼤学的⼈类学家罗宾·邓巴（Robin Dunbar）于2009年提出：根据猿猴的智⼒与社交⺴⽹网络推断出：⼈类智⼒将允许⼈类拥有稳定社交⺴⽹网络的⼈数是148⼈，四舍五⼊⼤约是150⼈。因此，150⼜称邓巴数字。

该定律指出：⼈的⼤脑新⽪层⼤⼩有限，提供的认知能⼒只能使⼀个⼈维持与⼤约150个⼈的稳定⼈际关系，这⼀数字是⼈们拥有的、与⾃⼰有私⼈关系的朋友数。也就是说，⼈们可能拥有150名好友，甚⾄更多社交⺴⽹网站的“好友”，但只维持好与现实⽣活中⼤约150个⼈的“内部圈⼦”。⽽“内部圈⼦”好友在此理论中指⼀年⾄少联系⼀次的⼈。

社会网络分析

为理解⼈类各种社交关系的形成、⾏为特点以及信息传播的规律，采⽤相关的分析⽅法，涉及信息学、数学、社会学、管理学、⼼理学等多学科的融合理论和⽅法

社会网络分析⽅法基于⼀个直觉性观念，即⾏动者嵌⼊在其中的社会关系的模式对于他们的⾏动结果有重要的影响，社会网络分析者则⼒求揭⽰不同类别的模式

社会网络分析的特点包括

源⾃于联系社会⾏动者关系基础之上的结构性思想
以系统的经验数据为基础
⾮常重视关系图形的绘制
依赖于数学或计算模型的使⽤

社会计算

2009年2⽉，美国哈佛⼤学⼤卫·拉泽（David Lazer）等15位美国学者在《Science》上联合发表了⼀篇具有⾥程碑意义的⽂章《Computational Social Science》

社会计算（Social Computing），⼜称计算社会学（Computational Social Science）。⼀般指社会⾏为和计算系统交叉融合⽽成的⼀个研究领域，研究如何利⽤计算系统帮助⼈们进⾏沟通与协作，如何利⽤计算技术研究社会运⾏的规律与发展趋势。

社会计算的研究目标

1）在深⼊理解当前社会问题动态性、快速性、开放性、交互性、数据海量性和复杂性的基础上，为解决新兴社会问题建⽴统⼀的社会科学基础模型和理论框架；

2）社会科学基础模型和理论“计算化”或建⽴其到计算技术的映射机制，研究与社会相关应⽤中的建模与计算⽅法，⾃下⽽上地为解决新兴社会问题提供整套理论和技术⽀撑；

3）深化学科交叉研究，为⺴⽹网络化社会背景下的社会科学研究提供实验⽅法；同时，以新兴问题促进相关研究领域内涵和内容的延拓，推动基础理论和⽅法的创新和突破。

而社交网络挖掘是社会计算的研究内容的一部分。

社交网络挖掘

Social Media Mining is the process of representing, analyzing, and extracting meaningful patterns from social media data

社交网络挖掘的挑战：

大数据悖论
- 个体数据是往往是稀疏的，因此才需要汇聚群体/整体的⼤大数据
  - 举例：社会推荐中的冷启动问题
- 个体⾏行为模式不能简单等同于整体，因此不能是个体的简单相加来代表整体，也不能整体的简单拆分来刻画个体
数据采集与获取：爬虫、API等需要掌握的重要技术⼿手段
数据清理与噪⾳音消除
- ⼤大数据可以允许个体数据的错误，但不等于不需要数据清理
- 消除噪⾳音个体trade-off 个体数据价值挖掘
性能/作⽤用评价
- ground truth（事实/标准答案）如何获取？
- 没有客观标准答案的如何评价？
- 数据挖掘出来的模式/结果能否解答“为什么”？

数据分析/挖掘的结果往往能较好地解释 what/where/when/how many/how often 但较难回答why

我们面对的是社会学的问题，我们⽤用交叉的思想去寻找解决方案，并利⽤数学和信息学的手段来解决它。

2-图论基础

图是网络结构的数学模型

网络问题一般可以转化成一个图论的问题

微博信息传播网络：Given a piece of information, a network of individuals, and the cost to propagate information among any connected pair, find the minimum cost to disseminate the information to all individuals.
科尼斯堡问题：奇点的数目不是0个(起点即终点)就是2个（一个是起点，一个是终点）
欧拉环路：途经每条边恰好一次，起点=终点
哈密顿回路（点之间只能遍历一次
四色猜想/问题（拓扑学topology 原意“地质学”）

图的基本结构

结点/节点 vertex/node：用户 user/actor、组织、网络、各类资源item/resource（商品、电影、音乐、论文）
边 edge：有向图，入度邻居 Nin，出度邻居 Nout
- 边的重数：具有相同始点和终点的边称为平⾏边，平⾏边的条数称为边的重数
度 degree
- 度数为1的结点是悬挂结点，其关联的边是悬挂边
- 度数为0的结点是孤⽴点
- 度分布
图的密度：实际边数与理论上最⼤的边数之⽐
- 对无向图，\({L\over n(n-1)/2}\)
- 有向图，没有系数 2

一些简单的结论

无向图中，所有节点的度数之和是其图中边数的两倍
无向图中，度数为奇数的节点有偶数个
有向图中，所有节点的入度和等于出度和

图的表示

图的同构 graph isomorphism

如果图 G 中的结点集 V 与图 G’ 中的结点集 V’ 具有一一对应的关系，并且对应的边都具有相同的重数，则称 G 与 G’ 同构，记作 \(G\cong G'\)。
因此，两图同构必须满足下列关系：节点数、边数相同、度数相同的节点相同。（必要非充分）
判断：双射函数

图的类型

零图 null graph：没有节点没有边
空图 empty graph：边集空，节点集可以非空——零图是空图
完全图 complete graph：任何节点之间有边
无向/有向/混合图
补图：由图G中的所有结点和构成完全图需添加的边所组成的图称为G的补图，记作 \(\bar G\)
简单图：两节点间最多一条边
多重图 multigraph：可以多条边
带权图/赋权图
标号图：权重用+/-或0/1等二元表示
树与森林：
- 树是特殊的⽆无向图，没有回路
- 树的任意两点之间恰好有⼀一条路径
- 森林由多个互不相连的树组成
生成树 spanning tree
- 包含图中所有结点的树型子图
- 带权图中，权重最小的生成树为最小生成树（也可能多个）
斯坦纳树 steiner tree
- 对于带权图的一个结点子集 V’，包含这个子集中所有结点且权重之和最小的子树即斯坦纳树
- 与最小生成树的区别在于，由于关注的一个图的子集，也就意味着在所给定的节点之外利用额外的节点以减少网络的代价
正则图：所有结点的度数相同，k-正则图
二分图/二部图 bipartite graph
- 所有的结点分为两个集合，每条边的两个端点分别在这两个集合中，即同一集合的结点间没有边相连
- An affiliation network is a bipartite graph. If an individual is associated with an affiliation, an edge connects the corresponding nodes.
- 例如这样的隶属关系网络，还比如，推荐算法：找出连个兴趣相似的人，以购买的书的数量决定，在图中表现为（用户间）通路数量
多分图多部图 multipartite graph

用户-标签-电影（三类结点）

图的连通性

相邻节点 adjacent
- 一条边联结的两个点
相邻边 incident
- 无向图：具有相同端点
- 有向图：一条边终止结点必须是另一条便的开始结点，即两条边方向一致
路径 path
- 依次遍历相邻边产⽣的结点序列称为路径
- 简单路径 path：不包含重复节点（所以也没有重复边）的路径称之为简单路径（本课程重点）
- 起点和终点相同，但其他结点都不重复，且至少包含三条边的路径称之为回路/圈（cycle），即闭合 path
通路 walk: sequence of incident edges visited one after another
- 依次遍历相邻边产生的边序列称之为通路
- 开通路 open walk：起始结点不同于终止结点
- 闭通路 closed walk：起始结点和终止结点是同⼀个结点（圈）
- 通路长度 length of walk：通路中遍历的边数量
- 简单通路 trail：每条边只遍历一次的通路
- 环路 tour/circuit：闭合简单通路

哈密顿回路 Hamiltonian Cycle：遍历了图中所有结点的回路

欧拉环路 Eulerian Tour：图中所有边均只被遍历⼀次，Konigsberg bridges

连通性
- 图中任意两个结点间存在一条路径，则为连通图
- 有向图中，图中任何两个结点都有路径（不考虑沿边的方向前进），则为弱连通图
- 有向图中，考虑沿着边的方向前进，图中任何两个结点存在有向路径，则为强连通图
连通分支
- 若子图中任意两个结点间存在一条路径，则该子图为连通分支（连通分量）
- 有向图中，连通分支内任何两个结点u, v，无论是 u 到 v 还是 v 到 u，都存在有向路径连通，则为强连通分支
最短路径
- 连通图中任何两个结点之间长度最短的路径为最短路径，其长度为该两个结点间的最短距离
- 图中所有结点对的最短路径平均值为图的平均路径长度，或称之为特征路径长度
- 结点 v 的 n 阶邻居（n-hop neighbor）是指所有到 v 的最短路径不大于 n 的结点
直径
- 图中任何两个结点之间最短路径的最大值为图的直径（社交，聚拢程度）
- 直径只定义在连通图中
桥
- 移除某条边会导致图中连通分支增加，这样的边为桥
- 桥是超大连通分⽀形成的关键

图算法

随机游走：带权图上的
图/树遍历 Traversal：BFS、DFS
最短路径：Dijkstra 算法，针对非负带权图，建立一个优先队列
最小生成树：Prim 算法，从一个初始节点，每次在边缘中找最小的那条边
网络流算法：给定一个图 \(G(V,E,C)\) 其中 C 是每条边的容量 capacity，有向，要求从 \(s\) 到 \(t\) 的最大流，注意其需要满足，1. 网络上的流是有方向限制的；2. 对于每个节点的流量守恒。
- Ford-Fulkerson 算法
- 基本思想：寻找⼀条从源点到汇点的路径，使路径中的所有边都有未使⽤的容量，使⽤该容量（路径上所有边中未使⽤的最⼩容量）去增加流，不断迭代直⾄没有其他路径可⽤。
- 核心就是定义一个残流网络：对于某一条边 \((u,v)\) 来说，若是还有剩余容量则画出 \((u,v)\) 边和剩余流量；若是有流经过此边则画反向的边 \((v,u)\) 权重是流过这条边的流量；注意后者是关键，对于正向流入此边的流来说，若是其他边满足条件，可以产生相反的流从而得到增量。
二分图的最大匹配
- ⽤⼆分图 G 表⽰⽤户和商品，以及他们之间的兴趣关系
- 匹配M是 G 中边集合 E 的⼀个⼦集，使得 G 中每个结点⾄多出现在 M 的⼀条边上（即每个⽤户⾄多买⼀个商品/每个商品⾄多卖给⼀个⽤户）
- 何以在二分图的前后分别加 \(s,t\) 利用最大流算法解决。

3-网络度量

我们需要从网络中找出核心的节点。

中心性度量

Degree centrality: ranks nodes with more connections higher in terms of centrality
- 有向图中，可以用
\(C_d(v_i)=d_i^{in}\) , prestige

\(C_d(v_i)=d_i^{out}\) , gregariousness
- Normalized Degree Centrality：可以用理论最大度/图中最大度/图中度之和进行归一化
特征向量中心性
- Eigenvector centrality generalizes degree centrality by incorporating the importance of the neighbors (undirected) 朋友多不一定重要，要有重要的朋友才是关键
- 计算公式 \[ C_e(v_i)={1\over \lambda}\sum_{j=1}^nA_{j,i}C_e(v_j)\\ \lambda C_e=A'C_e \] 其中 A 为邻接矩阵，于是就变成了求特征向量的问题，其中 \(\lambda\) 为对应的特征值
每个节点的中心性应该都为正，而根据 Perron-Frobenius 定理，可以通过求 A 的最大特征值对应的特征向量得到
Katz Centrality
- 注意到上面的 Theo 中似乎要求是在连通图的情况下，所以特征向量中心性一般在无向图中较为稳定；而在有向图中，中心性将从有向边中流出，在一定情况下，例如图是 acyclic 的，则可能出现某一个节点有很多入边但是中心性为零的情况
- 在此基础上加了偏置项 \(\beta\) \[ C_{Kate}(v_i)=\alpha\sum_{j}A_{j,i}C_{Kate}(v_j)+\beta\\ C_{Kate}=\alpha A'C_{Kate}+\beta\mathbf 1\\ C_{Kate}=\beta(\mathbf I-\alpha A')^{-1}\mathbf1 \] 其中第一行加了偏置项；整体写成第二行的形式；解析解是第三行的样子，注意到涉及到矩阵求逆，而我们知道当选取 \(\alpha={1\over\lambda}\) 时 \(det(I-\alpha A')=0\) ，会出现问题，所以一般会取一个小一点的数值。
PageRank 中心性
- 想法是「权威的出边并不一定是权威」，因此对传递的权重进行衰减，于是有 \[ C_p(v_i)=\alpha\sum_{j}A_{j,i}{C_p(v_j)\over d_j}+\beta\\ C_p=\alpha A'D^{-1}C_p+\beta 1\\ C_p=\beta(I-\alpha A'D^{-1})^{-1}1 \]
- 类似的，若 \(\lambda\) 为 \(A'D^{-1}\) 的最大特征值，我们要求 \(\alpha<{1\over\lambda}\)
- 当然，这和我们熟悉的 PageRank 公式不太一样，差别只是两个权重的形式，我们可以从随机浏览的角度来理解。
Betweenness Centrality 中间/中介中心性
- 从一个节点在网络上连接其他节点意义上的重要性 \[ C_b(v_i)=\sum_{s\ne t\ne v_i}{\sigma_{st}(v_i)\over\sigma_{st}} \] 其中分母是从 \(s\) 到 \(t\) 的最优最短路径，分子是这些路径中经过 \(v_i\) 的数量；这样定义的中心性可能对大于 1，因此需要进行归一化操作，最好情况下，对于所有的 \(s\) 和 \(t\) 来说分式均为 1，于是极大值为 \(2\binom{n-1}{2}=(n-1)(n-2)\) 除掉即可 \[ C_b^{norm}(v_i)={C_b(v_i)\over 2\binom{n-1}{2}} \]
Closeness Centrality 接近中心性
- 想法是你距离其他节点有多远
- 因此，考虑公式 \[ C_c(i)=1/({1\over n-1}\sum_{j\ne i}l_{i,j}) \] 其中 \(l_{i,j}\) 为 i 到 j 的最短路径长度
- 接近中心性高的节点往往是社交网络信息传播的关键人物

群体中心性

基于上面的对于单个节点的中心性讨论，可以将这些概念拓展到一组结点的中心性度量

传递性与相互性 Transitivity and Reciprocity

传递性

传递性和相互性用于表示社交网络总个体间的连接行为。

其中，传递性的思想是：若 BC 两人拥有一个共同的朋友 A，则 BC 之间未来成为朋友的可能性也会提高，即，我朋友的朋友也是我的朋友（考虑现实场景下的情况，可以联系到社会学、经济学的各种理论）。从网络结构的角度来看，就是容易形成紧密连接的三角形，三元闭包。

三元闭包的数量体现了图的传递性强弱，通常用 聚类/聚集系数 cluster coefficient 来表示传递性。

以下定义 Global Cluster Coefficient: Count paths of length two and check whether the

third edge exists \[ C={|Closed\ Paths\ of \ Length\ 2|\over |Paths\ of\ Length\ 2|}, or\\ C={(Number\ of\ Triangles)\times6\over |Paths\ of\ Length\ 2|} \] 这里关注的是 path，因此计算起来是有方向的，更为简单的计算方法是根据 三元组 Triple，即关注一组结点，没有方向，一个三角形中包含三个不同的 Triple \[ C={(Number\ of\ Triangles)\times3\over Number\ of\ Connected\ Triples\ of\ Nodes} \] 基于上面的思想，还可以定义 Local Clustering Coefficient: Computes how strongly neighbors of a node 𝑣 (nodes adjacent to 𝑣 ) are themselves connected

\[ C(v_i)={Number\ of\ Pairs\ of\ Nerghbors\ of\ v_i\ That\ Are\ Connected\over Number\ of\ Pairs\ of\ Neighbors\ of\ v_i} \]

相互性

相互性是传递性在 有向图 中的简化表示。例如，在微博上好友之间的相互关注，即，如果你是我的朋友，那么我也是你的朋友。

结构平衡与社会地位 Balance and Status

结构平衡

结构平衡理论由 Cartwright 和 Harary(1956) 在 Heider(1946) 提出的平衡理论基础上形成的；该理论认为，由于不平衡的三角关系是心理压力和心理失调的原因，人们在人际关系总试图让他们尽量少地出现，因此在显示社交网络中，不平衡三角关系要比平衡三角关系少。

社会地位

Status: how prestigious an individual is ranked within a society

既然社会地位是一个 rank，其满足不等关系的传递性。例如下面的左图即不符合社会地位理论，而右图则是符合的；另外，需要注意到，虽然这里都用符号图来进行表示，但要注意 Status 图和 Balance 图之间没有什么关系。

相似性 Similarity

网络节点相似性的度量有着重要的意义，

可以判定/预测结点间关联的重要程度
- 进行用户行为预测（第 9 章）：电影票房/产品市场预测、精准营销、个性化推荐
- 用户类别判定：垃圾用户识别、潜在用户预测、用户影响力估计

Structural Equivalence

在结构等价性中，We look at the neighborhood shared by two nodes; The size of this shared neighborhood defines how similar two nodes are.

下面的几个指标直接利用了节点 i 和 j 之间的共同邻居，并用不同的方式进行了归一化处理

还有另外的出发点：我们计算两点之间的共同邻居的数量，与其在随机连接下的期望值之间的差距。图中共有 \(d_j\) 的节点为 j 的邻居，而对于任一个结点，其与 i 的邻居的概率为 \(d_i\over n\) ，于是两者的共同邻居的期望值为 \({d_id_j\over n}\) ；而实际 i 与 j 的邻居数为 \(|N(v_i)\cap N(v_j)|=\sum_kA_{i,k}A_{j,k}\) ，于是

可以看到将 i 和 j 的连接关系表示向量看成随机变量的形式，则上面的差值可以写成两个随机变量 Covariance 的形式，进一步作归一化处理，得到 Pearson correlation coefficient

Regular Equivalence

在规则等价性中，我们不再关注两节点的共同邻居数量，而关注的是 How neighborhoods themselves are similar。其显示的考量是，例如两个运动员之间可能并不认识，但事实上其存在着很高的相似性（社交圈子，相似的教练、队友、经理人、球迷），这可以体现在社会网络上。

其代表性的度量模型为 SimRank，基于邻居节点之间的相似度来递归定义两个节点的相似度；基于递归度量的代价比较高，可以做适当放宽。

然后我们设法将其写成矩阵形式。这里的想法很巧妙，将求两个节点的邻居之间相似度的计算转化为了节点 j 和节点 i 的邻居之间的相似度（这样的转换是否会有一定误差？），然后就可以写成下面的矩阵形式；进一步基于相似性的意义加上一个 Identity matrix，从而得到最终的表达式。

和之前在 Katz 中心性时的讨论一样，我们一般假定选取的 \(\alpha\) 要小于 A 的最大特征值的倒数，从而使得该矩阵可逆。

其他度量方式

课上还介绍了其他的一些度量方式，例如

基于结点间路径
- Katz 度量：参考路径长度，相似度与路径长度成反比
- Hitting/Commute Time：考虑一个节点随机游走到另一个节点的概率
- Rooted PageRank/Personalized PageRank
基于图/网络嵌入的向量表示

4-网络模型 Network Models

网络属性 Properties of Real-World Networks

这些介绍一些能在不同的网络中使用一致方法来计算的属性，包括

度分布
聚类系数：衡量网络的 传递性
平均路径长度：衡量节点之间信息传播路径的长度 可达性

度分布

来看一些现实生活中的客观现象

更为常见的表述的 帕累托法则（二八定律）；更为精确的描述则是 Power-Law Degree Distribution 幂律分布 ；注意到这里归一化成了概率分布的形式，因此也称之为 Zipf 分布，来源于一个语言学家对于词汇使用频率的发现。

PPT 中介绍了 Zipf 分布的一些性质，在此略过。

补充：符合 Zipf 分布是 无标度网络 （scale-free network）的重要特征，即少数重要节点连接了很多的节点。在无标度网络中，数据存在着明显的 长尾现象。

聚类系数 Clustering Coefficient

平均路径长度 Average Path Length

随机图模型 Random Graphs

即图中任意两点之间的边的产生是随机的。

具体又可分为两类

\(G(n,p)\) 模型，假设网络中有 n 个节点，对于所有可能的 \(\binom{n}{2}\) 边中，每一条边产生概率为 p
\(G(n,m)\) 模型，固定图的边数为 m 从所有可能的边中随机选取 m 条

下面主要研究第一种情况，事实上当图较大的时候，我们可以选取 \(p={m\over \binom{n}{2}}\) ，两者是类似的。

我们可以证明以下的一些性质

在模型 \(G(n,p)\) 中，连接到一个节点的边的期望数为 \((n-1)p\) 条
整张图的期望边数为 \(\binom{n}{2}p\)
观察到 m 条边的概率为 \(P(|E|=m)=\binom{\binom{n}{2}}{m}p^m(1-p)^{\binom{n}{2}-m}\)

在随机图的演化过程中，有一个有趣的现象：当随机图的节点平均度数 \(c=1\) 时，会有大部分的结点被连接在一起，出现大连通分支 giant component，这时候的图直径很大，平均路径长度较长。

称之为 相变点 Phase Transition: the point where diameter value starts to shrink in a random graph

度分布

对于一个随机图来说，其每一个节点的度数的分布显示服从二项分布 \(Binom(p, n-1)\) ；当 n 很大的时候，可以近似为泊松分布 \(Poisson(c), c=p(n-1)\) 。

因此，随机图的度分布满足平均值为 c 的泊松分布，有明显的 尺度特征，其产生的网络 不是无标度网络。

另外，基于近似的泊松分布，PPT 中给出了「第二相变点」，即 When the graph is connected there are no nodes with degree 0 ，这里的假定是 \(P(d_v=0)=e^{-c}\le {1\over n}\) ，则据此计算得到的 \(c=\ln n, p={1\over n-1}\ln n\)

聚类系数

对于随机图来说，每个结点的聚类系数为 p。

可以通过条件期望公式来说明：假定其中一个节点的度数为 d，则去聚类系数为 \[ E(C(v)|d_v=d)={number\ of\ connected\ pairs\ of\ v's\ neighbors\over number\ of\ pairs\ of\ v's\ neighbors}={p\binom{d}{2}\over \binom{d}{2}}=p \] 利用条件期望公式 \[ E(C(v))=E(E(C(v)|d_v))=\sum_{d=0}^{n-1}E(C(v)|d_v=d)P(d_v=d)=p\sum_{d=0}^{n-1}P(d_v=d)=p \]

类似的，随机图的全局聚类系数也为 p

平均路径长度

在随机图中，平均路径长度为 \(l\approx {\ln|V|\over \ln c}\)

随机图模拟现实网络的能力

度分布并不遵从幂律分布
聚类系数远低于真实网络
只有平均路径长度接近真实网络

小世界模型 Small-World Model

也叫做 Watts-Strogatz (WS) model，由此二人在 1998 的 Nature 上提出来

模型的想法起源于 规则网/规则格 ，每一个节点连接其相邻的 c 个邻居。

规则网具有 较长的平均路径长度和较大的聚类系数（均要高于真实网络）

规则网中任一结点的邻居节点之间连接数量为 \({3\over8} c(c-2)\) （分为左右两种情况）
因此，其聚类系数为 \({3(c-2)\over 4(c-1)}\approx {3\over4}\)
规则网的平均路径长度为 \(n\over 2c\)

对规则网采用 边重连 的方法，可以让规则网逐渐过渡到随机网络。即对规则网中每一条边以概率 p 重新连接（固定其中一个端点）。若 p=0 则为完全规则网络；若 p=1 则为完全随机网络。

我们关心的是，如何选择合适的 p，使得重连后的网络能够近似真实世界的网络性质。下图绘制了聚类系数和平均路径长度在不同 p 值情况下的变化

可以看到 L 的下降比较快，我们可以选择合适的区间作为「小世界」模型，使得即能保证 L 比较小，又能维持较大的聚类系数

优先链接模型 Preferential Attachment Model

Proposed by Albert-László Barabási and Réka Albert，因此也叫 BA 模型；其想法类似于经济学的 马太效应：新加入网络的节点倾向于链接网络中度数比较高的节点。其可以较好地反映现实网络中的度分布（幂律分布）。新节点连接已有网络中任一节点的概率为 \(d_j\over \sum_kd_k\) 。该模型有以下性质

度分布：\(P(d)={2m^2\over d^3}\)
聚类系数：\(C={m_0-1\over8}{(\ln t)^2\over t}\)
平均路径长度：\(l\sim {\ln|V|\over\ln(\ln|V|)}\)

PA 模型的构建详见相关材料，其中 m 为期望度数。

马太效应

下面简单介绍了马太效应。1968 年 Robert K. Merton 提出这一效应来概括一种社会心理现象：「相对于那些不知名的研究者，声名显赫的科学家通常得到更多的声望，即使他们的成就是相似的，同样地，在一个项目上，声誉通常给予那些已经出名的而研究者。」

名字起源于新约圣经「马太福音」第二十五章：「凡有的，还要加给他叫他多余；没有的，连他所有的也要夺过来。」

流行度的上升，在初始阶段是比较脆弱的；一旦一开始就被充分肯定，在富者越富 the Rich-Get-Richer Effects 的推动下，其流行度可能变得更高。

详见论文。