2022-130

Consider the following statements about degree correlation in networks:

1. In neutral networks, nodes link to each other randomly, which in turn results in a lack of degree correlation for the linking pattern.
2. A perfectly assortative network is always a complete graph.
3. The correlation exponent can help determine the type of the network. When the correlation exponent is positive, we may say the network is assortative.
4. In assortative networks, nodes tend to link to nodes of similar degree. In other words, hubs tend to connect with hubs, and small-degree nodes tend to connect with small-degree nodes.
5. Degree correlations for directed networks are defined by two coefficients: \( r_{in,out} \) and \( r_{out,in} \).

Select the alternative that lists the correct statements:

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

Original idea by: Heitor Mattosinho

2022-129

Which of the alternatives is true, regarding assortative networks?

1. Hubs tend to connect to small-degree nodes.
2. The average degree of the neighbors of nodes with degree \( k \) (denoted by \( k_{nn}(k) \)) increases with \( k \).
3. Technological networks are usually assortative.
4. For large \( \langle k \rangle \), the giant component is bigger in assortative networks than in neutral or disassortative networks.
5. None of the above.

Original idea by: Diogo Souza.

2022-128

Consider the following oriented network:

Executing a BFS algorithm in this network, starting at node 5, and traversing the adjacent lists in increasing order, we have:

1. All nodes can be reached using this algorithm
2. The node with the highest distance from node 5 is node 6
3. Nodes  2 and 4 have the same distance from node 5
4. Node 8 is assigned as the parent of node 2
5. The highest distance from node 5 is 4 links

The only statements that are correct are:

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

Original idea by: Athyrson Machado Ribeiro

2022-127

 Analyze the following statements:

      I.  The Barabási–Albert model describes a process to generate scale-free networks, and tries to capture the idea that, in real networks, the number of nodes continually grows, thanks to the addition of new nodes;

     II.  Scale-free networks don't follow a power-law degree distribution, because there are almost no hubs in this type of network, which means the degree distribution can't follow an exponential curve (be proportional to an exponential term);

    III.  The number of links in a Barabási-Albert-generated network can decrease over time, since there is a significant chance the algorithm will remove links from hubs, to keep the network from having a linear degree distribution;

    IV.  The Barabási-Albert model uses a preferential attachment mechanism. The network grows by adding new nodes over time, and a new node links to existing nodes in the network with probability proportional to their degree.

Now, mark the correct alternative:

    A. I and IV are correct
    B. I and III are correct
    C. II and III are correct
    D. All statements are correct
    E. None of the above

Original idea by: Victória Pedrazzoli

2022-126

Consider the statements below about network flows, where s is the source and t the sink:

I) The maximal flow in the following network is 10:

II) Given the following graph with flow/capacity for each link:

 

The residual graph associated to the above solution is the following:  

III) The push-relabeled based algorithms are the ones which involves computing a residual network and looking for augmenting paths.

 

IV) The sum of the incoming flow of a vertex u has to be equal to the sum of the outgoing flow of u, except in the source and sink nodes 

Mark the alternative that list exactly the true statements:

a) only I and IV 

b) only I, II, and IV

c) only II and III

d) only III and IV

e) None of the above 

Original idea by: Levy Chaves

2022-125

Social networks display an assortative behavior. In the friendship network below, consider that John and Karen want to make new friends.

Which alternative lists very likely next friends for John and Karen, respectively:

1. Mike, John
2. Anne, Jane
3. Paul, Paul
4. Mark, Mike
5. None of the above

Original Idea by: Iury Cleveston

2022-124

Consider the two networks A and B above, where the numbers close to each edge represent its respective capacities of flow and π can only assume values greater or equal to 0:

Select the correct alternative below:

A) Independently of the value of π, the maximum flow of network A cannot be bigger than the value of the max flow of network B.

B) If the value of π is 0, the maximum flow of network A will be smaller than the value of the max flow of network B.

C) Depending on the value of π, network B may have a maximum flow bigger than network A.

D) Only if the value of π is bigger than 2 network A will have a bigger flow than network B.

E) None of the above.

Original idea by: Athyrson M. Ribeiro

2022-123

Below are descriptions of Evolving Network models. Select the alternative that correctly relates each description to the named model:

    I. This model generates rather complex degree correlations. It's a possible extension of the preferential attachment model that addresses the low-degree cut-off phenomenon via the inclusion of attractiveness.

    II. This algorithm generates random scale-free networks using a preferential attachment mechanism. The network grows by adding new nodes over time, and these new nodes link to existing nodes in the network with probability proportional to the degree.

    III.  This model also it's a possible extension of the preferential attachment model where we incorporate the role of fitness. In that case , we assume that preferential attachment is driven by the product of a node’s fitness and its degree. Consequently, a node with a higher fitness will increase its degree faster.

    IV. This is a good representation of real networks were average degree s have a high increase on a short time period. In the other models discussed so far, the number of links increases linearly with the number of nodes. In this particular case, the number of links grows faster than N.

    V. This approach intends to replicate the idea of a finite life span, so nodes have a limited lifetime. In these networks, nodes do not disappear abruptly, but fade away throughout, gradually reducing the rate at which they acquire new links. That is done by introducing capacity limitations.

Now mark the correct alternative:

    A. I - Initial attractiveness, II - Barabasi-Albert,  III - Bianconi-Barabási, IV - Accelerated Growth, V - Aging

    B. I - Initial attractiveness, II - Bianconi-Barabási,  III - Barabasi-Albert, IV - Aging, V - Accelerated Growth

    C. I - Bianconi-Barabási, II - Barabasi-Albert,  III - Initial attractiveness, IV - Accelerated Growth, V - Aging

    D. I - Initial attractiveness, II - Bianconi-Barabási,  III - Barabasi-Albert, IV - Accelerated Growth, V - Aging

    E. None of the above

Original idea by: Victória Pedrazzoli

2022-122

A traveling salesperson wants to use the Farthest Insertion algorithm to build a route map for their next trip. Consider the cities below and the cycle BDE as the initial route.

Which alternative represents a possible order of cities (nodes) addition:

 

A) GCFA

B) ACGF

C) FGCA

D) AFCG

E) None of the above



Original Idea by Iury Cleveston

2022-121

Consider the following statements about the Initial Attractiveness model:

I -  Initial attractiveness increases γ, the degree exponent, making the network more homogeneous and reducing the size of the hubs. 

II - Initial attractiveness adds a random component to the probability of attaching to a node. This random component favors the numerous small-degree nodes and weakens the role of preferential attachment

III -  Initial attractiveness enhances the probability that new nodes link to the small-degree nodes, which pushes them towards higher degrees.

IV - The higher the degree of a node, the more relevant its initial attractiveness term gets.

The only statements that are correct are:

A) I, II, and IV.
B) II and III.
C) I, II and III.
D) I, III and IV.
E) None of the above.

Original idea by: Athyrson M. Ribeiro

2022-120

Analyze the following statements and select the correct alternative.

1. The Barabási-Albert model describes a network where a new node is twice as likely to connect to a degree-four node than a degree-two node;
2. When the dynamical exponent is β=1/2 in a BA network, the first-mover advantage might emerge over time, making hubs larger because they arrived earlier. But, in real networks, that is not always the case ; BA is a minimum model and does not account for intrinsic node properties;
3. The Barabási-Albert model predicts networks that result in rich-gets-richer dynamics which are replicated in real networks, regardless of the intrinsic properties of their nodes.

1. Statements I and III are true.
2. Statements I and II are true.
3. Statements II and III are true.
4. Only statement III is true.
5. None of the above.

Original idea by: André Portela