java - 如何使用 JUNG 进行二部图的投影

Question

我在 JUNG 中创建了一个二分图，并且我希望对其中一组节点进行单模投影。在投影中，如果同一集合的两个节点有共同的属于另一个集合的节点，则它们将被链接。 JUNG 中是否有一个函数已经可以做到这一点？到目前为止我的代码(对于 1600 个节点的二分网络来说非常慢，其中只有 400 个属于我想要投影的集合)是:

public static void perform(UndirectedSparseGraph<Node, Edge> g, List<Node> companies) throws Exception {
    // 
    UndirectedSparseGraph<Node, Edge> oneMode = new UndirectedSparseGraph<>();
    // 
    for (Node n : companies) {
        // take my concepts
        Collection<Node> myConcepts = g.getNeighbors(n);
        // for each of my concepts
        for (Node m : myConcepts) {
            // take its companies
            Collection<Node> itsCompanies = g.getNeighbors(m);
            // for each of the companies that use this concept
            for (Node nn : itsCompanies) {
                // if company is not myself
                if (!nn.equals(n)) {
                    // if at least one of these is not in the graph, go straight to add a link
                    if (!oneMode.containsVertex(nn) || !oneMode.containsVertex(n)) {
                        // add a new link
                        Edge edge = new Edge(1);
                        // set edge name
                        edge.setName(findEdgeLabel(n, nn));
                        edge.setFrom(nn);
                        edge.setTo(n);
                        // add a link between myself and this company
                        oneMode.addEdge(edge, n, nn, EdgeType.UNDIRECTED);
                    } else {
                        if (oneMode.isNeighbor(n, nn)) {
                            // retrieve edge based on the label
                            boolean incrementWeight = incrementWeight(oneMode.getEdges(), findEdgeLabel(n, nn));
                            if (!incrementWeight) {
                                throw new Exception("doesn't work");
                            }
                        } else {
                            // add a new link
                            Edge edge = new Edge(1);
                            // set edge name
                            edge.setName(findEdgeLabel(n, nn));
                            edge.setFrom(nn);
                            edge.setTo(n);
                            // add a link between myself and this company
                            oneMode.addEdge(edge, n, nn, EdgeType.UNDIRECTED);
                        }
                    }
                }
            }
        }
    }
    // now write result to file
    try (PrintWriter writer = new PrintWriter("icleantech-one-mode.csv", "UTF-8")) {
        // iterate
        for (Edge e : oneMode.getEdges()) {
            writer.println(e.getFrom().getName() + ";" + e.getTo().getName() + ";" + String.valueOf(e.getWeight()));
        }
    } catch (FileNotFoundException | UnsupportedEncodingException ex) {
        Logger.getLogger(BipartiteProjection.class.getName()).log(Level.SEVERE, null, ex);
    }
}

private static String findEdgeLabel(Node n, Node nn) {
    if (n.getId() < nn.getId()) {
        return String.valueOf(n.getId() + "-" + nn.getId());
    } else {
        return String.valueOf(nn.getId() + "-" + n.getId());
    }
}

private static boolean incrementWeight(Collection<Edge> edges, String findEdgeLabel) {
    for (Edge e : edges) {
        if (e.getName().equals(findEdgeLabel)) {
            // increase weight
            e.setWeight(e.getWeight() + 1);
            return true;
        }
    }
    return false;
}

代码中的瓶颈是当我想要更新链接权重时...没有它，代码真的很快...我不知道我错在哪里...非常欢迎任何帮助。

Answer 1

到目前为止，最有效的方法是使用超图而不是二分图。 (一个分区成为超图顶点，另一个成为超边，每个超边连接与原始图中相应顶点相连的顶点。)然后您只需向一个顶点询问其在超图中的邻居，就完成了。