Evolution in SN – Graphs over Time

Paper: Graphs over Time: Densification Laws, Shrinking Diameters and Possible Explanations

文章发表在kdd 2005上。而facebook 2004年才正式启动。所以这篇文章是online social network时代之前的作品,也是研究sn evolution领域早期的最有影响力的文章之一。

三位作者都是大神级别的,Jure Leskovec,Jon Kleinberg 和 Christos Faloutsos。

言归正传。

——————————-

文章的核心是指出了SN中的两个现象:

1. Densification Power Law
传统的看法,网络中节点的平均度数(average degree)在网络变化的过程中基本是一个定值,或者换个说法,节点数和边数之间是线性增长的关系。
而作者发现,随着网络的成长,网络的密度会越来越大,即节点数和边数是超线性的关系:

The networks are becoming denser over time, with the average degree increasing … Moreover, the densification follows a power-law pattern.

作者对4个网络的观察发现,节点数n(t) 和 边数e(t) 满足下面的公式:

image

是个指数的关系,a的值介于1到2之间。仔细想想,这是废话。当a=1的时候,相当于每个node有恒定数量的边,a等于2时,相当于node之间两两相连。实际的网络可不就介于两者之间么。其实更重要的是,作者发现,对于一个网络,它的a值基本是个固定的值,不太随时间而变化。

2. Shrinking Diameters
以前的研究都认为网络的直径是随着网络的成长缓慢的增长“slowly growing”。但作者很意外的发现,网络的直径随着网络的成长是在不断缩小的:

The effective diameter is, in many cases, actually decreasing as the network grows.

image

文章的后半部分,作者提出了一个“Forest Fire Model”,产生的network能够达到得到上面两个现象,同时还满足power-law degree distribution 以及 community。它产生的思路很有借鉴价值:

image

具体的做法是,对于一个新加入的节点v:

image

—————————-

文中有句话,今天读来很有意思:

real graphs are impossible to collect (like, e.g., a very large friendship graph between people).

— END. —

Advertisements
相册 | 此条目发表在Evolution in SN, Paper笔记, Social Network分类目录。将固定链接加入收藏夹。

发表评论

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / 更改 )

Twitter picture

You are commenting using your Twitter account. Log Out / 更改 )

Facebook photo

You are commenting using your Facebook account. Log Out / 更改 )

Google+ photo

You are commenting using your Google+ account. Log Out / 更改 )

Connecting to %s