Introduction to Graph Networks: Adjacency Matrix
A network is a collection of nodes connected by edges. The most fundamental way to represent this type of structure mathematically is to consider an Adjacency Matrix.
Let’s consider a simple undirected network with n nodes. Each node in our network is someone in your family (parents, grandparents, cousins, distant relatives… Cousin Bob’s parrot, you name it!), and each edge represents a phone call ahead of a major family holiday. You are all meeting at grandma’s house to celebrate.
One can imagine that grandma will be on phone calls with many members of the family for extending invitations and managing logistics, and she might even talk to 2-year-old Lucy about a certain chocolate cake. Cousin Bob’s parrot may be joining some calls too, since it can speak fluent English.
Let’s name each node/person from 1 to n, so as to preserve their privacy (Facebook style, lol). The adjacency matrix A of the family network is defined as the n x n matrix:
We order people by age here to make things easy, so from 1 to 6 we have Grandma, Dad, Aunt Daisy, Cousin Bob, the parrot and Lucy.
As we can see, Grandma (row 1 and column 1) talked to everyone except herself. Little Lucy (row 6 and column 6) has only talked to Grandma. Dad (row 2 and column 2) and Aunt Daisy (row 3 and column 3) have talked to each other, which gives us two entries in the matrix. And the same for Cousin Bob and his Parrot.
Two important things to note about this particular adjacency matrix are: 1) the diagonal elements are all zero, since we assume no one is calling themselves on the phone, and 2) the matrix is symmetric, since each phone call occurs between two individuals.
If grandma used her landline to accidentally call her cellphone, then the first entry in the matrix would be 2 (not one!), because a self-edge needs to be recorded in the matrix from both ends.
Moreover, we could imagine that not all details of the family gathering were discussed within the same phone call. Let’s say Grandma called Cousin Bob twice and Aunt Daisy three times, and that Cousin Bob called Dad 7 times!
Our new adjacency matrix would look like this:
Interestingly, this is how we represent undirected weighted networks.
The weights in our example are how many phone calls connected each pair of people in the family.
I hope you liked this post. Please hit Like and subscribe to my Medium channel. I hope to bring a lot more about networks in the coming posts.
Let’s learn together! =)
