Barabási: Ch. 5 — Barabási-Albert Model

Consider a network of N = 1000 nodes constructed using the Barabási–Albert (BA) model with parameter m = 3. We know that $\langle k \rangle = 2m = 6$ and $P(k) \sim k^{-3}$.

Now compare this network with an Erdős–Rényi network of the same size and same average degree, where the degree distribution is concentrated around $\langle k \rangle$.

Which alternative best describe the difference between these two types of networks?

a) In a BA network, the probability of finding nodes with degree much larger than 6 is significantly higher than in an Erdős–Rényi network.

b) In a BA network, all nodes tend to have degrees close to 6 just like in an Erdős–Rényi network.

c) In a BA network, the probability of high-degree nodes decays exponentially, while in Erdős–Rényi it follows a power law.

d) In both networks, the probability of hubs is practically the same.

e) None of the above


Original idea by: Gabriel Sato

Barabási: Ch. 4 — Scale Free Networks

 In scale-free networks, the maximum degree grows with the size of the network as a power of the total number of nodes.

Suppose you have a scale-free network with $\gamma = 2.5$ and a total of $N = 10^6$ nodes. Which of the following best approximates the maximum degree in the network?

a) $N^{0.5} \approx 10^3$

b) $N^{1/3} \approx 10^2$

c) $N^{2/3} \approx 10^4$

d) $N^{1.5} \approx 10^9$

e) None of the above

Original idea by: Gabriel Sato

Barabási: Ch. 3 — Random Networks

$G_1(\mathrm{N,}{p}_1)$ and $G_2(\mathrm{N,}{p}_2)$ are two random networks with the same number of nodes $\mathrm{N,\; but\; different\; link\; probabilities\; with }$$p_1>p_2$. 

Which of the following statements is correct?

a) $G_1$will have a lower clustering coefficient than $G_2$.

b) $G_2$ will have a larger average degree than $G_1$.

c) $G_1$is more likely to contain a giant component than $G_2$.

d) Both $G_1$and $G_2$must have the same degree distribution, since they share the same $\mathrm{number\; of\; nodes\; N.}$

e) None of the above

Original idea by: Gabriel Sato

Barabási: Ch. 2 — Graph Theory

 Consider the statements about the following network:

I. The graph is connected;

II. The graph will have 2 components if edge DG is removed;

III. Edge AD is a bridge;

IV. When applying the Breadth-First Search (BFS) algorithm starting from node D, node C and node E will be the last to be visited.

Which alternative lists all correct statements?

a) I

b) I, II

c) I, III

d) I, III, IV

e) None of the above

Original idea by: Gabriel Sato