如何抽取无标度图

Question

给定一个大型无标度图（社交网络图），对样本进行抽样的最佳方法是什么样的，以便抽样保留原始属性的可接受抽象？

我有一个大图（Munmun的twitter数据集，如果你知道的话）。但我需要一个具有相当大直径（tl; dr ...的原因，为什么要求...直径10的直径是好的）的图表的连接样本。

问题是任何有点宽度优先的搜索总是可能遇到一些大规模连接的节点。所以我开始这样的搜索，得到我遇到的所有节点的朋友。我不可避免地遇到了一些大规模连接的节点，并且必须得到他们所有的朋友。这是一个问题，因为我最终得到了大量在图中彼此接近的节点。为了使程序分析可行，我必须限制节点（和边）的数量。这个练习的要点是找到节点之间的最短路径，所以我通常对节点的所有邻居感兴趣。这就是问题所在。

一个黑客围绕这是限制最大。连接到我感兴趣的用户的节点数。例如，如果我在我的广度优先搜索中遇到@barackobama，我确保我只接受一小部分朋友，而忽略其余部分。但是，这个被黑客入侵的图会值得该死，还是我在寻找最短路径方面失去了太多信息？

希望是有道理的......

Answer 1

我不知道，如果我正确地理解你的问题。我认为你的主要问题是关于如何计算巨型有向图中两个节点的最短路径。创建图的子样本似乎是您尝试创建高效的解决方案。 （但我可能完全误解你了。）

这或许SO-问题有一些指针你：Efficiently finding the shortest path in large graphs

在这个问题的图表似乎是显著更小，虽然。

Answer 2

存在几种取样方法，如何选择取决于您想保留的属性（除其他外）。我在论文Sampling and Inference in Complex Networks [Maiya '11]中找到了文献综述（第3节），对此很有帮助。

但是您似乎已经找到了抽样网络的方法，现在您想知道样本是否代表整个图的最短路径。你可以尝试看看这篇论文：Complex Network Measurements: Estimating the Relevance of Observed Properties [Latapy & Magnien '08]。他们描述了一种评估样本代表性的方法，涉及各种经典的拓扑性质。总结他们的方法，他们最初可以访问整个研究网络，并模拟一些取样过程中的这些数据，随着样本量的增加。他们监测性质如何随样本大小而变化，并在感兴趣的属性足够稳定时决定合适的大小。他们的工具是自由available online。

编辑：我可以在网上找到的唯一准备使用的工具是Albatross。相关文章Albatross Sampling: Robust and Effective Hybrid Vertex Sampling for Social Graphs [Jin et al。'11]也包含了对现有抽样方法的很好的评论，其中一些是在他们提供的源代码中实现的。编辑2：我需要在Linux系统上使用Albatross，所以我做了一个Java端口。这是非常原始的，但它似乎工作正常。它的问世在GitHub上：https://github.com/vlabatut/Albatross

Answer 3

您可能要检查以下内容：Gscaler：https://github.com/jayCool/Gscaler 这是最近的工具，它产生的合成比例图。

它包含jar文件和相关文章供您参考。