定义网络社区的参考标准并评估

sndnyangd

论文标题： Defining and Evaluating Network Communities based on Ground-truth  

论文链接

作者： Jaewon Yang 和 Jure Leskovec

网站： snap

我在博客上的总结： 博客地址

本文在社区发现领域绝对算是做出了巨大贡献。 对于定义比较多样又复杂的社区， 一般论文也就不断地提出改进方法， 在自己的一亩三分地上闹腾。 本文的贡献却能给所有此领域的研究者极大的帮助， 将手工时代提升到了信息化时代， 估计以后能作为标准了。

作者们自己描述， 本文的贡献在于：

1. 对230个大规模的社交、信息网络，用一种可靠的方法，定义了参考标准（ground-truth）社区
2. 基于ground-truth，量化评估了网络社区的13种常用的结构化定义， 并检验了它们的稳定性和敏感性
3. 扩展了局部谱聚类算法， 得到一种无参社区发现方法， 可支持百万点级别的网络检测




首先是定义了参考标准社区， 而且是为若干个大规模的网络数据。 以前若手工标注、 评估社区的话， 也就几百上千的级别， 现在则是百万、千万的级别。

定义参考标准社区的原则如下：

1. 社交网络的社区， 基于特定主题的分组
2. 购物网络， 基于层次化组织的货物分类
3. 科研合作网络， 基于相同的出版组织（会议等）

原则思想非常简单， 虽然没有包含所有方面， 只涉及了三种。 诸如， 生物网络等其他的并没有定义。



其次量化评估了 13种网络社区的评分函数（结构化定义），  做了实验检验。

本节主要都是在做实验分析， 用上了各种诸如相关性、 Z-score 、干扰评估等多种检验。

1. 评估那13种评分函数的相关性， 并分成了四组。



2. 定义了四种效果度量指标， 可以视作是一种评估框架， 某种方法得到的结果再用其他方法来评估。

3. 评估了其中几种代表性评分函数， 对噪音干扰的稳定、 敏感性。使用了四种给社区数据加噪音的方法。

个人认为， 本节算不上提出多新的方法， 但这种做实验、 做分析的态度、 作风还是很值得学习的，  而且作为顶级会议论文， 如何设计实验也是很有参考价值的。



最后一块是提出一种无参社区发现方法， 并检验了该方法的效果（准确度）。在前面部分有强调这个方法可处理百万级数据， 但并没有列出相应的实验数据。

算法描述如下：



第四步使用了某种启发式方法。 步骤如下：

1. k从小到大， 将局部极小的点作为备选点——At some point k∗, f(Sk) will stop decreasing and this k∗becomes our “candidate point” for a local minimum
2. 若 备选点之后， f(Sk) 上升， 并最终超过αf(Sk∗)， 则该 k* 点为有效点， 没超过αf(Sk∗)， 则无效。经试验， α = 1.2  最佳。

这种方法没有明确地说明， 不知道怎么想出来， 不知道有没有理论支撑， 还是纯粹从数据试验结果试出来的。




总结：

本文的实验思路非常严谨、 认真， 也可作为一种参考标准

本文提出的社区发现方法 相比之下， 就是一普通的算法了。虽然感觉里面用的启发式方法 对后面FOCS 论文的方法有点影响， 但FOCS里只提这篇的数据集， 没提他们的划分方法来源于哪里。

本文定义的参考标准社区数据已公开， 可在 网站： snap 中下载。 用了非常简洁的思想， 形成了标准， 能极大地失去此领域的发展。