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 [latex]A[/latex] of a network is the matrix which contains non-zero element [latex]A_{ij}[/latex] if there exists an edge between node [latex]i[/latex] and [latex]j[/latex]. The resulting graph is undirected if the adjacency matrix [latex]A[/latex] is symmetric [latex]A_{ij} = A_{ji}[/latex] 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 [latex]AA^T[/latex] and [latex]A^TA[/latex] 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 [latex]i[/latex] its importance can be defined as a vector [latex]x_i[/latex] which can be computed as [latex]x_i \sum_k A_{ik}x_k[/latex].
• Closeness: A geodesic path connects two vertices with the lowest amount of edges. The length of a path between [latex]i[/latex] and [latex]j[/latex] measured in edges is denoted [latex]d_{ij}[/latex]. Closeness then can be expressed as the harmonic mean between [latex]i[/latex] and all other nodes [latex]C_i = \frac{1}{n-1}\sum_{j(\neq i)}\frac{1}{d_{ij}}[/latex].
• Betweenness: The number of geodesic paths between [latex]s[/latex] and [latex]t[/latex] is denoted as [latex]\sigma{st}[/latex]. The number of geodesic paths through a node [latex]i[/latex] is denoted as [latex]\sigma_{st}(v_i)[/latex]. Then betweenness is defined as [latex]C(v_i) = \sum_{s,t} = \frac{\sigma_{st}(v_i)}{\sigma_{st}}[/latex]

[latex] <k^2> = \sum_i P(k=i ) i^2= \sum_{i=0}^\infty i – \gamma i^2 [/latex]  [latex]<k> = \sum_i P(k=i ) i  = \sum_{i=0}^\infty i – \gamma i[/latex]