Logo

Network basics 1

A network is a graph \(G\) consisting of a set of nodes (or vertices) \(V\) and a set of links (or ties or edges) \(L\).

\[G=\{V,L\}\]

Nodes (vertices) and links (edges)

A fundamental property of a network is its total number of nodes \(N\) along with the total number of links \(K\) between nodes. As a network is formed, each node has a certain number of links that connects it to other nodes. This number is called the degree \(k\) of a node.

The degree is often interpreted in terms of the immediate risk of a node for catching whatever is flowing through the network (a virus, or information).

An important network index is the average of all degrees in a network, the mean degree \(\bar{k}\)

The total possible number of links in a network is \(K_{tot} = \frac{N(N - 1)}{2}\)

A striking feature of completely connected networks is the fact that the number of links is disproportionally growing when the number of nodes is increasing. A network with 5 nodes needs 10 links to be completely connected, a network with 10 nodes needs 45 links, and a network with 20 nodes already needs 190 links to be completely connected.

Nodes versus ties

Matrix notation

Mathematically, networks are denoted in the form of symmetric matrices with \(g \in \{0,1\}^{n*n}\), with \(g_{ij}=1\)indicating that \(i\) and \(j\) are connected, and \(g_{ij}=0\)indicating that \(i\) and \(j\) are unconnected.

Matrix notation

\(g_{ii}=0\)for all \(i\) means that no self-links are allowed.

Links can be directed or undirected. To be friend with someone usually is both-sided or symmetric. Friendship-links hence are undirected. To love someone can be one-sided or asymmetric. Love-links can be directed.

directed versus undirected

Matrix notation

Indegree

The indegree denotes the number of links directed towards a node - the in-coming links.

Outdegree

The outdegree denotes the number of links directed away from a node - the out-going links.

Degree distribution

Nodes are often regarded in respect to the probability of having a certain degree \(p(k)\)

This allows classifying networks in respect to a degree distribution of

\[p(k) \sim k^{-\gamma}\]

which is characteristic for many natural networks. Networks of this kind are said to have a power law degree distribution, implying that they have few nodes with high degree and numerous nodes with low degree. Such networks are called scale free networks.

Nodes with significantly more links than other nodes in the network are often called hubs.

Barabási A.L. / Albert R. (1999) Emergence of scaling in random networks. Science 286 (1999), 509-512.

Scalefree network