2021-057

Given the following statements,

I - A scale-free network is a network whose degree distribution follows a power law.
II - All real-world networks can be described as scale-free networks
III - Hubs are much more common in scale-free networks than in random networks
IV - The World Wide Web was the first real network that could be described as a random network

Select the alternative where statements are incorrect:

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

Original idea by: Taylla Milena Theodoro

2021-056

Based on the statements below, choose the correct alternative.

I. Nodes with widely different degrees may coexist in the same scale-free network.

II. To mathematically study the properties of scale-free networks, we should use the continuum formalism.

III. The main difference between a random and a scale-free network comes in the tail of the degree distribution, representing the high-k region of p_k.

IV. The maximum degree represents the expected size of the largest hub in a network.

1. Only II is correct.
2. I, III and IV are correct.
3. I and IV are correct.
4. III and IV are correct.
5. None of the above.

Original idea by: Maria Vitória R. Oliveira

2021-055

Given a scale-free network with the following properties:

• 1369 nodes
• the node with less connections has only 2 links
• its degree distribution follows a power law with exponent \( \gamma = 3 \)

Which value is the most probable to be the number of links in the node with most connections:

1. 111
2. 1368
3. 37
4. 684
5. None of the above.

Original idea by: Jader Martins

2021-054

About random networks and scale-free networks, check the incorrect answer.

1. Many networks of scientific and practical interest, from the WWW to the subcellular networks, are scale-free;
2. In a random network most nodes have comparable degrees and hence hubs are forbidden. Hubs are not only tolerated, but are expected in scale-free networks;
3. The main difference between a random and a scale-free network comes in the tail of the degree distribution, representing the high-\(k\) region of \( p_k \);
4. In a network with a power-law degree distribution, most nodes have only a few links. These numerous small nodes are held together by a few highly connected hubs;
5. None of the above.

Original idea by  Adson N Alves

2021-053

Consider a random graph G1 with 150 nodes and with a probability of 0.2 and a random graph G2 with 100 nodes and with a probability of 0.3. Which of these two distributions will have the highest average number of links and what is this value? 

1. G1 - 1485
2. G2 - 1485
3. G1 - 2235
4. G2 - 2235
5. None of the above

Original idea by: Victor Menuzzo

2021-052

Given the random network \( G(20, 0.2) \), what is the probability that this network does NOT contain 16 links?  Round your answer to 0.001%

1. 53,086%
2. 71,972%
3. 97,529%
4. 99,999%
5. None of the above

Original idea by: Isabela Marçal

2021-051

Random networks evolve in a dynamic process when \( \langle k \rangle \) grows from 0 to infinity. They start with isolated nodes, which are progressively linked in this random process. As a consequence, a giant component can emerge and change the network topology. The appearance of the giant component is only one of the transitions that occur as we change \( \langle k \rangle \). Four topologically distinct regimes are usually studied, namely: subcritical regime, critical point, supercritical regime and connected regime. Consider the following statements:

(I) In the subcritical regime, the network consists of numerous small, isolated components.

(II) At the critical point, most nodes are located in numerous small components. These numerous small components are mainly trees, while the giant component may contain loops.

(III) In the supercritical regime, numerous isolated components coexist with the giant component. These small components are trees, while the giant component contains only cycles. The supercritical regime lasts until the giant component absorbs all nodes.

(IV) In the connected regime, there are isolated nodes or unconnected components.

Which alternative lists the correct statements about the regimes?

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

Original idea by: Bruno Moritani

2021-050

Consider a random graph with 100 nodes and with a probability of 0.10. What is the expected average number of links?

1. 395
2. 420
3. 450
4. 585
5. None of the above

Original idea by: Thales Rogério

2021-049

Considering a random network with average degree equal to 2 and 200 nodes, what is the probability of a given node having 2 neighbors (round to two decimal places)?

1. 0.27
2. 0.10
3. 0.02
4. 0.50
5. None of the above

Original idea by: Leandro Stival

2021-048

Consider a random network such that \( N = 100 \) and \( \langle k \rangle = 0.5 \). What is the standard deviation of the network's degree distribution (round to two decimal places)?

1. 0.50
2. 0.58
3. 0.69
4. 0.71
5. None of the above

Original idea by: Helena Vieira

2021-047

For each of the following graphs determine whether it is planar, bipartite, both, or none.

