George Gigilas Jr's Graph Algorithms Quiz Blog

Consider a network composed of N nodes and E edges called Network A. Network B and Network C were created based on Network A, using the same set of nodes and keeping the same degree distribution, but changing the set of edges. The networks show the following properties: In Network A, hubs connect predominantly to other hubs; In Network B, hubs connect predominantly to low-degree nodes; In Network C, links are placed randomly with respect to node degree. You measured the average nearest-neighbor degree function knn(k) for each network. Which alternative below best describes the behavior of knn(k)? a) Network A: decreasing with k     Network B: increasing with k     Network C: strongly increasing with k b) Network A: approximately constant     Network B: approximately constant     Network C: decreasing with k c) Network A: increasing with k     Network B: decreasing with k     Network C: approximately constant d) Network A: incr...

The following network was generated according to the Barabási-Albert model: Now, consider the following statements. Which of them are true? Note: round every calculation to 2 decimal places. I. Node A has the highest probability of receiving the new link, equal to 0.28. II. Node G has the second highest probability, equal to 0.17. III. Nodes C, D, F, and H have the same probability of receiving a new link, equal to 0.11. IV. Nodes B and E have probabilities equal to 0.04. V. Node A is more than four times as likely as node B to receive the new link. a) T T T F T b) T T F T T c) T F T F T d) F F T F F e) None of the above. Original idea by George Gigilas Junior

 A network G' is generated from a real network G. The following properties are observed: G' preserves the exact degree sequence  of G. The clustering coefficient is close to that expected in a random graph with the same degree sequence. The construction process depends explicitly on the original network structure. Which method best explains these observations? a) Configuration Model , because it generates networks with the same degree sequence and produces low clustering typical of random graphs. b) Degree-Preserving Randomization, because it modifies the original network through edge swaps that preserve degrees while driving the network toward a random configuration. c) Hidden-variable model, because it generates networks from probabilistic connections based on node attributes, rather than modifying the original network. d) A deterministic graph construction, because preserving the degree sequence uniquely determines the network structure. e) None of the above. ...

In a galaxy far far away, there is a planet called Coruscant with approximately 2 trillion habitants. Scientists are trying to estimate the average distance of this network of people. In a previous study, it was observed that the population can be divided into three groups: 500 billion people know 1000 other people in average; 1 trillion people know 7000 other people in average; 500 billion people know 5000 other people in average; Which of the following statements are true: I. Since the network is not random, we cannot estimate the average distance of the network; II. In real networks, the average distance behaves similar to random networks. In this case, the average distance is approximately 3.3; III. Considering that the total population is large and that the average degree is relatively low, the degree distribution is well approximated by a Poisson distribution; IV. The presence of highly connected individuals reduces the average distance in the network. a) II and III. b) III and I...

Consider the following graph, which is a simplified version of part of the Unicamp's institutes map. Which of the following affirmations are true: I. FECFAU and FEAGRI are the only nodes with the lowest degrees. II. The degree distribution shows that 60% of the nodes have degree 3. III. The local clustering coefficient of IQ and IE is 1. IV. The diameter of the graph is 4. V. No links are bridges a) I, II, and III. b) II and V. c) I, III, and IV. d) II, IV, and V. e) None of the above. Original idea by George Gigilas Junior