H1
A network G has 2 parts:
1. A set of N elements: Nodes
2. A set of L pairs of nodes: Links or Edges. The link (i, j) joins the nodes i and j.
A network can be directed (gericht) or undirected (ongericht):
- In directed networks, links are called direct links and the order in a link reflects the direction
- in undirected networks, links are bi-directional and the order does not matter.
A network can be weighted (gewogen) or unweighted (ongewogen): in weighted networks, links have an associated
weight. (e-mail communications, more emails between persons, heavier link)
Other network types:
- Bipartite network: two groups of nodes where links only connect to nodes from different groups.
- Multiplex network: a network with multiple types of links
Number of links in networks:
- The maximum number of links in an undirected network with N nodes is the number of distinct pairs of
n∗(n−1)
nodes: L =
2
- In a directed network, each pair of nodes should be counted twice, once for each direction, so
- L = n * (n-1)
- A bipartite network is complete if each node in one group is connected to all nodes in the other group. In this
case Lmax = N1 × N2
Density:
- The density of a network with N nodes and L links is: d = L/ Lmax
2L
- In an undirected network the density is: d = L/ Lmax =
N ( N−1)
L
- In an directed network the density isL d = L/ Lmax =
N ( N−1)
In a complete network, d = 1, since L = Lmax
in a sparse network, L < Lmax and therefore d < 1
If the number of links grows proportionally to the number of nodes (L ~ N), the network is sparse.
If the number of links grows faster to the number of nodes (L ~ N 2 ) , the network is dense.
Subnetworks
A subset of a network is called a subnetwork. A subnetwork is obtained by selecting a subset of the nodes and all the
links between those nodes.
A clique is a complete subnetwork: a subset of nodes all connected to each other. Any subset of a complete
network is a clique because all pairs of nodes are connected and therefore all pairs of nodes in any subnetwork are
connected.
Degree
The degree of a node is the number of links or neighbours. A node with no neighbours has a degree of 0 (k = 0) and is
called a singleton. The average degree of a network is denoted by K. The average degree of a network is defined as
❑
∑ Ki . K=
2 L dN (N −1)
= =d (N−1)
i
k= N N
N
Directed networks
In a graphical representation of a network, the direction of a link is indicated by an arrow. The presence of a link in a
directed network does not necessarily imply the presence of a link in the opposite direction. For the degree of a node
in a directed network, we have to think of incoming and outgoing links separately:
- The number of incoming links of node i is called the in-degree and denoted by k iin
- The number of outgoing links of node i is called the out-degree and denoted by k iout
Weighted networks
In a graphical representation of a network, the weight of a link is represented by the thickness of a line. A weight of
zero is equivalent to the absence of a link. A weighted network can be directed or undirected:
A network G has 2 parts:
1. A set of N elements: Nodes
2. A set of L pairs of nodes: Links or Edges. The link (i, j) joins the nodes i and j.
A network can be directed (gericht) or undirected (ongericht):
- In directed networks, links are called direct links and the order in a link reflects the direction
- in undirected networks, links are bi-directional and the order does not matter.
A network can be weighted (gewogen) or unweighted (ongewogen): in weighted networks, links have an associated
weight. (e-mail communications, more emails between persons, heavier link)
Other network types:
- Bipartite network: two groups of nodes where links only connect to nodes from different groups.
- Multiplex network: a network with multiple types of links
Number of links in networks:
- The maximum number of links in an undirected network with N nodes is the number of distinct pairs of
n∗(n−1)
nodes: L =
2
- In a directed network, each pair of nodes should be counted twice, once for each direction, so
- L = n * (n-1)
- A bipartite network is complete if each node in one group is connected to all nodes in the other group. In this
case Lmax = N1 × N2
Density:
- The density of a network with N nodes and L links is: d = L/ Lmax
2L
- In an undirected network the density is: d = L/ Lmax =
N ( N−1)
L
- In an directed network the density isL d = L/ Lmax =
N ( N−1)
In a complete network, d = 1, since L = Lmax
in a sparse network, L < Lmax and therefore d < 1
If the number of links grows proportionally to the number of nodes (L ~ N), the network is sparse.
If the number of links grows faster to the number of nodes (L ~ N 2 ) , the network is dense.
Subnetworks
A subset of a network is called a subnetwork. A subnetwork is obtained by selecting a subset of the nodes and all the
links between those nodes.
A clique is a complete subnetwork: a subset of nodes all connected to each other. Any subset of a complete
network is a clique because all pairs of nodes are connected and therefore all pairs of nodes in any subnetwork are
connected.
Degree
The degree of a node is the number of links or neighbours. A node with no neighbours has a degree of 0 (k = 0) and is
called a singleton. The average degree of a network is denoted by K. The average degree of a network is defined as
❑
∑ Ki . K=
2 L dN (N −1)
= =d (N−1)
i
k= N N
N
Directed networks
In a graphical representation of a network, the direction of a link is indicated by an arrow. The presence of a link in a
directed network does not necessarily imply the presence of a link in the opposite direction. For the degree of a node
in a directed network, we have to think of incoming and outgoing links separately:
- The number of incoming links of node i is called the in-degree and denoted by k iin
- The number of outgoing links of node i is called the out-degree and denoted by k iout
Weighted networks
In a graphical representation of a network, the weight of a link is represented by the thickness of a line. A weight of
zero is equivalent to the absence of a link. A weighted network can be directed or undirected:
