CGSS: Complex Networks

Behind complex networks, there are networks that describe the interaction between components.

Basics

A network is a set of nodes interconnected by a set of links. The adjacency matrix $A$ of a network is the matrix which contains non-zero element $A_{ij}$ if there exists an edge between node $i$ and $j$ . The resulting graph is undirected if the adjacency matrix $A$ is symmetric $A_{ij} = A_{ji}$ or directed otherwise.

A cycle exists in a graph if there exists an edge in the graph that can be removed without dividing it into two. A graph without cycles is considered a tree.

A bipartite graph connects two different kinds of nodes. The bipartite graph can be projected onto either type of node by matrix multiplication $AA^T$ and $A^TA$ respectively.

Centrality Measures

To assess a network the centrality of each nodes needs to be analysed. Several options are available:

Degree: The number of incoming edges is easy to measure, but does not centrality over a larger neighbourhood of nodes.
Eigenvector: For a vertex $i$ its importance can be defined as a vector $x_i$ which can be computed as $x_i \sum_k A_{ik}x_k$ .
Closeness: A geodesic path connects two vertices with the lowest amount of edges. The length of a path between $i$ and $j$ measured in edges is denoted $d_{ij}$ . Closeness then can be expressed as the harmonic mean between $i$ and all other nodes $C_i = \frac{1}{n-1}\sum_{j(\neq i)}\frac{1}{d_{ij}}$ .
Betweenness: The number of geodesic paths between $s$ and $t$ is denoted as $\sigma{st}$ . The number of geodesic paths through a node $i$ is denoted as $\sigma_{st}(v_i)$ . Then betweenness is defined as $C(v_i) = \sum_{s,t} = \frac{\sigma_{st}(v_i)}{\sigma_{st}}$