MO412 - Graph Algorithms Exercises

Consider the following partitions over the same graph: Which alternative lists the partitions in ascending order of modularity ? A) PA, PB, PC, PD B) PD, PA, PB, PC C) PB, PA, PD, PC D) PA, PD, PB, PC E) None of the above Original idea by: Fernando de Facio Rossetti

Consider the following three networks: Network 1: A network where \(k_{nn}(k)\) is completely flat and independent of \(k\). The probability of a link between two nodes depends only on their degrees independently. Network 2: A network where every degree-\(k\) node connects exclusively to other degree-\(k\) nodes. Network 3: A network where \(k_{nn}(k)\) increases with \(k\). Nodes with high degree tend to connect to other high degree nodes, while nodes with low degree tend to connect to other low degree nodes. What are the following networks respectively? A) Neutral, Perfectly assortative, Assortative B) Neutral, Assortative, Disassortative C) Disassortative, Perfectly assortative, Assortative D) Disassortative, Neutral, Assortative E) None of the above Original idea by: Fernando de Facio Rossetti

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

Given two networks: Network A with \(N_{A}\)=50 nodes and \(P_{A}\) Network B with \(N_{B}\)=100 nodes and \(P_{B}\) Analyze these statements and find the values of X and Y I. For both networks to share the same average degree, \(P_{A}\) should be approximately (1 decimal) X times \(P_{B}\) II. Given that \(P_{A} = 0.5\) and \(P_{B} = 0.15\), you need to add Y nodes to A so they share the same average number of links A) X=2, Y=5 B) X=2, Y=6 C) X=3, Y=7 D) X=3, Y=4 E) None of the above Original idea by: Fernando de Facio Rossetti

A bipartite graph can also be interpreted as a \(2\)-colorable graph. That means every vertex is assigned one of two possible colors, such that no adjacent vertices share the same color. This can be generalized to any number of colors, so a graph G can be k-colorable if you assign a color \(c \in \{c1,c2,\dots,c_{k}\}\) to every vertex such that no adjacent vertices share the same color. Figures 1 and 2 show an example of a \(2\)-colorable and \(3\)-colorable graph, respectively. Figure 1 \(2\)-colorable graph Figure 2 \(3\)-colorable graph Which of the following statements are true I. Cycles with odd number of vertices cannot be \(2\)-colorable; II. A complete graph with \(N\) vertices is \(N\)-colorable at minimum; III. An empty graph is not \(2\)-colorable; IV. A graph is \( (k+1) \)-colorable if and only if it is \(k\)-colorable. A) I, II B) I, II, III C) I, II, III, IV D) III, IV E) None of the above Origi...