Question 6

 Consider the following network:

The Girvan–Newman algorithm detects communities by iteratively removing edges with the highest edge betweenness centrality.

Which edge is most likely to be removed first?

a) (2,4)

b) (4,6)

c) (4,5)

d) (3,7)

e) None of the above.

Original idea by George Gigilas Junior

Comentários

  1. Joao Meidanis23 de maio de 2026 às 11:24

    Betweenness centrality is costly to calculate. My would be (7,8), b ut I need to check.

    ResponderExcluir
  2. George Gigilas Jr's Graph Algorithms Quiz Blog25 de maio de 2026 às 16:14

    Hmm maybe I misunderstood it, but I thought it would be (3,7). There is just one path per node that crosses (7,8)

    ResponderExcluir

Postar um comentário

Postagens mais visitadas deste blog

Question 1

Imagem
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
Leia mais

Question 2

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

Question 3

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