• 通过Generating Function转换为如下的Differential Equation:
• 假设网络由ER生成过程生成 • 通过在该网络上的扩散数据推测边的存在
• Peiyuan Sun. Inferring Multiplex Diffusion Network via Multivariate Marked Hawkes Process.
• 扩展至多层网络（仍基于ER生成过程）
4/30

m2t k2 )
1
p(ti

m2t ) k2

1

k
2
m2t (t m0
)
幂律分布 动态网路 单层网络
p(k) p(ki (t) k) k
2m2t 1 m0 t k 3
Ak 3
8/30
ppt课件
3. BA Model
幂律分布 动态网路 单层网络
• 优点
• 简单 • 节点度满足幂律分布，且为动态网络
• 该模型生成网络满足节点度的幂律分布 • 由生成过程可知为动态网络模型
10/30
ppt课件
4. PA Model with initial attractiveness 幂律分布 动态网路 单层网络
• 网络模型中非常有用的套路：
• Difference Equation & Generating Function Method
likelihood (G)
paij (1 p)1aij
ij
• 节点度分布为：
p(k) (np)k enp k!
3/30
ppt课件
2. Erdos-Renyi Model
泊松分布 静态网路 单层网络
• Barbieri, Nicola, Francesco Bonchi, and Giuseppe Manco. "Who to follow and why: link prediction with explanations." KDD2014.
• 该模型的Master Equation为：
11/30
ppt课件
4. PA Model with initial attractiveness 幂律分布 动态网路 单层网络
• 求解该Master Equation：
• 在t很大时，将差分转化为微分
• 在t很大时，假设网络分布极限存在
12/30
ppt课件
• 假设网络由ER生成过程生成（Dirichlet Distribution, Beta Distribution） • 通过节点上附着的标签信息推测边的存在及生成原因
• S. W. Linderman and R. P. Adams. Discovering latent network structure in point process data. ICML2014.
6/30
ppt课件
3. BA Model
• 单个节点的度演化：
ki t
m(ki )
m ki
kj j
=m ki 2mt
ki 2t
幂律分布 动态网路 单层网络
ki
(t)

t m(
ti
)0.5
7/30
ppt课件
3. BA Model
• 整个网络度分布：
p(ki (t)

k)

p(ti
4. PA Model with initial attractiveness 幂律分布 动态网路 单层网络
• 求解该Difference Equation：
• 假设生成函数： • 以及一些基本推论：
13/30
ppt课件
4. PA Model with initial attractiveness 幂律分布 动态网路 单层网络
9/30
ppt课件
4. PA Model with initial attractiveness 幂律分布 动态网路 单层网络
• 每个网络节点s拥有一个初始的吸引参数：A
• 每个时刻加入一个节点并引入m条边 • 网络中已存在节点s吸引其中一条边的概率为：
(s,t) qs A (m A)t
ppt课件
2. Erdos-Renyi Model
泊松分布 静态网路 单层网络
• 优点
• 简单高效 • 易与机器学习中概率图模型结合
• 缺点
• 与现实网络有出入
• 节点度为泊松分布而非幂律分布 • 不存在小世界现象 • 集群现象也很少见
• 效果一般 • 扩展的Watts-Strogatz网络满足Small World和Clustering，但仍为静态单层
多层网络模型及其应用
ppt课件
孙佩源 2017年4月19日
1
1. 背景
• 现实网络（社交网络、引用网络、脑网络等）并非完全随机
• 节点度服从power law（Scale Free） • 节点间平均路径长度很小（Small World）
• 现实网络动态增长
• 节点加入、撤离；边的添加、删除及重连接等
• 仍保持Scale Free和Small World特性
• 现实网络通常呈现多层特性
• 节点间存在多种连接关系
• 交通网络：公路，地铁，高铁等
• 层间关系影响网络的增长
2/30
ppt课件
2. Erdos-Renyi Model
泊松分布 静态网路 单层网络
• 假设节点间边的生成互相独立 • 整个网络的似然度为：
• 缺点
• 仍然与现实网络有出入
• 集群现象很弱 • 现实网络中节点度分布指数多有出入
• 只能作为一个解释型模型
• 用于生成随机网络 • 如LFRbenchmark即基于此模型的改进生成随机图
Lancichinetti A, Fortunato S. Benchmarks for testing community detection algorithms on directed and weighted graphs with overlapping communities.[J]. Physical Review E,2009. （引用量477）
网络
5/30
ቤተ መጻሕፍቲ ባይዱ
ppt课件
3. BA Model
幂律分布 动态网路 单层网络
• 每个时刻加入一个节点并引入m条边 • 网络中已存在节点i吸引其中一条边的概率为：
(ki )
ki kj
j
• 该模型生成网络满足节点度的幂律分布
• 由生成过程可知为动态网络模型
Preferential Attachment