CS4423 - Networks

Prof. Götz Pfeiffer
School of Mathematics, Statistics and Applied Mathematics
NUI Galway

Lecture 4: New Networks from Old

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.

Product of Relations

Suppose that $A$ is the (square) matrix adjacency matrix of a (undirected) network, corresponding to a relation $R$.

In [ ]:
import networkx as nx
import matplotlib.pyplot as plt
%matplotlib inline
In [ ]:
G = nx.Graph()
In [ ]:
G.add_edges_from([(1,2),(2,3),(2,4), (3,4),(3,5)])
In [ ]:
nx.draw(G, with_labels=True)
In [ ]:
A = nx.adjacency_matrix(G)
In [ ]:
print(A.todense())
In [ ]:
AA = A * A
In [ ]:
print(AA.todense())
In [ ]:
AA[AA>0] = 1
In [ ]:
print(AA.todense())
In [ ]:
GG = nx.from_scipy_sparse_matrix(AA)
nx.draw(GG, with_labels = True)

Directed Graphs

In [ ]:
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)
In [ ]:
list(G.successors(2))
In [ ]:
G.nodes()
In [ ]:
A = nx.adjacency_matrix(G)
print(A.todense())
In [ ]:
At = A.transpose()
print(At.todense())
In [ ]:
AAt = A * At
print(AAt.todense())
In [ ]:
GGt = nx.from_scipy_sparse_matrix(AAt)
nx.draw(GGt, with_labels=True)
In [ ]:
AtA = At * A
print(AtA.todense())
In [ ]:
GtG = nx.from_scipy_sparse_matrix(AtA)
nx.draw(GtG, with_labels=True)

Bipartite Graphs

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.

In [ ]:
B = nx.Graph([(1,6), (2,6), (2,7), (2,8), (2,9), 
              (3,9), (4,10), (5,9), (5,10)])
In [ ]:
pos = [divmod(x, 5) for x in range(10)]
pos
In [ ]:
nx.draw(B, [""] + pos, with_labels=True)