Network Theory Jazz

Brief Introduction

Networks are flexible representations of systems governed by many interacting components. This flexibility has led to their application across a broad range of disciplines, modeling trade between countries [2, 3], cascading failures in power grids [5], the structure of the World Wide Web [1], neuronal connections in microscopic organisms like C. elegans [7, 8], and even human and animal social dynamics [4, 6].

The Language of Networks

In their most basic form, networks are a set of dots connected by lines. In the nomenclature of the field, the dots are often called nodes (or vertices) and the lines edges. Fundamentally, the language of networks is expressed through mathematics. But how exactly does one use a collection of dots and lines to represent scientific systems and solve problems? Formally, we denote \(G = \left(V,E\right)\)to represent the network \(G\) with a set of nodes \(V\) and a set of edges joining them \(E\), where \(n=\lvert V\rvert\)and \(m=\lvert E\rvert\) are the number of nodes and edges, respectively. There are a number of ways to represent \(G\) in a way that can be used to do calculations. One of the most flexible of such representations is known as the adjacency matrix. The most elementary form of the adjacency matrix has a very intuitive definition: it is an \(n \times n\)matrix, \(A\), such that for any pair of nodes \(u,v \in V\): $$ a_{uv} = \begin{cases} 1 & \text{if edge } \left\{u,v\right\}\in E, \\ 0 & \text{otherwise.} \tag{$1$} \end{cases} $$ Adjacency matrices of the form described in Equation (1) correspond to simple networks, where edges denote only that a pair of nodes interact in some manner. Should one need to be more specific about the nature of the interaction, there are a number of attributes that can be used to decorate edges, such as:

• Self-edges: edges that connect a node to itself.
• Multiedges: multiple edges connecting the same pair of nodes.
• Weighted edges: edges represented with a real value denoting the strength or weight of the interaction.
• Directed edges: edges representing the direction of the interaction; from one node to another.

Below we’ve illustrated what these networks might look like along with their adjacency matrices.

	$$\left(\begin{array}{cccccc}0& 0& 0& 0& 1& 0\\ 0& 0& 1& 1& 0& 0\\ 0& 1& 0& 1& 0& 1\\ 0& 1& 1& 0& 1& 0\\ 1& 0& 0& 1& 0& 1\\ 0& 0& 1& 0& 1& 0\end{array}\right)$$		$$\left(\begin{array}{cccccc}0& 0& 0& 0& 2& 0\\ 0& 2& 1& 1& 0& 0\\ 0& 1& 0& 1& 0& 1\\ 0& 1& 1& 0& 1& 0\\ 2& 0& 0& 1& 0& 1\\ 0& 0& 1& 0& 1& 0\end{array}\right)$$
	$$\left(\begin{array}{cccccc}0& 0& 0& 0& 1.5& 0\\ 0& 0& 1& 1& 0& 0\\ 0& 1& 0& 1& 0& 1\\ 0& 1& 1& 0& 1& 0\\ 1.5& 0& 0& 1& 0& 1\\ 0& 0& 1& 0& 1& 0\end{array}\right)$$		$$\left(\begin{array}{cccccc}0& 0& 0& 0& 1& 0\\ 0& 1& 0& 1& 0& 0\\ 0& 1& 0& 0& 0& 1\\ 0& 0& 1& 0& 0& 0\\ 1& 0& 0& 1& 0& 0\\ 0& 0& 0& 0& 1& 0\end{array}\right)$$

Basic Network Structure

The study of networks is based on empirically measured interactions and aims to gain insights into real-world phenomena. Once a network is measured, the goal is to use it to better understand the system being modeled. Visualizations like the ones shown above, can indeed be enlightening, allowing one to see structural patterns not that are not immediately obvious from raw data. However, their utility is somewhat limited to qualitative descriptions, and as the size of the network grows, the visualizations become quite involved, and many of the structural features become obscured. In contrast, mathematical analyses provide a way to quantitatively summarize specific and relevant features of interest.

Degree and Degree Distribution

At the smallest scale, we focus on individual nodes and their direct connections to others. The most fundamental property of a node at this level is its degree: the number of edges attached to the node. We can calculate the degree, \(d_u\), of any node \(u\) directly from a network’s adjacency matrix as follows $$ \begin{align} d_u = \sum\limits_v a_{uv}. \tag{$2$} \end{align} $$ The degree is the number of ends of edges incident on a node, so if we count the degrees of all the nodes we will have equivalently counted every edge in the network twice, more concretely $$ \begin{align} \sum\limits_{uv} a_{uv} = \sum\limits_u d_u = 2m, \tag{$3$} \end{align} $$ where \(m\) is the number of edges. Note that this definition of degree makes it clearer why a self-edge is represented by a 2 in the adjacency matrix. If we have a network with just one node connected to itself, it has two ends of edges attached and Equation (3) gives the expected result. Similar expressions for degree can also be defined for other types of networks. For weighted networks, we can use Equation (2) directly, only that \(d_u\) will represent a weighted degree. In the directed case, we have two types of edges: in-going edges and out-going edges, so it makes sense to measure an in-degree: \(d_u^{\text{in}} = \sum_v a_{vu}\) and an out-degree: \(d_u^{\text{out}} = \sum_v a_{uv}\) (note: for directed networks, the adjacency matrix is not symmetric by definition, so the order of the indices matters).

Once we know the degrees of all the nodes, we can study an illuminating global property of the network: the degree distribution. For a network of \(n\) nodes, let \(n_d\) denote the number of nodes with degree \(d\). The degree distribution is the fraction of nodes, \(p_d = n_d/n\), with degree \(d\). This distribution provides insight into the central tendency and variability of the connections in the network, shedding light on the large-scale organization of the nodes. For example, the average degree can be calculated as follows: $$ \begin{align} \langle d \rangle = \sum\limits_{d’} d’ p_{d’} = \frac{2m}{n} \end{align} $$

References

1. A. Broder, R. Kumar, F. Maghoul, P. Raghavan, S. Rajagopalan, R. Stata, A. Tomkins, and J. Wiener, Graph structure in the web. Computer Networks 33, 309–320 (2000)

2. F. Emmert-Streib, S. Tripathi, O. P.Yli-Harja, and M. Dehmer, Understanding the world economy in terms of networks: A survey of data-based network science approaches on economic networks. Frontiers Appl. Math. Stat. 4, 37 (2018)

3. G. Fagiolo, J. Reyes, and S. Schiavo, The evolution of the world trade web: A weighted-network analysis. Journal of Evolutionary Economics 20, 479–514 (2010)

4. M. Girvan and M. E. J. Newman, Community structure in social and biological networks. Proc. Natl. Acad. Sci. USA 99, 7821-7826 (2002)

5. R. Kinney, P. Crucitti, R. Albert, and V. Latora, Modeling cascading failures in the North American power grid. Eur. Phys. J. B 46, 101–107 (2004)

6. D. Lusseau, K. Schneider, O. J. Boisseau, P. Haase, E. Slooten, and S. M. Dawson, The bottlenose dolphin community of Doubtful Sound features a large proportion of long-lasting associations. Behavioral Ecology and Sociobiology 54, 396-405 (2003)

7. D. J. Watts and S. H. Strogatz, Collective dynamics of ‘small-world’ networks. Nature 393, 440-442 (1998)

8. J. G. White, E. Southgate, J. N. Thompson, and S. Brenner, The structure of the nervous system of the nematode Caenorhabditis elegans. Phil. Trans. R. Soc. London 314, 1-340 (1986)