狠狠撸

A geometric interpretation
for growing networks
孙佩源
2016.12.28

? scale free
? 节点度分布满足幂律分布
? strong clustering
? 与同一节点连接的节点对有较大概率连接
? significant community structure
? 通常节点出现集聚现象
Real Networks

Previous Work
? Erdos-Renyi Model [Erdos and Renyi, 1959]
? 假设任意两点之间的连接为独立同分布的伯努利随机变量
? Erdos-Renyi通常只是作为一个基准模型
? Stochastic Block Model [Nowicki and Snijders, 2001]
? 假设任意两点之间的连接依赖于一个表述节点所属类型的隐变量
? 只具有集群现象

Previous Work
? Preferential Attachment Model [Barabasi and Albert, 1999]
? 网络中新加入节点与已有节点连接的概率与其度成正比
? 最成功的地方在于发现citation网络中的幂律指数为3
? Preferential Linking Model [Dorogovtsev, 2000]
? 在Barabasi的基础上加入了节点的初始attractiveness
? 最成功的地方在于获得了初始attractiveness与幂律指数的关系表达式

Geometry Framework
? Hyperbolic Geometry Model [Krioukov and Papadopoulos, 2010]

Geometry Framework
? 网络节点由极坐标描述: (angular coordinate, radial coordinate)
? 不同于传统的Euclidean空间，Hyperbolic Space中两点距离为：
2
' ln
2
x r r
?
?
?
? ? ?
节点极半径 = K? ? 两节点角度差

Geometry Framework
? 假设我们可以将现实网络中的节点映射到Hyperbolic Space中
? 两点间产生连接的概率为：
? 则简单推导即可得：
( ) ( )p x R x? ? ?
距离小于R的连接概率为1
1
2 1,
2
( ) ,
1
2,
2
p k k r?
? ?
? ?
?
?
?
?
? ???
? ?
? ?
??
: 节点度满足幂律分布

Geometry Framework
? 进一步地，如果假设连接概率为：
? 则更进一步的推导可得：
1/
1
( )
1T
p x
x?
?
?
与集群系数成反比T

Geometry Framework
假设网络节点位于Hidden Hyperbolic Space和特定连接概率即可得
1. 生成网络中节点度服从幂律分布
2. 通过调节连接概率参数可以控制集群系数
Geometry Framework非常简单
并且满足现实网络的特性

Geometry Framework
? Popularity versus Similarity Model [Papadopoulos, Krioukov etc, 2012]
? 前述模型只考虑了popularity，而忽略了similarity
e.g：新的微博用户除了关注大V，还关注与自己兴趣相近的用户
? 前述模型只考虑了静态网络，没有考虑网络的动态增长

Geometry Framework
? Popularity versus Similarity Model [Papadopoulos, Krioukov etc, 2012]
1. 初始网络为空
2. 在时刻：
(a) 节点的极坐标为：，角坐标为：
(b) 早于的节点更新极坐标为：
3. 新加入节点与已经存在节点连接概率为：
1,2, ,i t? L
2
lnir i
?
? [0,2 ]U ?i
i
( ) (1 )j j ir i r r? ?? ? ?
( )
2
1
( )
1
ij i
ij
x R
T
p x
e
?
?
?
?

Geometry Framework
? Node coordinate inference [Papadopoulos, Krioukov etc, 2015]
1. 基于链接的推断算法
逐节点使用MLE求解:
原理为：
2. 基于公共邻居的推断算法
求出公共邻居节点的概率分布，然后使用MLE求解似然度函数
1
1
( ) [1 ( )]ij iji
L ij ij
j i
L p x p x
? ??
? ?
? ??
( ) ( , )ij ij i ip x r? ?: :
https://bitbucket.org/dk-lab/2015_code_hypermap

Geometry Framework
? Geometric correlations in multiplex network [Kleineberg, 2016]
主要结论：
1. 多层网络重叠节点在不同层的极坐标具有很强的相关性

Geometry Framework
主要结论：
2. 多层网络重叠节点在不同层的角坐标具有很强的相关性

Geometry Framework
主要结论：
3. 多层网络节点间链接概率具有很强的关联性

some preliminary experiments
? 数据集
序号事件总结点数总边数 MCC节点 MCC边节点比例
1 郭美美 153744 435515 67680 158551 44.02%
2 李庄 40989 70444 16216 30249 39.56%
3 钱云会 64596 165066 24882 53027 38.52%
4 夏俊峰 56405 79163 21567 29712 38.24%
5 药家鑫 215316 372219 79852 129829 37.09%
6 房价 525083 1292306 192383 432974 36.64%
7 9级地震 173700 286229 49076 75433 28.25%
8 钱明奇 44390 65206 10281 13550 23.16%
9 王功权 173619 165362 27701 32593 15.96%
10 中石化 86504 98116 11442 12832 13.23%
11 李刚 110523 128589 14291 15913 12.93%
12 宜黄 12886 8775 1534 1533 11.90%
13 邓玉娇 18739 16507 2155 2431 11.50%
14 个税起征点 51267 40115 3211 3269 6.26%
15 胶州路大火 107825 113908 5605 5790 5.20%

? 各层重迭节点分布

? 验证转发网络是否满足Hyperbolic结构
（1）是否满足幂律分布（原图）

（1）是否满足幂律分布（最大连通子图）

（2）集群系数是否满足（极大连通子图）

（2）集群系数是否满足（极大连通子图，10bin）

（3）Hyperbolicity是否满足（极大连通子图）
[Tree-like structure in large social and information networks, 2013, ICDM]
指出：可以使用树分解衡量图的hyperbolicity，树分解得到的tree width越低，
hyperbolicity越强

（3）双曲性是否满足（极大连通子图）

? 几个事件的笔辞濒补谤图

Reference
1. Krzysztof Nowicki and Tom A B Snijders. Estimation and prediction for stochastic
blockstructures. Journal of the American Statistical Association, 96(455):1077–
1087, 2001.
2. A.L. Barabási and R. Albert, Science 286, 509 (1999).
3. S.N.Dorogovtsev, J.F.F.Mendes and A.N. Samukhin, PRL, 2000.
4. Krioukov D, Papadopoulos F, Kitsak M, et al. Hyperbolic geometry of complex
networks[J]. Physical Review E Statistical Nonlinear & Soft Matter Physics, 2010,
82(3 Pt 2):98-118.
5. Papadopoulos F, Aldecoa R, Krioukov D. Network Geometry Inference using
Common Neighbors[J]. Computer Science, 2015, 92(2).
6. Kleineberg K K, Bogu?á M, Serrano M ?, et al. Hidden geometric correlations in
real multiplex networks[J]. Nature Physics, 2016.

狠狠撸

A geometric interpretation for growing networks

More Related Content

Viewers also liked (9)

More from sun peiyuan (8)

A geometric interpretation for growing networks

Editor's Notes