java - 如何从 KNeighborhoodFilter 中提取样本

Question

我正在构建一个二分网络生成器，并且我正在使用 How to filter the result of KNeighborhoodFilter? 中的代码当我的网络很小(5000 个节点)时它可以完美地工作。

现在我正在使用一个具有 60.000 个节点和 250.000 个链接的网络。为了加快速度，我想知道在提取节点的 2-dist 邻居时是否可以随机抽取节点样本，比如仅 50% 的 2-dist 邻居...

我真的不知道如何实现这一点，也不知道如果不破解 KNeighborhoodFilter 类本身是否有可能(我知道我无法做到这一点......)。

现在我获取结果并随机选择一个样本，但我不知道我是否走在正确的道路上:

Predicate<Node> onlyUsers = new Predicate<Node>() {
            @Override
            public boolean apply(Node node) {
                return node.getName().startsWith("u");
            }
        };
// find neighbors of nodes with degree i
Filter<Node, Edge> filter = new KNeighborhoodFilter<Node, Edge>(u, 2, KNeighborhoodFilter.EdgeType.IN_OUT);
// retrieve everything at distance 2 from node u
List<Node> twoDistNei = Lists.newArrayList(filter.transform(zpa).getVertices());
// sample the collection
List<Node> sampledUsers = Lists.newArrayList();
for (int i = 0; i < 2000; i++) {
   sampledUsers.add(twoDistNei.get(context.getRNG().nextInt(twoDistNei.size())));
}
Set<Node> sampledNodesHashed = Sets.newHashSet(sampledNodes);
Set<Node> twoDistUsers = Sets.newHashSet(Collections2.filter(sampledNodesHashed, onlyUsers));

我的目标是让这段代码运行得更快。非常感谢您抽出宝贵的时间。

最诚挚的问候，西蒙娜

Answer 1

如果您想更快，这里有几种可能的方法。它们都涉及一些黑客行为。 :)

(1) 修改 KNeighborhoodFilter 以获得一个以一定概率 p 遍历边的版本。
对此的概括是，您为每个跃点指定一个概率，即，对第一跳使用一个概率，对第二跳使用一个概率，等等
进一步的概括将为每个边使用单独的概率，可能基于所涉及的节点/边的某些属性(例如，如果目标具有高度数，则可能您希望或多或少地跟踪边)。

请注意，此解决方案需要认真考虑哪种随机抽样适合您的情况。如果您真正想要的是对完整结果中的节点进行统一随机采样，那么您基本上需要生成完整结果，然后对其进行过滤。

这可能是最简单的解决方案；实际上，这根本不需要太多工作。

(2) 创建 KNeighborhoodFilter 的修改版本，将工作分配给不同的处理器。您可能在具有 > 1 个核心的机器上运行它，因此您可以创建多个线程并让 Java 将它们分配给不同的机器；如果您确实想加快速度(并且您有适当的设置)，那么您可以将其分配给不同的机器，MapReduce 风格。