### 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_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)