MO412 - Graph Algorithms Exercises

Regarding the Barabási-Albert (BA) and Linearized Chord Diagram (LCD) models, analyze the following statements: I. Both of these models can be used to generate scale-free networks II. In the BA model, if a network starts with only one isolated node at \(t=1\), a new node at \(t=2\) cannot connect to it because the sum of all degrees \(\sum k_j\) is zero, resulting in an undefined probability function III. By allowing self-loops, the LCD model provides a consistent initialization, allowing the network to grow from \(t=1\) without requiring a pre-existing graph IV. In the LCD model, as the network size \(N\) increases, the occurrence of new self-loops becomes increasingly rare, as the probability of a node connecting to itself is \(\frac{1}{2t-1}\) Which of the statements are TRUE A) I, II, III, IV B) I, II, III C) I, II, IV D) I, IV E) None of the above Original idea by: Fernando de Facio Rossetti

Regarding scale-free networks and degree distributions with exponent \(\gamma\), which of the following statements is FALSE ? A) If \(\gamma B) If \(2 C) If \(\gamma > 3\), the first and second moment converges D) If \(\gamma = 2\), the maximum degree \(k_{max}\) scales linearly with the network size E) None of the above Original idea by: Fernando de Facio Rossetti