2021-025

Consider a scale-free network that has \( N = 10^7 \) nodes, each of them connected to at least one node, and with at least one leaf. If the degree exponent is \( \gamma = 2.5 \), what is the maximum expected degree of this network? Round the result to the nearest integer.

1. \( k_{max} = 75 \)
2. \( k_{max} = 630 \)
3. \( k_{max} = 3162 \)
4. \( k_{max} = 46415\)
5. None of the above.

Original idea by: Bruno Almêda

2021-024

 Choose the incorrect alternative about scale-free networks and their properties.

1. Scale-free networks have a large quantity of small degree nodes.
2. For large node degree \( k \), the power law lays below the Poisson curve.
3. Scale-free networks are networks whose degree distribution asymptotically follows a power law.
4. Many real networks such as the citation and email networks, are scale-free.
5. None of the above. 

Original idea by: Adolfo Aires Schneider

2021-023

Consider a Random Network with \( N = 100 \) nodes and probability \( p = 0.4 \) that two nodes are connected. The values of \( \langle L \rangle \) (expected number of links in this random network) and \( \langle k \rangle \) (average degree for this random network), are, respectively:

1. 1980 and 40
2. 2000 and 39.6
3. 2000 and 40
4. 1980 and 39.6
5. None of the above

Original idea by Angelica Oliveira

2021-022

Given a Random Network with \( N = 10000 \) nodes, and a probability \( p = 0.01 \) that a node pair is connected, what is the probability that a given node \( n \) will have exactly \( k = 100 \) links?

(Obs. Round off the result to 2 decimal places)

1. 0.01
2. 0.02
3. 0.04
4. 0.08
5. None of the above

Original idea by: José Nascimento

2021-021

In a graph, a "tree edge" is an edge that is present in the tree obtained after performing DFS on the graph. Suppose that \(k\) tree edges resulted from a depth-first traversal of an \(n\)-vertex, undirected graph. The number of the connected components in the graph can be calculated as:

1. \( k-1 \)
2. \( k \)
3. \( n-k \)
4. \( n-k+1 \)
5. None of the above

Original idea by: Soroor Salavati

2021-020

Consider the following graph:

Which alternative corresponds to a possible DFS order of node visits?

a. A, B, D, F, E, C, G 

b. A, B, C, D, E, F

c. A, C, D, B, E, F

d. G, C, A, B, C, D, F

e. None of the above

 

Original idea by: Wandersom Moura

2021-019

Which of the formulas below computes the average degree of an undirected network, where \( N \) is the number of nodes in the network,  \( k_i \) is the degree of node \( i \), \( N_k \) is the number of degree-\(k\) nodes, and \( A \) is the adjacency matrix:

1. $$ \sum_{j=1}^N A_{j,i} $$
2. $$ \dfrac{1}{2} \sum_{i=1}^N k_i $$
3. $$ \dfrac{1}{N} \sum_{i=1}^N k_i $$
4. $$ \dfrac{N_k}{N} $$
5. None of the above

Original idea by Mauricio Schiezaro