社交网络演化中的局部传递性
人类动力学（human dynamics）研究者习惯于从系统的角度来分析问题；社会科学家则强调个体作为基本研究单位的重要性。系统的特性会作用于个体，个体的行动汇总起来可以塑造系统的全局特性。
连边局部特性
Leskovec等人(2008)尝试从个体出发，研究网络演化过程中的微观过程如何产生宏观的网络结构（如度分布、半径、聚类系数、社团结构）。Jure Leskovec, Lars Backstrom, Ravi Kumar, Andrew Tomkins在2008年KDD会议中发表了题为Microscopic Evolution of Social Networks的论文。他们发现除了偏好链接（preferential attachment），连边的局部特性（edge locality）在网络演化的过程中发挥着重要作用。
微观过程
他们首先将网络演化分为三个阶段：
- 节点的进入过程（node arrival process）：节点到达率（node arrival rate）的差异很大，可以使指数增长，也可以使亚线性增长，所以节点到达率作为模型的输入信息。
- 链接的发起过程（edge initiation process）：节点进入系统后，就开始建立链接，直到死掉。链接的间隔建立比率符合一个带有指数截断的幂率分布。Leskovec等发现链接的生成随着节点的中心度的增加而加速增长。
- 链接的闭合过程 （edge destination selection process）：leskovec等发现大多数链接的建立具有很强的局部性。局部性的测量通过起点和终点的距离来衡量（注意本文讨论的是有向网络的模型！！），因为多数起点和终点的距离是2，所以连边也就是在闭合三角形（close triangles）。说人话：多数链接是添加朋友的朋友（30%-60%）。什么样的三角闭合机制呢（即一个起点怎么选择终点呢）？他们发现节点从它所有的邻居中均匀地（uniformly）选择一个居中的节点建立链接具有最高的可能性（likelihood）。
最大似然准则
用来比较那些参数化模型生成的结果最好。应用方法：将网络演化看成链接逐条增加的过程。
- 对于任何一个新的边的建立（已知起点，未知终点（endpoint）），测量使用一个特定的模型的话，选择一个终点的似然率。
- 对于所有的连边都算一遍选择特定终点的似然率。
- 对于所有可能的模型算一遍上面的过程
- 根据这些似然率，选择最好的参数模型。
主要的竞争模型有$G_{n, p}$模型和PA模型，显然随机模型不靠谱，PA模型则主要考虑度分布、节点的年龄、共同作用。
真实数据链接数量随着节点距离（hops)的增加而指数下降；链接概率也跟节点距离负相关。两种度量PA和$G_{n, p}$模型的结果都不算好。
随机-随机三角闭合模型（RR）
作者转而提出所谓的三角闭合模型，主要是强调关系传递性（transtivity）在网络演化中的重要性。将模型的设定摘抄到这里（懒得翻译了）：
多数起点和终点的距离是2，即大多数边跨越了两步。因此简单的随机-随机三角闭合模型（random-random triangle closing model）效果不错. 随机-随机三角闭合模型可以参数化为 $N(·)$, $\lambda$, $\alpha$, $\beta$, 具体定义如下.
- 定义节点到达函数（新加入节点函数） N(·).
- 节点 u 出现并且从指数分布中抽取一个生命周期 a $p_{l}(a) = \lambda exp(−\lambda \alpha)$.
- 节点 u以正比于对方节点的度的概率添加第一条链接到节点v 。
- 一个度为d的节点u从分布 $p_{g(\delta |d; \alpha, \beta)} = (1/Z) \delta^{ − \alpha} exp(−\beta d \delta)$中抽取一个时间差（time gap） $\delta$ 并休眠$\delta$ 个时间点.
- 当一个节点醒来的时候，如果它的生命周期还没有结束，它就会根据随机-随机三角闭合模型（random-random triangle closing model）创造一个两步长的链接.
- 如果一个节点的生命周期到尽头了，它就会停止添加链接；否则它会重复步骤4
以flickr的数据来看，RR模型确实比PA要好。
参考文献
Jure Leskovec, Lars Backstrom, Ravi Kumar, Andrew Tomkins （2008）Microscopic Evolution of Social Networks. KDD. link video link
Leave a Comment