Postagens

Question 7 - Network Flow

Imagem
Consider the flow network below with flow f and capacity c in f / c format, with node 0 as the source and node 5 as the sink. It is correct to state that: A.  The maximum flow is 18. B. There are no augmenting paths.  C. In the residual network there is only one augmenting path, in the following nodes: 0 -> 1 -> 4 -> 5. D. The maximum flow is 27, obtained after increasing the flow in two augmenting paths, 0 -> 1 -> 4 -> 5 and 0 -> 2 -> 5, by 3 and 6 units, respectively.   E. None of the above.  Original idea by: Vitoria D. M. Pinho 

Question 6 - Network Robustness

 Consider a scale-free network of Protein Interactions, with average degree of 2.9, second moment of 32.3, and degree exponent of 2.89. It is possible to  affirm  that: A. The preferential attachment property is valid, with a probability Π(k) that a link of a new node links to another node of degree k proportional to the square of k. B. This network is perfectly assortative, with a degree correlation coefficient r of 1. C. This network displays enhanced robustness since its breakdown threshold of value 0.9 is grater than the breakdown threshold of random network prediction of value 0.65.  D. This network is in a random network regime, since the degree exponent is close to 3. E. None of the above.  Original idea by: Vitoria D. M. Pinho 

Question 5 - Envolving Networks

 Choose the correct alternative about evolving network models:  A. In the Bianconi-Barabási Model, the preferential attachment is proportional to the node's degree and fitness property, which is the probability of generating new internal links between pre-existing nodes. B. In the Initial Attractiveness Model, the preferential attachment is proportional to the product of the node degree and a constant A, called initial attractiveness.  C. In the Accelerated Growth Model, for any θ value, the network is always scale-free. D. In the Aging Model, the preferential attachment depends on a v parameter. A positive ν means that new nodes are more likely to connect to younger nodes, while a negative v means that new nodes are more likely to connect to older nodes. E. None of the above.  Original idea by: Vitoria D. M. Pinho 

Question 4 - The Barabási-Albert Model

Imagem
Consider the following graph. According to the Linearized Chord Diagram, what are the probabilities that a new node is added to each of the nodes? Consider the normalization constant as 13. A. N1: p =  1/25, N2: p = 4/25, N3: p = 3/25, N4: p = 2/25, N5: p = 1/25, N6: p = 1/25 B. N1: p =  1/13, N2: p = 4/13, N3: p = 3/13, N4: p = 2/13, N5: p = 1/13, , N6: p = 1/13 C.  N1: p =  1/25, N2: p = 4/13, N3: p = 3/13, N4: p = 2/13, N5: p = 1/25, N6: p = 1/25 D. N1: p =  1/3, N2: p = 4/9, N3: p = 3/7, N4: p = 2/5, N5: p = 1/3, N6: p = 1/3 E. None of the above.  Original idea by: Vitoria D. M. Pinho 

Question 3 - Scale-Free Networks

Mark the correct alternative regarding scale-free networks: A. The internet can not be described as a scale-free network since there are no hubs as they would disrupt data traffic. B. The configuration model can generate networks without self-loops and multi-links. C. The degree-preserving randomization can generate networks from a pre-defined degree sequence, but these networks can have self-loops and multi-links. D. The science collaboration network can be described as a scale-free network since its degrees follows a power law distribution. E. None of the above.  Original idea by: Vitoria D. M. Pinho 

Question 2 - BFS and DFS

Imagem
Consider the direct graph below and apply the BFS and DFS algorithms (with timestamps, starting at 0), starting at node A and inspecting the nodes in alphabetical order. Consider the statements below and choose the alternative that lists those that are correct.            I. The finishing time of node A, after the execution of DFS algorithm is 9.           II. The graph has a cross edge and therefore has a cycle.           III. The graph has a backward edge.           IV. The longest distance from A computed by the BFS algorithm is 2.  A. I and IV. B. I, II, and III.  C.  I, II, III and IV. D. I, III, and IV.   E. None of the above.  Original idea by: Vitoria D. M. Pinho     

Question 1 - Graph Theory I

Imagem
Consider a bipartite network with 5 nodes that has the following graph of probability distribution of degrees: Which of the following networks can have these properties? A.  B. C. D. E. None of the above.