2023-206

 

Imagine a Cayley Tree, constructed starting from a central node, where each node has degree \(k\), except the nodes at distance P from the central node, that have degree one, as shown in the figure above. Considering that the number of nodes reachable in \( t \geq 1 \) steps from the central node is \( k(k-1)^{t-1} \), and the number of links is \( L = N-1 \), where \( N \) is the number of nodes, what is the probability of conexion between nodes for \(k=4\) and \(P=4\)?

1. 1/161
2. 2/161
3. 1/41
4. 2/41
5. None of above

Original idea by: Germán Darío Buitrago Salazar

2023-205

Suppose that we are trying to project a distributed system with random architecture. Every time a new computer \( i \) tries to ingress, for each existing machine \( j \) in the network, a connection \( (i,j) \) may be created with probability \( p \).

For this architecture, it is desired that any computer must be reachable from any node, however a few exceptions are tolerable. Also, \( p \) cannot be too big for cost reasons.

Which one of these options presents a reasonable choice for the value of \( p \)? Assume that\( N \) is the number of expected computers in the network, and it is large enough to apply the law of large numbers.

1. \( p = \frac{1}{N} \), because it is the critical point.
2. \( p = \frac{\ln N}{N} \), because it is the boundary between the supercritical and the connected regime.
3. \( p = \frac{\ln N}{\ln \langle k \rangle} \), because it is the boundary between the supercritical and the connected regime.
4. \( p = \frac{\langle k \rangle}{N} \), because it is the critical point.
5. None of the above

Original idea by: Christian Konishi

2023-204

Considering the Gilbert model , which statements from the following list are correct?

1. The expected number of links in a network generated with this model is \( \frac{pN(N-1)}{2} \)
2. If \( p > \frac{\ln N}{N} \) this model always generates a fully connected network with 100% certainty
3. This model produces a degree distribution that follows a Poisson distribution, which can be approximated by binomial distribution when \( N \) is much larger than \( k \)
4. A complete network can be generated from this model when \( p > 0 \), even if this is not likely

1. I and III
2. II, III and IV
3. I, II and IV
4. I and IV
5. None of above

Original idea by: Anderson Nogueira Cotrim