Network Science 101 Part 1 (Graph Theory)

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

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

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.

Degree of a node:

Click on the button to add nodes. And drag to connect them.