在Hadoop中存储图形进行计算的有效方法

Question

我目前正在尝试在Hadoop的帮助下执行像聚类系数一样的巨大图表计算。因此，我需要一种有效的方式来存储图形，以便我可以轻松访问节点，邻居和邻居的邻居。该图非常稀疏，并存储在一个巨大的制表符分隔文件中，其中第一个字段是边界转到第二个字段中第二个节点的节点。

在此先感谢！

Answer 1

直接在HDFS中存储图形的问题是，您无法执行数据的随机读取。因此，要查找节点的所有邻居，必须在HDFS中处理整个边缘列表以查找连接到该节点的节点。

因此，要执行聚类系数计算，您需要将所有数据传递两次。第一次找到连接到起始节点的节点。第二次了解这些节点是如何相互连接的。

每次你想在图表中出现另一个级别时，你都需要处理整个图表来找到新的连接。

这是一件容易的事情，很好，是的。时间效率高吗？这实际上取决于你希望如何快速计算像LCC这样的事情，以及你的图表有多大。它不会接近实时。

另一种方法是使用HBase以某种方式存储边缘，这将使您能够以并行方式随机访问节点。毕竟HBase是hadoop的一部分。

如果您想以平行方式存储大图，可能会感兴趣的可能是FlockDB。它是Twitter最近发布的分布式图形数据库。我没有使用它，但它可能值得一看。

Answer 2

如果您想以逐个用户的身份执行此操作，HBase/Cassandra可能会工作。将边缘存储在列族中：user_a_id是行键，user_b_id是列键（具有空值）。 FlockDB不太适合（他们明确引用“图形步行查询”作为非目标）

如果您希望计算整个图中的聚类系数 - 也就是做一个巨人高效的计算 - 我会使用Hadoop。有一些注意事项（见下文），你可以很直接地做到这一点;在infochimps上，我们在具有数百万个节点+边的强链接twitter图上使用了Wukong。

如果你的数据集有很高的偏差，那么无效的做法是从每个节点天真地进行2跳广度优先搜索。思考Twitter的后续图表：跟随@wholefoods的170万人拥有60万次外出边缘，以争夺1万亿2跳。使用强大的链接使得这更容易（大大减少了歪斜）;否则，做一些局部聚类并迭代。