MapReduce中的分层聚类实现具有代表性的链路社区的树状图

Question

我希望使用具有链接之间相似性的分层聚类来构建一个树状图，其中每片叶子都是来自原始网络的链接，分支使用MapReduce中的分层聚类来表示链接社区。任何参考方法算法将不胜感激。

Answer 1

分层聚类在MapReduce中将永远不能很好地工作。

首先，MapReduce设计为一次处理一条记录，而距离计算一次至少需要两条记录。由于这个原因，将基于距离的算法黑客到MapReduce通常是个坏主意；这就是为什么MapReduce现在几乎成了昨天的新闻。没有人再关注MapReduce了，除了预处理和过滤之外，它对任何东西都是太有限的。

此外，这也不会有多大帮助。分层集群规模本质上不好的原因是，在通常的实现中，它需要O(n^2)内存和O(n^3)运行时。因此，通过分布式实现获得的任何收益都只允许处理稍微大一些的数据集:如果添加8倍多的计算机，则只能处理2倍大的数据集。这显然不能满足可伸缩性的要求。另外，你还需要更多的磁盘空间。您真的希望O(n^2)磁盘空间可用吗？

最后但并非最不重要的是，如果你真的有大的数据，你将无法查看树状图无论如何。

如果您有大数据，请使用不同的算法。或者取样。

如果您的数据不是那么大，那么只需使用像埃尔基这样的单主机实现就可以了，这是相当快的。最有可能的是，它的性能将优于基于集群的实现，因为它可以避免使用mapreduce获得的所有额外磁盘IO。