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.
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.
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 is defined by a set of vertices and a set of Edges . Each edge 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 to is different from to . 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.
The adjacency matrix of a graph is an matrix (where is the number of nodes, or the size of the vertex Set ) whose elements are defined as follows
In other words, the elements in the matrix are non-zero only when there is a link from to . 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 when there is a link from to . We will be using this notation.
Click on the button to add nodes. And drag to connect them.