Prof. Götz Pfeiffer

School of Mathematics, Statistics and Applied Mathematics

NUI Galway

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$.

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)
```

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)
```

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)
```