in Graph

Different ways of representing Graphs

Graph data can be represented in different formats for onward computation. The choice of the graph representation hugely relies on the density of the graph, space required, speed and weight of edges. The main ways a graph can be represented are as an adjacency matrix, incidence matrix, adjacency list and incidence list.

Adjacency Matrix: This is one of the most popular ways a graph is represented. One of the core aims of this matrix is to assess if the pairs of vertices in a given graph are adjacent or not. In an adjacency matrix, row and columns represent vertices. The row sum equals the degree of the vertex that the row represents. It is advisable to use the adjacency matrix for weighted edges.  You replace the standard ‘1’ with the respective weight.  It is easier to represent directed graphs with edge weights through an adjacency matrix. Adjacency matrix works best with dense graphs. As dense graphs usually have twice the size of the edges to the given nodes.

Dense graph = | E |- |V|²

Sparse Graph = | E |- |V|

The above formula highlights a 1:1 vertex to edge ratio for a sparse graph and 1:2 for the dense graph type.

Adjacency matrix takes up  |V|² space, regardless of the graph density. Matrix for a graph with 10,000 vertices will use up at least 100, 000 Bytes.

Similarly, you could think of the dense graph as twice the number of the order of the graph to its actual size. As in graph theory, the order of the graph is determined by the number of edges and the size as the number of vertices.

|V|= Order of the graph G  (Number of edges)

|E|= Size of the graph G    (Number of vertices)

Overall, the adjacency matrix is considered to be faster for dense graphs and simpler for weighted edges. On the downside, it uses more space. We will have a look at an adjacency matrix example in NetworkX, a Python library for networks. As expected, the Adjacency Matrix is a 2D array of size V x V where both V’s represent the number of vertices in a graph. For an unweighted graph, the 2D array of rows and columns will be adj[][]. Leading to adj[m][n] = 1.

This clearly expresses that there is an edge connecting vertex m to vertex n which automatically outputs 1. When the edges of graphs contain weights, the adj[m][n] = w, then we have an edge from vertex m to vertex n with weight w. In the case of an undirected graph (i.e. all present edges are bidirectional), the adjacency matrix is symmetric. 

In the example matrix below, the rows and columns both represent the vertices and an instance of 1 indicates if there is an edge connection between nodes.

Here is a quick code implementation of an adjacency matrix created via Numpy and converted into a network. It is a matrix utilising a standard 0 or 1 values (0: when there are no edges and 1:when edges are present between nodes). As a sparse matrix, there are equal numbers of rows and columns with labels 1 – 7.

import networkx as nx
import numpy as np
import matplotlib.pyplot as plt
import scipy as sp
import pandas as pd

%matplotlib inline

#Adjacent matrix
adj_matrix = np.matrix([[0,1,0,0,1,0,1],[1,0,1,0,1,0,1],[0,1,0,1,0,0,1],[0,0,1,0,1,1,1],[1,1,0,1,0,0,1],[0,0,0,1,0,0,1],[0,0,0,1,0,0,1]])
adj_sparse = sp.sparse.coo_matrix(adj_matrix, dtype=np.int8)
labels = range(1,8)
DF_adj = pd.DataFrame(adj_sparse.toarray(),index=labels,columns=labels)
print (DF_adj)

 1  2  3  4  5  6  7
1  0  1  0  0  1  0  1
2  1  0  1  0  1  0  1
3  0  1  0  1  0  0  1
4  0  0  1  0  1  1  1
5  1  1  0  1  0  0  1
6  0  0  0  1  0  0  1
7  0  0  0  1  0  0  1



The next step is converting the adjacency matrix into a graph via the NetworkX Python library. Firstly, the row and column labels are converted into vertices or nodes. This would generate a total of 7 nodes based on the corresponding row and column labels. Column label ‘i’ and row label ‘j’ are assigned as nodes and an add_edge command establishes a connection between nodes.

#Utilising Network graph
G = nx.Graph()
G.add_nodes_from(labels)

#Connecting the nodes
for i in range(DF_adj.shape[0]):
    col_label = DF_adj.columns[i]
    for j in range(DF_adj.shape[1]):
        row_label = DF_adj.index[j]
        node = DF_adj.iloc[i,j]
        if node == 1:
            G.add_edge(col_label,row_label)

#Draw graph
nx.draw(G,with_labels = True)

The graph is now drawn to represent the nodes and edges initialised in the previous section

Incidence Matrix: It is a matrix that highlights the relationship between two objects. In this instance, the objects are nodes and edges. The matrix has one row for each node and one column for the edges. An entry for the intersection of row (X) and column (Y) is 1 when there is a relationship. In the incidence matrix, loops count as twice.

Here is a simple representation of the weight in an incidence matrix. A weight of 23 is allocated to entries where there is an intersection.

import networkx as nx
from math import sqrt

T = nx.grid_2d_graph(3,3)
for m, n in T.edges():
    x1, y1 = m
    x2, y2 = n
    T[m][n]['weight']=sqrt((x2-x1)**2 + (y2-y1)**2 )*23

print(nx.incidence_matrix(T,weight='weight').todense())

[[23. 23.  0.  0.  0.  0.  0.  0.  0.  0.  0.  0.]
 [ 0. 23. 23. 23.  0.  0.  0.  0.  0.  0.  0.  0.]
 [ 0.  0.  0. 23. 23.  0.  0.  0.  0.  0.  0.  0.]
 [23.  0.  0.  0.  0. 23. 23.  0.  0.  0.  0.  0.]
 [ 0.  0. 23.  0.  0.  0. 23. 23. 23.  0.  0.  0.]
 [ 0.  0.  0.  0. 23.  0.  0.  0. 23. 23.  0.  0.]
 [ 0.  0.  0.  0.  0. 23.  0.  0.  0.  0. 23.  0.]
 [ 0.  0.  0.  0.  0.  0.  0. 23.  0.  0. 23. 23.]
 [ 0.  0.  0.  0.  0.  0.  0.  0.  0. 23.  0. 23.]]

Adjacency list: An adjacency list presents the neighbouring or connected edges to a given node. One of the benefits of adjacent lists is that it is faster and uses less space for sparse graphs. Unfortunately, it is slower for dense graphs.

These are some of the ways graphs can be represented.

Write a Comment

Comment