Complex Network Theory

Question 1

Discuss the strengths and limitations of applying network theory for
quantifying the reliability of infrastructures and assess the vulnerability
to large-area breakdowns

Answer 1

Network Theory can serve as a analytically inexpensive way to model failure behavior of networks and their vulnerability on a large scale.

It is limited when it comes to real world physics, but can serve as a first anaylsis to identify critical points.

Question 2

What is the definition of a complex graph? What are the different types
of analyses that can be conducted on complex network systems?

Answer 2

A complex Graph consists of Notes and edges with a moderate number of interconnections. Both highly connected and not connected graphs are not complex.

We can do topology and structure analysis and assess the vulnerability of the network.

Question 3

How is the connectivity pattern of a network represented in
mathematical terms? Given a network structure, write the adjacency
matrix Aij.

Answer 3

The connectivity pattern of a network is completely described in the adjacency matrix. It has dimension nxn where each element can take the state zero or one.

A one means that the row element is connected to the column element.

For undirectional graphs the adjacency matrix is symmetric on the main diagonal.

If A -> B then also B -> A etc.

Question 4

What is the definition of a degree of a node? Which information is
extracted from the degree distribution of a network? What does it tell
about the overall connectivity of the network?

Answer 4

The degree of a note discribes to how many other nodes a node is connected (first neighbour)
To calculate this we simply sum up all elements in the corresponding row.

Question 5

What are the different connectivity properties of Poisson, Exponential
and Power-law networks? Discuss the degree distribution of real-world
networks. Focus on both technical and non-technical networks.

Answer 5

Poisson have a sharp mean for the degree distribution that falls off sharply to both sides.
In power law networks a new node prefers to attach to the nodes with the most connections. We have few nodes with many connections, this number increasis logarithmically with falling degree.
In Expenential networks the probability of a node to attaching to any node is always the same. We have many moderately connected nodes and few very connected nodes. With the number dropping off sharply.

Question 6

Discuss the tolerance of exponential and scale-free networks against
random failures and targeted attacks. How does the global connectivity
varies with respect to random failures and targeted attacks of increasing
magnitude?

Answer 6

Exponental Networks are robust to both random failure and malicious attacks.
The connecticity does not vary much after such an attack.

Scale Free Networks are very robust to random failure but sensitive to targeted attacks, when these attacks are targeted at very interconnected nodes. The connectivity may decrease significantly after a targeted attack.

Question 7

What is the underlying assumption in using the shortest path for
characterizing the service of a network system? How do you
compute the shortest path matrix dij of a given network?

Answer 7

The underlying assumption is that a piece of of information always takes the shortest (or the most reliable path).
For the shortest path can be computed by trying out all paths or much more efficiently with a shortest path algorithm such as dijkstra.

Question 8

Name a global connectivity indicator that can be directly
computed from the shortest path matrix dij. Which properties of
the connectivity are measured by this indicator?

Answer 8

The local efficiency is simply the reciprocal of the shortest path

The characteristic path length is a global indicator of path size

Question 9

For any given network, compute the characteristic path length L
from the shortest path matrix dij. Which properties of the
connectivity are measured by the characteristic path length L?

Answer 9

The charactaristic path length is the average of all shortest distances.
It is the mean distance a for example piece of information or a passenger on a subway network has to travel between any points

Question 10

Name an indicator for local connectivity of a node that can be
directly computed from the adjacency matrix Aij. Which properties
of the connectivity are measured by this indicator?

Answer 10

We can calculate the topological centrality of a given node directly from the adjecency matrix. The topological centrality caputures the number of nearest neighbours.

Question 11

For a network, compute the clustering coefficient Ci of any node.
Which properties are measured by the clustering coefficient Ci
and by the average clustering coefficient C?

Answer 11

The clustering coefficient captures the interconnectivity of the nearest neighbors (e.g. how interconnected are your friends)
1. For this we calculate Cmax as the maximum number of interconnections between nearest neighours k through k over 2 permutations.
2. Next divide the actual interconnections by the maximum number of interconnections to get Ci.

For the average clustering coefficient C we simply sum up all the Coefficients and then divide by the number of nodes.

Question 12

What is a weighted network? What additional information do weights
add to connectivity? How are weights included in the indicators of
connectivity of networks?

Answer 12

In a weighted network, the connections between nodes can have different lengths or penalities. This is included into the shortest path analysis, but has no influence on the topology.

Question 13

