Status and Friendship: Mechanisms of Social Network Evolution

Christina Brandt & Jure Leskovec
WWW 14 Companion

词汇概念

$n$ reciprocates
reciprocation to $n$

Abstract

• 使用了 Twitter, Flickr, DeviantArt, Delicious和 Yahoo!Answers 的数据，研究社交网络中社会关系的演化
• 研究几种社交网络下边建立的机制（edge creation mechanism）
• 社交网络中的边往复率（edge reciprocation rate）和底层结构差异巨大
• 两种机制可以解释这些差距（disparities）：有向三角闭包，导致状态指向行为（status-oriented behavior）；往复，导致伙伴指向行为（friendship-oriented behavior）
• 建模论证这些机制中的变量如何表示网络子图图案的差异
• 基于初始边创建行为来预测一个用户未来的影响力和入度

Introduction

原始问题

• 社交关系和网络结构的联系？
• 各种社交网络的区别在哪儿，为什么不同？

考虑方式

• 考虑有向演化图

  • 从而边形成的过程可以表示用户关系的建立
  • 考虑有向边：用户关系是不对等的
  • 考虑有向边：三元闭包的细节

• 组织调查

  1. 节点度数和局部结构（小型诱导子图 small induced subgraphs：网络基图 network motifs）如何影响边建立和边往复的行为
  2. 基于 friendship-oriented behavior 和 status-oriented behavior 建立网络生成模型，网络基图构建方式的不同可以解释这两种简单机制
  3. 节点的局部网络结构可以预测节点未来的显著性（prominence）。

Edge formation in context

五种网络：

• photo-sharing Flickr (photo-sharing)
• DeviantArt (art-sharing)
• Twitter (microblogging)
• Delicious (link-sharing)
• Yahoo!Answers (Q&A).

边建立和边往复

边往复和边聚集的差异无法单独用节点入度来很好解释，所以就写成一个基于入度的函数关系式。这个关系式可以认为是节点在社区中的地位。

• DA 网络可以用一个 status factor 解释：low-status 用户连向 high-status 用户。当节点的status 增长之后，它边往复越来越低，但它建立的边的边往复越来越高
• F 网络与 DA 相反，从high-status 连向low-status，low-status 的节点更多边往复
• Twitter 在两者之间

基图形成Motif formation

一个节点的局部网络结构提供了边形成的骨架结构，因为邻居节点在边建立中扮演了协调员（辅助商，主持人，facilitators）的作用

Modeling edge formation

边形成的原因可能是两种竞争机制：

• friendship → edge reciprocation
• status → visible as feed-forward transitive links（前馈传递链接）

一个简单的概念模型 $(S, \alpha, \beta, \gamma)$

模型定义

$S=\{(u,t)\}$ ，其中 $(u,t)$ 表示 $u$ 在 $t$ 时刻建立了一条边
$\alpha$ 控制往返
$\beta$ 控制前馈传递
$\gamma$ 控制随机链接

节点 $u$ 依据 $S$ 中的时间 $t$ 苏醒，并依据以下过程建立连接。

• 依据概率 $\beta$ ，节点 $u$ 形成前馈链接
  已知$u→ v → w$ ，有 $u→w$

• 按概率 $(1-\beta)$ ，$u$ 从网络中选择节点 $r$

  • 按概率 $(1-\gamma)$ , $u$ 停止并且建立连接$u→r$
  • 否则，$u$ 选择 $r$ 的一个邻居 $s$ 并连接 $u→ s$

• 不管边的类型，边有概率 $\alpha$ 往复。

实验配置和结果

• 在三个最大的网络上fit了该模型： Flickr, Twitter, and DA
• 使用粗粒度网格搜索（coarse-grained grid search）来估计参数，最小化网络基图的平方差
• 基图例如sibling and follower-of-friend会自然而然的在我们的模型中出现，但是它们不是简单的度数或者往复的产物
• Twitter 和 DA 都有较高的 $\gamma$ 导致高入度的名人。再结合 low $\beta$ 使用平均场分析可以达到优先链接
• 考虑互惠边（reciprocal edges）的话，模型拓展增加参数 $\rho>1$ 这样双向边的数量增加 $\propto\rho$

Predicting future prominence

由于网络基图可以用来刻画网络的演化，它们也许可以用来预测节点未来的行为。
给定节点最早获得的 $k$ 条边的情况，我们可以预测一个节点是否会 popular （未来是高入度还是低入度）

特征

不同于最大化效果，我们的目标是检验结构属性和边形成机制是怎样表征节点在社区未来的显著度。当每个节点 $u$ 获得了它的第 $k$ 条入边，我们计算以下特征：

• (AD) age and degree: 捕获节点的时间活动，例如：age, birth, outdegree, and rate to in-/out-degrees $k_0 < k$
• (N) Neighbor status and activity: follower/friend in-/out-degree
• (R) Reciprocation: 节点 $u$ 收到的往复边，$u$ 射出的和没有射出的往复边
• (NM) Non-motif: union of AD, N and R

---

• (MS) Motif-Source: 捕获 $u$ 指向其他节点的边中通过基图的。
• (MD) Motif-Destination: 基图中，$u$ 作为边的终点的
• (MA) Motif-All: union of MS and MD

实验设置和结果

分别对Flickr, Twitter, and DA预测90 120, and 180天之后边的入度出度。使用 logistic regression进行10-fold 交叉检验。 F1-score 有0.6-0.7.
在所有情况中，(NM+MA)对所有 $k$ 的效果都是最好。

• DA
  the ordering and gaps between the results are maintained as k increases
• Flickr
  non-motif features become more useful at higher degrees, but the relative importance of motif-based features also increases
• Twitter
  the gap between motif- and nonmotif- features eventually peaks, while reciprocation-based features are increasingly important at high k

基图特征在Flickr and Twitter中提高了准确率。并且总是提高了召回率。
对DA而言， 度数特征成功识别了一些活跃节点，尤其是 $k$ 较高的时候，基图特征使得算法可以区分的更好