Create a projection from a bipartite graph

[yaslena]

Projections

Creating a projection is a method that allows one to convert a two-mode graph (for example a bipartite graph) into a one-mode graph. Several different solutions are possible. One can create a projection of the top nodes or the bottom nodes. One can also decide how to handle edges and their weights. Here is a sketch of a simple projection of the top nodes (a, b, c, d) from the bipartite graph consisting of top nodes a, b, c, d and bottom nodes 1, 2, 3:

Projections can be useful to examine the relationships of one of the node sets in a a two-mode network in more detail. There are more computational methods and algorithms available for one-mode graphs.

Projection steps

1. Specify top nodes and bottom nodes partition

• Inputs:

network_graph (type: bipartite network_graph, qualities: three tables 'edges'/'nodes1'/'nodes2')
bipartite nodes attribute

• Outputs:

partitioned nodeset (as list or dictionary?)

top_nodes = {n for n, d in B.nodes(data=True) if d['bipartite']==0}

bottom_nodes = set(B) - top_nodes

2. Create the projection

(load from graphml file, or sqlite-db-file, created from create_bipartite_graph module ...)

• Inputs:
  network_graph (type: bipartite network_graph, qualities: three tables 'edges'/'nodes1'/'nodes2')
  nodeset (string, choose bottom nodes or top nodes, from partition input in previous module)
  type of projection (string, options: projected_graph, weighted_projected_graph, collaboration_weighted_projected_graph, Overlap_weighted_projected graph, generic_weighted_projected_graph)
  multigraph option (string): !Graph type directed/undirected is inherited from the origin graph, but multigraph status is not and needs to be specified (default: multigraph=False).

P = bipartite.projected_graph(B, top_nodes, multigraph=True)

• Outputs:
  network_graph (type: network_graph, stored as sqlite-db-file, qualities: two tables 'edges'/'nodes')

Solution with SQL

The same result can be achieved by creating a new edge-list from the old edge-list.

original two-mode edgelist

source	target
a	1
a	3
b	2
c	1
c	2
c	3
d	3

projected one-mode edgelist

source	target
a	c
a	d
b	c
c	d

SELECT c.source, c1.source, c.target
FROM edges c
INNER JOIN edges c1
ON c.target = c1.target