(I)

(II)

(III)

(IV)

A. I-Bipartite, II-None, III-Planar, IV-Bipartite

B. I-Planar and Bipartite, II-None, III-Planar, IV-Bipartite

C. I-Planar and Bipartite, II-Planar and Bipartite, III-Bipartite, IV-None

D. I-Planar, II-Planar and Bipartite, III-None, IV-Planar

E. None of the above

 

 Original idea by: Taylla Milena Theodoro

2021-046

 

Consider the following graph:

 

The average degree and average clustering coefficient values for this graph are, respectively:

A. 16/7 and 4/7  

B. 16/7 and 3/7

C. 15/7 and 4/7

D. 11/3 and 1/3

E. None of the above

2021-045

Let \( \bar{G} \) denote the complement graph of an undirected, loppless graph \( G = (V, E) \), that is, \( \bar{G} \) has the same set of vertices \( V \), but the set of edges in \( \bar{G} \) consists of every pair of vertices from \( V \) that is not included in \( E \).

How can we express the number of edges in \( \bar{G} \) in terms of the sizes \( v = |V| \) and \( e = |E| \) ?

1. $$ \frac{2v^2 + 2v + e}{2} $$
2. $$ \frac{v^2 - v - 2e}{2} $$
3. $$ \frac{2v^2 - v + 2e}{2} $$
4. $$ \frac{v^2 + 2v - e}{2} $$
5. None of the above

Original idea by: Jader Martins

2021-044

Consider that you are a postman and have been asked to deliver some packages in different neighborhoods in two cities: Sorocaba and Campinas. For this, the logistics company provided a diagram that represents the possible routes. As you are an excellent student of Network Science, you remember that it is possible to build an Adjacency Matrix to help you in this choice. Which alternative represents these matrices, assuming the order of nodes in the rows and columns is 1,2,3,4,5,6 for Sorocaba and A,B,C,D,E,F for Campinas?

Sorocaba and Campinas Neighborhoods

1. \( \left( \begin{array}{cccccc} 0&0&1&0&0&0 \\ 0&0&1&1&0&0 \\ 1&1&0&0&1&1 \\ 0&1&0&0&0&0 \\ 0&0&1&0&0&0 \\ 0&0&1&0&0&0 \end{array} \right) \) , \( \left( \begin{array}{cccccc} 0&0&0&0&0&1 \\ 0&0&1&0&1&1 \\ 0&1&0&1&1&0 \\ 0&0&1&0&0&0 \\ 0&1&1&0&0&0 \\ 1&1&0&0&0&0 \end{array} \right) \)
2. \( \left( \begin{array}{ccccc} 0&0&1&0&0 \\ 0&0&1&1&0 \\ 1&1&0&0&1 \\ 0&1&0&0&0 \\ 0&0&1&0&0 \end{array} \right) \) , \( \left( \begin{array}{cccccc} 0&0&0&0&1 \\ 0&0&1&0&1 \\ 0&1&0&1&0 \\ 0&0&1&0&0 \\ 1&1&0&0&0 \end{array} \right) \)
3. \( \left( \begin{array}{ccccccc} 0&0&1&0&0&0 \\ 0&0&0&0&0&A \\ 0&0&2&1&0&0 \\ 0&0&B&0&1&1 \\ 1&1&0&0&5&1 \\ 0&1&0&A&1&0 \end{array} \right) \) , \( \left( \begin{array}{ccccccc} 0&3&0&0&0&0 \\ 0&0&1&0&0&0 \\ 0&0&4&0&0&0 \\ 0&C&D&0&0&0 \\ 0&0&1&0&6&0 \\ 1&1&0&0&E&0 \end{array} \right) \)
4. \( \left( \begin{array}{ccccccc} 1&0&1&0&0&0 \\ 0&1&0&0&0&1 \\ 1&0&1&1&0&0 \\ 0&1&1&0&1&1 \\ 1&1&0&0&1&1 \\ 0&1&0&1&1&0 \end{array} \right) \) , \( \left( \begin{array}{ccccccc} 0&1&0&0&0&0 \\ 0&0&1&1&0&0 \\ 0&0&1&0&0&0 \\ 0&1&1&0&0&0 \\ 1&0&1&0&0&0 \\ 1&1&0&1&0&0 \end{array} \right) \)
5. None of the above

Original idea by: Adson N Alves