ETH

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 of a network is the matrix which contains non-zero element if there exists an edge between node and . The resulting graph is undirected if the adjacency matrix is symmetric 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 and 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 its importance can be defined as a vector which can be computed as .
• Closeness: A geodesic path connects two vertices with the lowest amount of edges. The length of a path between and measured in edges is denoted . Closeness then can be expressed as the harmonic mean between and all other nodes .
• Betweenness: The number of geodesic paths between and is denoted as . The number of geodesic paths through a node is denoted as . Then betweenness is defined as   Standard