George Gigilas Jr's Graph Algorithms Quiz Blog

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. ...