Original article was published on Deep Learning on Medium
TL;DR Representing Graphs using Adjacency Matrix, Adjacency List, Incidence Matrix and node degree matrix
In this post, we will understand what is a graph, and different ways to represent it. Specifically
- Adjacency Matrix
- Adjacency List
- (Edge) Incidence Matrix
- (Node) Diagonal Degree Matrix
A Graph is simply a collection of vertices/nodes and edges — where vertices typically represent entities and edges associate a relationship between the entities
Say for example — we have graph of Users (say Facebook/LinkedIN). Each user is a node in the graph. And all the people we are friends with (they will be nodes too!), will be represented using an edge to capture the friend-relationship.
Another example, lets take a graph of a road network — each node in the graph can represent a location (a pair of lat/lons) and edge between two locations describe the road or connectivity relationship.
As you might be already wondering now — hey these graphs have billions nodes and edges.. They are Huge!! Yes they are Big Graphs and by just by leveraging the network information we can extract meaningful relationships.
Lets take my LinkedIN profile (a node in the LinkedIN user Graph). I have connected with some profiles —they become my 1st degree connection. If there someone connected to “my connections” (but not to me) — they become my 2nd connection in the graph. This kind of reachability and propagation information in the graph is what populates your daily feeds, decide who will be an Influencer etc.
Ok — now that we can understand a node looks like me, and an edge looks like a friend-relationship etc. But how does a computer understand nodes and edges? This leads us to Graph Representation
There are 2 major ways to represent a graph
Each of the 3 cases above represents an notion of a Graph. For an adjacency matrix we see
- The ones in bold on the borders — shows the nodes in the graph.
- If a node is connected to another — represent it by 1 in its corresponding position. 0 otherwise
Voila, you got an adjacency matrix.. Where each row of the matrix represents all the relationships of that node. Say the first row has [0, 0, 1, 1,0] — which means node 1 is connected to 3 and 4.
One real world example from google maps — assume each node represents a road in road-network graph, then the value of the edge can represent details like real-time traffic, congestion, weather information etc. In this case edge values are not 1/0, may be a real value number which represents degree of relationship. This is called weighed Adjacency.
Note — Adjacency matrix is always of size Node x Node. In our case we have 5 nodes and hence if of size 25 elements. Now you may ask — hey, Facebook has over a billion users. I am connected to less than 1000 friends. Do I still need to save millions of zeros?
Great — just like you someone else asked the same intelligent question. The short answer Adjacency List
Same idea — different implementation.. For each node instead of saving its relationship with all the nodes, save the ones which matter..
I can rewrite the above Adjacency Matrix as follows
1 — [3,4]
2 — [4,5]
3 — [1,5]
4 — [1,2]
5 — [2,3]
So you save only the ones which is needed — but in practice for most ML tasks — we use adjacency matrix and/or try to save in sparse mode where we retain the location of the edge and the its value (say 1 or traffic information etc)
Edge Incidence Matrix
The idea of edge incidence matrix is quite similar to Adjacency — but with a few differences
Note — A graph is said to be directed if edges run in a particular traversal order. For example if our graph captures the relationship of wife, say Monica is wife of Chandler — does not mean Chandler is wife of Monica.. however spouse relationship works both ways. This kind of graphs are called directed graphs.
- Instead of nodes, this would be for edges
- If we used traditional 0/1 to represent the elements we can lose sense of direction (for directed graph) need to come up with a better way to define a->b relationship
In this example we have an edge incidence matrix which is of size Nodes x No of. Edges such that
- Each edge can take values 1 and -1
- 1 to -1 captures sense of direction — say E1 runs from A to B (not vice-versa)
We will visit this definition while computing Graph Laplacian.
Node Degree Matrix
This is quite straight forward. This just tells the number of nodes each node is connected to. Does not express individual edges (like previous methods) and hence is simply a diagonal matrix.
Catch — Node degree matrix can be different based on perception. Degree can mean both in-degree or out-degree. Based on application, can choose what suites your need.
In the above image — we can see the degree matrix is in-degree matrix — in general
- In-degree matrix is the sum of all elements row-wise.
- Out-degree matrix, sum along columns.
- For Symmetric matrix both in-degree matrix and out-degree matrix is the same.
There is a matrix on extreme right — is called the Laplacian. We will come to it soon in the next series of posts..
Representing Graphs, Adjacency Matrix, Directed Graphs, Adjacency lists, edge incident matrix and node degree matrix.
I know this is way to basic for a lot of DS and ML folks — the aim of this series to start from scratch. Have made a humble beginning today and hope we can learn, contribute and explore more together.
Stay with me — till we meet next time!