E4.1 Erdös Renyí connectivity

In the $G(n, p)$ Erdos-Renyi-model, a graph with $n$ edges is constructed by con- necting nodes randomly. Each edge is included in the graph with probability $p$ independent from every other edge. Check the statement that almost every graph in $G(n, 2 ln(n)/n)$ is connected. Meaning that as n tends to infinity, the probability of a graph on n vertices with edge probability $2 ln(n)/n$ being connected tends to one. You can proceed as follows:

a) Up to a moderately high number of n (n = 100 should be enough, why not more nodes?) create a sufficiently high number of Erd ̋os-R ́enyi-graphs (around 1000 should be ok).

b) Investigate how many connected components each of these graphs has and average over all graphs for a given n.

c) Plot the average number of connected components over n. Does the behaviour of the number of connected components support the above statement? How long does it take to create an Erd ̋os-R ́enyi-Graph of size n?

E4.2 Scale free degre distribution

a) Create a Barabasi-Albert random graph with $|V|>500$ and plot the degree distribution using plt.hist or np.histogram.

b) Find out what kind of function fits the degree distribution best. (Hint: Try semi/doubly logarithmic plots)

E4.3 Average shortest path length scaling: small world

a) networkx provides these two functions to generate radom graphs:

• nx.erdos_renyi_graph(nnode, p)
• nx.barabasi_albert_graph(nnode, m)

Find out how the number of edges scales with $p$ and $m$ in these cases respectively.

b) Write a function that generates one Erdos-Renyi graph and one Barabasi-Albert graph with $N$ nodes and (approximately) $6N$ edges. Vary $N$ in about 10 stepsizes between 100 and 500. Check which random graph has smalles average shortest path length: Erdos-Renyi or Barabasi-Albert.

E4.4 Robustness of graphs against attacks

Using the same function that you wrote in E4.3 (b), check how many nodes when removed randomly from ER graph and BA graph with similar size and order to make the graph disconnected. Make a remark about which kind of graph is more robust against random attacks aginst nodes.