Evolution in SN–剖尸Friendster

“Social Resilience in Online Communities: The Autopsy of Friendster”这篇文章的笔记。

这篇paper最近在网上挺火的,好些科技类的网站都有关于它的报道,似乎是社交网络的一个重大发现。我也因此好奇找到这篇文章拜读了一番,说实话,挺失望的。必须得说,这篇文章找了个好方向,研究Social Network是怎样解体的(我也打算做点这方面的实验),而且呢,它号称是在一个真实的网络数据上做分析。但细读后会发现,文章本身没有什么很特别的结论,而且论证的过程本身我个人认为是有点问题的。BTW,这篇文章其实还是处于submit的状态,所以……

言归正传。

————————

继承自Diffusion相关理论的影响,一般认为一个用户是否加入/离开某个Social Network(SN)很大程度会受到好友的影响,同时,他的决定又会发过来影响到好友。按照这个理论,当SN成长的时候,往往是周围的好友越来越多的加入到了某个SN,带动用户自身的加入,同时用户的加入又会带动其他好友的加入(级联效应)。但是当SN衰退的时候,往往是一个用户的退出导致他好友的相继退出,最终像雪崩一样,是整个网络的崩溃。

作者用k-core decomposition来表达上述过程。所谓的k-core,就是SN中的一个子图,子图中的每个节点的度数都大于等于k。而k-core decomposition就是对一个SN不断的做剪枝,不断的剔除 degree<k 的节点,直到所有的节点degree >= k:

image

上图就是一个k=3的k-core decomposition过程。需要注意的是,A->B只是一次性将网络中的degree < 3的节点剔除,但k-core decomposition是要求连续迭代的剔除。所以一个真正的k-core decomposition过程应该是 A->C->D->E。

作者在3.3节中定义了一个“ rational model for OSN users”。这个model简单解释,它认为每个用户如果继续呆在SN中,有一个恒定的cost(简称c),同时这个用户又会从它的好友邻居那获得benifit(简称b)。对于一个rational user,如果b >= c,那么用户会继续留在SN中,反之,b < c,用户就会离开。而作者假定benifit是和用户的活跃好友数相关的,所以最后就能够推导出,如果用户的活跃好友数小于一定值(K),那么就会离开。(3.3节的实际说法要复杂的多,一大段的数学公式推导和论证,我反复琢磨了几遍,其实就是这个意思。最烦丫这种卖弄风骚的。)

所以,如果K=3的话,那么上图的A->C->D->E描绘的就是一个SN的用户逃离的过程。而最后E图中的这个k-core就是这个社交网络的social resilience。所以,一个网络的坚固性是由它的k-core的大小决定的。

从A->C->D->E还能观察到一点,并不是degree越大的节点就越不容易离开。例如原图中左下侧的那个星状节点,这个节点的degree=5,但问题是这个节点所连接的大部分都是low-degree node,所以它在decomposition的过程中也被剔除掉了。

到目前为止,最大的问题在于作者的前提假设是否成立?真实的SN的过程是否和作者想象的rational user model相匹配呢?如果不匹配,那么所谓的A->C->D->E这样的k-core decomposition就不能够代表SN衰退的过程。

接下来,作者对下面5个SN的数据做了分析:

image

它计算了每个SN的网络,当k=1,2,3,4,…的时候k-core的大小。下图就是Friendster和Livejournal的比较结果:

image

你会看到,Friendster的k值高的k-core节点还是非常多的(左侧的红色区域)。而Livejournal大部分都是k=1的节点(右侧的蓝色区域)。作者非常尴尬的发现,Friendster的高值k-core区域占据了整个网络的大部分,按照前面所说的,它的social resilience应该是很好的,而Livejournal相对social resilience要差很多。但是,Friendster已经死掉了,而Livejournal活得好好的。作者只好说:

For the case of the unsuccessful communities of Orkut and Friendster, it requires a much worse environment, with values of K above 60. This way, the emprical data supports the idea that, under the same environmental conditions, both successful communities is less resilient than the three unsuccessful ones. This means that the topology of their social network is not enough to explain their collapse, ….

这不是打自己的脸么。

最后,作者试图分析Friendster的解体过程,是否能够对应上假定的k-core decomposition:

image

因为没有Friendster的用户何时离开的数据,所以作者用google search volume(gsv)来代替表示某一时间点上还有多少的active user。例如2009年的gsv最高,表示那一时间点有78%的active user,大概52 million。大概对应k=3的k-core的规模。而2010年初根据gsv推断大概是15%的active user,约10 million,这些用户对应于k=67的k-core的规模。

然后作者就模拟k-core decomposition的过程,从k=3一直解体到k=67,然后发现这个解体的过程(红线)和gsv的曲线是几乎一致的。所以作者认为,一个SN的衰落过程很近似于k-core decomposition的过程。

——————————

总的来说,我认为这篇文章的说服力还欠缺了一些。他只有Friendster所有用户的uid和这些用户构成的网络,uid的大小可以表示用户加入网络的先后顺序。但是仅仅凭这些数据就想分析出这个社交网络的衰落过程,我认为是绝对不够的。所以无论它的实验做得多漂亮,对于结论我都只能够持保留态度,因为数据不完整。

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