Network Science 101 (Graph Theory)

July 24, 2022

This Blog Post is about learning the basics of Network Science. Networks are all around us. From the electricity grid that supplies the power to your homes to the trasport system (Subway/Metro).

The tools that will be introduced in this blog post are basically tools that I learned during my Post Graduate degree. This also doubles as growth along the learning curve of HTML and javascript library vis.js for interactive graph visualisation. I will be posting an interesting interactive game next week hopefully which requires learning these We will start with introduction to Graph Theory.

What are Networks?

A network is a collection of many interconnected objects or things. A famous example being a social network like Facebook or twitter where each twitter account/profile would be an individual object often called as a node. And where if one account follow another, they are said to be connected by a link.

Other examples include: Biochecmical Networks/pathways, Ecological Networks such as Food webs, Neural Networks (Artifiial and Natural alike) and Social Systems such as Social Media and Societies.

Graphs

What are graphs? For many people graphs are confined to what they draw for mathematics examinations in schools. But in mathematical science, graphs have a very distinct definition. Graph is a mathematical structure defined by two components: Vertices (Nodes) and Edges (Links). Where edges denote some kind of connection between them.

A Graph $\mathcal{G}(V,E)$ is defined by a set of vertices $V = \{ v_1, v_2, v_3 , \cdots v_n \}$ and a set of Edges $E=\{e_1,e_2,e_3, \cdots ,c_m \}$ . Each edge $e$ is a ordered/unordered pair of vertices.

In the examples below, red circles denote two different graphs. The edge set for each graph is different even when the set of nodes are same. In the right example, the edge set consists of ordered pair of the vertices. For instance, the link from $1$ to $2$ is different from $2$ to $1$ . Whereas in the left example the edges are unordered.

The left graph is an example of an Undirected Graph. Whereas the one on the right is an example of a Directed Graph.

A real life example for a directed Graph would be this blog post for example. When you arrived at the link you had to click on a button or a hyper link. That is a directed edge with vertices being two different web pages on the world wide web.

⚠ Note

Almost all graphs in this page are interactive and nodes can be dragged along and you can zoom in and out as well

Properties of Graphs

Adjacency Matrix :

The adjacency matrix of a graph $\mathcal{G} (V,E)$ is an $N \times N$ matrix (where $N$ is the number of nodes, or the size of the vertex Set $V$ ) whose elements are defined as follows

\begin{aligned}A_{ij}&=1 \quad \text{if} (v_i,v_j) \in E \\ &= 0 \quad \text{otherwise} \end{aligned}

In other words, the $i-j$ elements in the matrix are non-zero only when there is a link from $i$ to $j$ . For undirected graph as the edge set is formed by unordered pairs, the Adjacency matrix is a symmetric matrix.

But for a directed graph, the symmetric is in general a asymmetric matrix. So, the convention of defining the adjacency matrix is often important. Some sources/textbooks consider the reverse notation, where $A_{ji}=1$ when there is a link from $i$ to $j$ . We will be using this notation.

Adjacency Matrix and The network

Using the above definition, following widget provides the adjacency matrix for an undirected graph. You can click on the canvas anywhere to add a new node. An edge can be made by clicking on the edit button on the top left corner.

Adjacency matrix for an indirected Graph

Matrix

Network

Degree of a node:

Degree of a node is defined as the number of links that are attached to a node. For an undirected graph, since there is no directionality in the links, we have only one measure (degree). Whereas for a directed graph, we can define In-Degree and Out-Degree for a node. The former being the total number of links that are coming into the node and the latter being the total number of links going away from the node.

This is a property of a node of the graph. i.e. each individual node of the graph can have different degree. For a graph, we can define a measure known as Average Degree, which is nothing but the sum of all individual degrees divided by the number of nodes.

In the widget below, you can edit the graph and see how the degree of the node changes. The node labels are individual degrees of nodes. And the average degree is displayed after the graph. If you hover the cursor on the node the node id will be shown.

Degree of node and Adjacency Matrix

Degree of a node for an undirected graph can also be calculated from the Adjacency matrix.

k_i=\sum_{j=1}^{N} A_{ij}

Where $k_i$ is the degree of $i^{th}$ node and there are $N$ nodes. Note that this is just the sum of $i^{th}$ row of the matrix.

The average degree is therefore,

k_{avg}= \sum_{i=1}^N \frac{k_i}{N}

For a directed graph, The In-Degree can be defined as the sum of the row elements while Out-Degree can be defined as the sum of all elements in the column.

\begin{aligned}k_i^{(in)} &= \sum_{j=1}^{N} A_{ij} \\ k_i^{(out)}&=\sum_{j=1}^{N} A_{ji}\end{aligned}

⚠ Note

Sum of the in-degrees or out-degrees of individual nodes gives us sum of all non-zero elements of the adjacency matrix. Which is the number of edges in the graph. i.e. if $L$ is the number of edges/links in the graph:

k_{avg}^{in/out}=L/N

For an undireccted graph, the things get a bit more complicated as we over count while taking the sum of the degrees which can be easily derived and left to the reader.

That is it from me for today. Hopefully next time we will be discussing a special kind of graph. Planar Graphs! And you will be able to play a famous game involving the concept of planarity of graph.