Prof. Götz Pfeiffer
School of Mathematics, Statistics and Applied Mathematics
In many situations, simple graphs are preferred over directed graphs. A simple method of turning a directed graph into a simple graph is given by ignoring the directions of the arrows, i.e., by reading each directed edge as an undirected edge. Some information will get lost on the way. Other methods of producing a simple graph from a directed one are based on composition of relations. We will see that the same method can be used to produce simple projections from bipartite graphs.
Suppose that $A$ is the (square) matrix adjacency matrix of a (undirected) network, corresponding to a relation $R$.
import networkx as nx import matplotlib.pyplot as plt %matplotlib inline
G = nx.Graph()
A = nx.adjacency_matrix(G)
AA = A * A
AA[AA>0] = 1
GG = nx.from_scipy_sparse_matrix(AA) nx.draw(GG, with_labels = True)
G = nx.DiGraph() G.add_nodes_from(range(9)) G.add_edges_from([(1,0), (2,0), (2,1), (3,1), (3,0), (4,2), (4,3), (5,1), (5,2), (5,3), (6,1), (6,4), (7,5), (8, 0), (8,3), (8,4)]) nx.draw(G, with_labels=True)
A = nx.adjacency_matrix(G) print(A.todense())
At = A.transpose() print(At.todense())
AAt = A * At print(AAt.todense())
GGt = nx.from_scipy_sparse_matrix(AAt) nx.draw(GGt, with_labels=True)
AtA = At * A print(AtA.todense())
GtG = nx.from_scipy_sparse_matrix(AtA) nx.draw(GtG, with_labels=True)
A (simple) graph $G = (X, E)$ is called bipartite, if the vertex set $X$ is a disjoint union of two sets $B$ (of black nodes) and $W$ (of white nodes) so that each edge in $E$ links a black vertex with a white vertex.
B = nx.Graph([(1,6), (2,6), (2,7), (2,8), (2,9), (3,9), (4,10), (5,9), (5,10)])
pos = [divmod(x, 5) for x in range(10)] pos
nx.draw(B, [""] + pos, with_labels=True)