Community Detection – 思考:什么样的算法才有效

根据我非常有限的调研观察,community detection算法大致的思路有两类:
1. clustering的思路。定义一个距离公式,能够衡量两个node之间的距离。然后根据距离公式进行聚类;
2. graph partitioning的思路。定义一个度量指标,然后切割graph使得指标最优化;

关于clustering的方法,Lei Tang老师在一个PPT中提到了这个问题: CD != Clustering

image

image

Lei Tang老师主要认为,传统的clustering的方法并不完全适用于graph这种特殊的数据。

而在我看来,无论是clustering,还是graph partitioning,对于Social Network的community detection,都不够好。

注意,我特指了Social Network。例如,如果是对Youtube的video进行community detection,我认为无论是clustering的方法,还是partitioning的方法,应该都能够取得不错的效果。但是对于Social Network,情况不一样。

Social Network一个最大的特点,是community的overlapping。绝大部分的人,它其实都属于多个community。social network上会有同事圈,还会有同学圈。而当所有的人都是处于多个community的时候,他们构成的网络就是一个非常密集,没有什么几何特性的网络。这样的large-scale social network和平时做实验用的小规模的网络是完全不一样的。很难找到一个cut能够将网络很好的分开,所以graph partitioning的方法我预测不会有太好的效果。clustering的方法亦是同理。

另外一个问题是,无论是clustering还是graph partitioning,会将network中的每一个node都分类,每一个node一定会有一个所属的community。而在social network中,情况不是这样。有一部分人会归属于多个community的同时,还有相当一部分人可能不属于任何的community。

不解决好以上的两个特性,我不认为能够有效的对social network进行community detection。而目前的算法,其实都没有解决这两个问题。所以,其实都不够好。

Advertisements
相册 | 此条目发表在Community Detection, Social Network分类目录。将固定链接加入收藏夹。

One Response to Community Detection – 思考:什么样的算法才有效

  1. bmw说道:

    基于EGO网络的划分完美解决这个问题,我在IM上验证,完美无缺

发表评论

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