Question 12 - Dendrogram

Applying a divisive algorithm on the network below, we obtain the following dendrogram:

Network 

Dendrogram

Looking at the dendrogram, we establish two cuts creating community partitions. Which partition yields better communities and why? (Values are rounded to 2 decimal places).

1. A, because its modularity is equal to 0.36
2. B, because its modularity is equal to 0.45
3. A, because its modularity is equal to 0.45
4. B, because its modularity is equal to 0.36
5. None of the above.

  Original idea by: Pedro Henrique Di Francia Rosso

Question 11 - The failure!

You have a network of connected hardware components, where each edge means a route of communication between two hardware components (nodes). The network was constructed to represent the graph below:

The datasheet of the hardware components says that once configured for a given number of communication routes, if more than 40% of these communications become broken, the component will likely fail to maintain the other routes. 

Knowing that you have two new spare hardware components (that will not fail for a long time) and, that soon in the future, you expect a failure in any of the hardware components, which components would you exchange for a spare component to mitigate the impact of a failure? 

1. 3 and 11
2. 4 and 3
3. 11 and 4
4. 4 and 9
5. None of the above.

  Original idea by: Pedro Henrique Di Francia Rosso

Question 10 - Big Components

The Kosaraju-Sharir algorithm is an algorithm used to find strongly connected components in a graph.

Applying the algorithm on the graph given above, how many strongly connected components do we find, and what is the size of the biggest component, and the size of the smallest? (respectively)

1. 4, 8, 1
2. 5, 6, 2
3. 6, 5, 1
4. 4, 7, 2
5. None of the above.

  Original idea by: Pedro Henrique Di Francia Rosso

Question 9 - The crazy Network

Pedro was really interested in last algorithms class. So he started thinking and creating crazy networks. He proposed this: 

• First, he restricted the BA model, so when adding a new node with \(m\) links, each link has to go to a different node (probabilities have to be calculated at each new link, excluding the nodes already linked to the new one). 
• Now he established that \(m\) should follow the t-Fibonacci sequence. Where for a given \(t\) we have \(tFib(t) = t * Fib(t)\). (\(Fib(t)\) is the standard Fibonacci sequence)
• Finally, for each node he adds, he deletes \(2^t\) nodes. 

Of course, at this rate, soon he could not add anymore node to the network preserving the constraints he impose. 

Pedro started the network with 9876 nodes. Can you help him find the time \(t\) where he will not be able to follow the crazy network constraints?

1. \(t = 10\)
2. \(t = 11\)
3. \(t = 12\)
4. \(t = 13\)
5. None of the above.

  Original idea by: Pedro Henrique Di Francia Rosso

Question 8 - BA Model

On the Non-linear preferential attachment, our probability becomes \(Π(k) \sim k^\alpha\). For a starting network with 1 node, approximately how many nodes we have to add on the network for it to achieve \(k_{max} = 100\), considering the cases where \(\alpha\) is \(0.5\), \(1\) and \(1.5\) respectively?

1. \(22026\) nodes; \(10000\) nodes; \(100\) nodes respectively
2. \(1024\) nodes; \(1000\) nodes; \(100\) nodes respectively
3. \(22026\) nodes; \(10000\) nodes; \(200\) nodes respectively
4. \(1024\) nodes; \(1000\) nodes; \(200\) nodes respectively
5. None of the above.

  Original idea by: Pedro Henrique Di Francia Rosso

Question 7 - The Science Project

During a science project, Pedro created a system that is governed by the following equation:

$$f(x) = \frac{1}{32}x^{2}a\ -\frac{1}{2}xz +3$$

In this system, \(a\) and \(z\) are constants that are adjusted manually by him, while \(x\) is the primary variable he wants to change. During his experimental tests, he found that the system can be very unstable, only for a few values of \(x\) for different \(a\) and \(z\) the system becomes stable. Can you help him find an equation that given  \(a\) and \(z\) he can easily find the value of \(x\)?

1. \(x = \frac{16z}{2a}\)
2. \(x = \frac{16za}{2}\)
3. \(x = \frac{2az}{16}\)
4. \(x = \frac{16a}{2z}\)
5. None of the above.

  Original idea by: Pedro Henrique Di Francia Rosso

Question 6 - Scale-free Property

  With respect to the Scale-Free Property, given the following statements:

1. One of the key differences between scale-free networks and random networks is that hubs are forbidden in the random networks, but are expected in scale-free networks.
2. In the Anomalous Regime, all nodes are close and connect in the same central hub. Thus the degree of the biggest hub increases linearly with the network size (N), so the average path length depends on N.
3. Most real networks are present in the ultra-small world (Scale-free Regime) because their first and second moments are finite.
4. In the Random Regime, the probability \(P_k\) decays sufficiently fast to make the hubs smaller and less numerous, so the scale-free networks in this regime are more closer to the random networks, being hard to distinguish one from another.

  Which alternative contains all the correct statements?

1. I and IV are true.
2. II and III are true.
3. II and IV are true.
4. I and III are true.
5. None of the above.

  Original idea by: Pedro Henrique Di Francia Rosso