Describe some physical weight that can be useful in different systems
and applications. How do you expect that the results of the unweighted
analysis are changed if weights are included?

Answer 13

Travel time can be useful for subway network. As shortest paths taken by passengers usually do not depend on stops but on travel time.

For energy grid the electrical load of a connection can be interesting. Electricity usally goes the path of least resistance. The most loaded ways are hence the “shortest” of least resistance from A to B

Question 14

How do you compute the efficiency matrix εij of a given network? Which
indication about the path from node i to node j does the matrix element
εij provide?

Answer 14

The efficiency matrix can be calculated by simply taking the reciprocal of the the individual items in the shortest distance matrix dij.
The shorter the travelled distances, the more “efficient” a network is overall.

Question 15

Name a global connectivity indicator that can be directly computed from
the efficiency matrix εij. Which properties of the connectivity are
measured by this indicator?

Answer 15

The global effiency can be calculated from the effifiency matrix εij.
We sum up all elements and divide by (N-1)*N for the number of elements (excluding the main diagonal of the matrix)

Question 16

For any given network G, compute the global efficiency Eglob(G) from the
efficiency matrix εij. Which properties of the connectivity are measured
by the global efficiency Eglob(G)? Can the indicator Eglob(G) be applied
also in situations when the characteristic path length L is not defined?

Answer 16

Do on paper.
The global efficiency gives hint towards the length of the shortest path interconnections. When the characteristic path length is not defined, that usually means that parts of the network are disconnected. In this case we can calculate the efficiency of the subgraphs instead and calculate an average for the network.

Question 17

Name a local connectivity indicator that can be directly computed from
the efficiency matrix εij. Which properties of the connectivity are
measured by this indicator?

Answer 17

We can calculate the closeness centrality by taking the reciprocal of all the elements.

Alternatively the information centrality Ci can be calculated directly. For this we need the efficiency matrix with a node, and then another efficiency matrix, where a node has been deactivated.

The received measure shows, how well a system can circumpass the failed node.
If the network experiences a significant loss in relative efficiency, the node is important.

Question 18

For a network, compute the local efficiency E (Gi) of any node from the
efficiency matrix εij. Which properties are measured by the local
efficiency E (Gi) and by the average local efficiency Eloc(G)?

Answer 18

The local efficiency measures the efficiency of a single node.

The average local efficiency measures the average efficiency in a subgraph.

Question 19

Given any network, detail the steps of the procedure to quantify the
vulnerability of the network to the removal of its links and nodes. Which
indicators would you use to quantify this vulnerability?

Answer 19

To quantify vulnerability I would calculate the vulnerability through the efficiency matrices when removing single nodes.

For further analysis I can also compare the characteristic path length and the network diameter.

Question 20

What information is provided by the measures of topological centrality of
network nodes. Name one of the centrality measure, discuss what it
highlights and how you can compute it.

Answer 20

The measures of centrality describe the local importance of nodes based on different measures.

Question 21

For any of the four measures of topological centrality of network nodes,
discuss what it quantifies and based on this discussion propose a
formula to quantify it.

Answer 21

The Topological centrality describes how many first neighbours a node as as a fraction of total node.

Question 22

What are the elements of the static analysis of network systems.
Discuss them.

Answer 22

The elements of static analyis of networks are:
1) Topological analysis where we can describe the networks interconnections, shape and distribtution of degrees
2) Weighted analysis
where we assess efficiency and find measures to describe the network in units. E.g. how much range does our fire truck need to serve the whole network of houses?

Question 23

What is the Floyd-Warshall Algorithm?

Answer 23

It compares all possible paths in a graphs and determines the shortest paths from i to j.

Question 24

What is the “small-world property”?

Answer 24

Exponential networks have high clustering (local connectivity) while at the same time having few random connections to other clusters creating good global connectivity.

Question 25

How are scale-free networks built?

Answer 25

From growth processes with preferential attachment to nodes that are already well connected.

Question 26

How can we combine reliability and an electric flow weight?

Answer 26

We can simply multiply the electric weight and the reliability weight. In the exponent of the E function this will become an addition.

Question 27

Name the 4 measures of information centrality and how to calculate them.

Answer 27

1) Topological centrality
Cd = ki / (N-1)
2) Closeness centrality
Ci = (N-1) / dij
3) Betweenness centrality
1/(N-1)(N-2) Sum njk(i) / njk
4) Information centrality
E[G] - E[G] / E[G]