Basic network characteristics

Question 1

Node properties

What is the degree of a node? What is the interpretation of the average degree?

Answer 1

The number of connections for each node. The average degree is a sort of global density.

Undirected networks:

• one number for each node
• adjacency matrix: k(n) = ∑(j) A(jn) = ∑(j) A(nj)
• average degree: ⟨k⟩ ≡ (1/N) ∑(i=1)^N k(i) = 2L/N

Directed networks:

• diff. variables for the incoming and outgoing links
• adjacency matrix: k(in)(n) = ∑(j) A(jn), k(out)(n) = k(n) = ∑(j) A(nj)
• average degree: ⟨k(in)⟩ = ⟨k(out)⟩ ≡ (1/N) ∑(i=1)^N k(in/out)(i) = L/N

Weighted networks:

• node strength also denoted

Question 2

Node properties

How can we quantify local transitivity?

Answer 2

Using the clustering coefficient C(i), that measures local density. It is the probability that a pair of neighbors are linked to each other. Mathematically: # of connections between neighbours/max. # of connections between neighbours.

• undirected: C(i) = 2e(i)/[k(i)(k(i) - 1)]
• directed: C(i) = e(i)/[k(i)(k(i) - 1)]
• if k(i) < 2, C(i) = 0 by definition
• average clustering coefficient: ⟨C⟩ ≡ (1/N) ∑(i=1)^N C(i) = ⟨k⟩/N
• most real networks are highly clustered (universal property of real networks)

e(i) is the # of neighbours.

1. E.g.: there are a lot of triangles in the network of aqcuintances.
2. There are twice as many links possible between neighbours of a node in directed networks.

Question 3

Node properties

Why is the clustering coefficient so much lower in the random networks?

Answer 3

For a real network: they’re globally sparse but locally dense due to being highly clustered. If a network is sparse AND random, it’s gonna be locally sparse as well.

Question 4

Distance and paths

What’s a path in a network? What are some special cases?

Answer 4

A sequence of nodes in which each node is adjacent to the next one.

• may self intersect
• in directed networks it must follow the direction of the links

Special/exotic paths:

• cycle: same start and end node
• self-avoiding path: does not intersect itself
• Eulerian path: traverses each link exactly once
• Hamiltonian path: visits each node exactly once

Question 5

Distance and paths

How to define the distance between nodes? What are its properties? Average distance?

Answer 5

In other words: shortest path length. It is the minimum number of steps it takes to reach j from i following the links.

• ℓ(ii) = 0
• undirected networks: ℓ(ij) = ℓ(ji)
• if we cannot reach j from i: ℓ(ij) = ∞
• weighted networks: minimum weight path

Average distance:

• for a given node: ⟨ℓ(i)⟩ = 1/(N − 1) ∑(j) ℓ(ij)
• for the entire network: ⟨ℓ⟩ = 2/[N(N − 1)] ∑(i < j) ℓ(ij)

Question 6

Distance and paths

What are some algorithms that calculate the shortest path length?

Answer 6

1. Breadth first research: exploring all unvisited neighbours of the first neighbours of the previous node, until there aren’t any left
2. Depth first research
3. Dijkstra’s algorithm: adding the link weights and overwriting if smaller than the previously recorded

Question 7

Distance and paths

What is the diameter of a network?

Answer 7

The diameter of a network is given by the maximum distance between any pair of nodes: D = max(ij) ℓ(ij).

Usually the average shortest path length is more descriptive though.

Question 8

Distance and paths

What is the small world property?

Answer 8

A network has this property if ⟨ℓ⟩ ∼ ln N at most.

• we assume that N is large and ⟨k⟩ is smol: ⟨k⟩^⟨ℓ⟩ ≃ N if we count each “ring” of neighbours from a source node, so ⟨ℓ⟩ ≃ lnN/ln⟨k⟩
• real networks have the small world property (universal property of real networks)

The logarithm is the slowest increasing function.

Question 9

Distance and paths

What are the consequences of the small world property?

Answer 9

In networks, the # of nodes grows exponentially as n~⟨k⟩^l.

• covering the whole system takes only a couple of neighbourhoods
• everything is only a few steps away from each other

Question 10

Components

What are components? When is a component large?

Answer 10

A component in an undirected network corresponds to a maximal set of nodes (subgraph) in which a path exists between any pair of nodes.

A network (graph) with system size N → ∞ contains a giant component if the relative size of this component remains finite, (larger than zero): lim(N → ∞) S1/N > 0.

This is for undirected networks.

Question 11

Components

How to generalize the concept of components for the directed case?

Answer 11

Strongly connected component:

A strongly connected component is a maximal set of nodes in which a directed path exists between any pair of nodes.

Weakly connected component:

A weakly connected component is a maximal set of nodes in which an undirected path exists between any pair of nodes.