# 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.

### 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.

\(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.

### 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.