Evolution in SN – Group Formation in Large Social Networks

Paper: Group Formation in Large Social Networks: Membership, Growth, and Evolution的笔记

这是kdd2006年的文章,算是比较早的一篇研究SN中community的发展和变化规律的文章。基本上后续的文章都会refer这篇,应该算是比较经典的。作者之一,Jon Kleinberg…

———————–

文章的核心是在尝试回答三个问题:1. 什么样的structure feature会导致人们加入某个group/community; 2. 什么样的group能够快速的成长; 3. 如果我们认为group是基于某个topic而聚合,那么人们和topic之间的变化是怎样的;

image

为了解答这三个问题,作者用了两份数据进行分析。一份是DBLP,一份是LiveJournal。两份数据有个共同的特点,就是都有人为定义的group/community,于是作者就可以回避community detection这个麻烦。(SN的paper中大量的使用了DBLP和LiveJournal这两份数据,但说实话,我个人观点这两份数据都不太能够真正反映OSN。DBLP只是根据学术论文中作者的署名构建的一个network,它和真实的OSN是不一样的。LiveJournal本质应该还是一个博客论坛,也和facebook这样的OSN有区别。)

整体看,文章对于第一个问题是回答的最好的。对于第二个问题只能说有些发现。对于第三个问题,首先我个人不太理解这个问题有什么意义,其次,我不认为仅用DBLP的数据能得到什么有价值的发现。

第一个问题

和其它的文章一样,关于这个问题基本的假设都来自于diffusion的相关理论,认为人们是否加入一个group是和他朋友是否加入息息相关的:

An underlying premise in diffusion studies is that an individual’s probability of adopting a new behavior increases with the number of friends already engaging in the behavior

为了验证这一点,作者拿两份数据做了实验,计算用户加入group的好友数(k)和用户加入该group的概率(p)之间的关系,LiveJournal的结果如下图(a):

image

而传统的diffusion理论中,k和p的关系应该是类似于“s-shaped curve”,如下图(b):

Satellite

所谓的S Curve,基本上就是曲线的左侧是一个超线性的增长,慢慢的转换到右侧变成了亚线性(sublinear)。而作者得到的曲线,基本上是符合S Curve的,虽然它的超线性那一段曲线很短(k = 0,1,2)。

LiveJournal的结果表示用户加入group的概率和他的好友数非常相关。当好友数增多,用户加入该group的概率就越大,但是每个好友所带来的边际收益是递减的。

除了好友数以外,作者还试图分析其他可能影响到用户join group的因素。他提出了很多可能相关的因素,然后用decision tree构造了一个分类器,做feature selection。然后发现,这些好友之间的关联性(Internal Connectedness of Friends)也很影响用户的选择。group中的好友他们之间的连接越多,用户越有可能加入这个group。关于这点,作者给出了两个解释:
1. 从weak ties/structure hole的角度,“there is an informational advantage to having friends in a community who do not know each other — this provides multiple “independent” ways of potentially deciding to join.”
2. 从social capital的角度,“there is a trust advantage to having friends in a community who know each other — this indicates that the individual will be supported by a richer local social structure if he or she joins”

第二个问题

为了回答这个问题,作者同样用decision tree做了个实验。他对同一份数据,构造了两个snapshot,snapshot之间间隔了4个月。然后观察在早期snapshot中member > 100的这些community,他们在后期snapshot中增长了多少。计算得到增长率后,再构造decision tree来检验哪个特征最能够影响到增长率:

clipboard

Fringe表示community的边缘(和community有连接但不属于community的节点的数量)。
实验结果显示,无论是fringe还是community size,和community的增长都没有什么相关性。说明这两个特征不起作用。反倒是另外两个特征更有用:
1. 当community中有很多节点都有很多friends,这个community会成长比较快;
2. 当community中,存在大量的triangles时,增长会放缓;

clipboard[6]

我个人观点,这两个特征似乎也能找到合理的解释。但也谈不上很可信。

第三个问题

个人认为意义不大,也没细看。

— 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