机器学习和生物信息学实验室联盟

标题: 定义网络社区的参考标准并评估 [打印本页]

作者: sndnyangd 时间: 2016-6-17 17:33
标题: 定义网络社区的参考标准并评估
论文标题： 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 中下载。用了非常简洁的思想，形成了标准，能极大地失去此领域的发展。

欢迎光临机器学习和生物信息学实验室联盟 (http://123.57.240.48/)