0

我正在构建一个二分网络生成器，我正在使用 如何过滤 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));

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

最好的问候，西蒙娜

4

1 回答 1

1

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

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

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

这可能是最简单的解决方案；它根本不会涉及太多工作，真的。

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

于 2013-11-06T18:07:17.430 回答