how to make a projection of a bipartite graph with JUNG

Question

I have created a bipartite graph in JUNG, and I would like to have the one-mode projection for one of the sets of nodes. In the projection, two nodes of the same set will be linked if they have in common a node belonging to the other set. Is there a function in JUNG that already does it? The code I have so far (very slow for a bipartite network of 1600 nodes where only 400 belong to the set I want to project) is:

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;
}

the bottleneck in the code is when I want to update link weights... without it, the code is really fast... I have no idea where I am wrong... any help more than welcome.

Answer 1

The most efficient way to do this, by far, is to use a Hypergraph instead of a bipartite graph. (One partition becomes the hypergraph vertices, the other becomes the hyperedges, each hyperedge connects the vertices that were connected to the corresponding vertex in the original graph.) Then you can just ask a vertex for its neighbors in the hypergraph, and you're done.