Degree Correlations

Considering an undirected graph network with no degree correlation. Let (e_jk) be the probability to find a node with degree j and degree k at the two ends of a randomly selected edge and let (q_k) be the probability to have a degree k node at the end of a link. You are given the average degree:

<k> = 10

and the following degree-distribution probability masses (all other (p_k) can be anything consistent and are not needed):

p_20 = 0.04

p_30 = 0.03

p_50 = 0.02

Using only the information above, compute the 3×3 submatrix of e_jk for degrees 20, 30, and 50. Which option matches this block? Consider the theoretical e_jk for the network with no degree correlation and that the matrix rows and columns correspond to degrees 20, 30, and 50 in that order.

A)

{0.0064  0.0072  0.0080 }

{0.0072  0.0081  0.0090 }

{0.0080  0.0090  0.0100 }


B)

{0.0032   0.0045   0.0060 }

{0.0045   0.0075   0.0080 }

{0.0060   0.0080   0.0090 }


C)

{0.0080   0.0090   0.0100 }

{0.0090   0.0100   0.0110 }

{0.0100   0.0110   0.0120 }


D)

{0.0064   0.0080   0.0096 }

{0.0080   0.0100   0.0120 }

{0.0096   0.0120   0.0144 }


E) None of the above.


Original idea by: Thiago Soares Laitz

Comentários

  1. Joao Meidanis23 de outubro de 2025 às 10:55

    Ótima questão! Fico com ela. Só botei uma formatação LaTeX mais bacaninha.

    ResponderExcluir

Postar um comentário

Postagens mais visitadas deste blog

Communities

Imagem
Consider the undirected graph shown below. The network contains two dense regions: nodes (1-4) and nodes (5-7), connected through node 3. Node 3 also connects to node 8 through the dashed edge (3,8). We wish to apply the Girvan–Newman divisive community detection algorithm, that is based on the betweenness of nodes. Assume that in the first iteration, the dashed edge (3,8) has the highest betweenness and is therefore removed. After removing the edge (3,8), which of the following statements best describes the next step of the algorithm and its structural implications? A) Since the graph becomes disconnected after removing (3,8), the algorithm terminates immediately and each connected component is taken as a final community. B) The algorithm recomputes the betweenness of all remaining edges. Because node 3 still acts as the bridge between the two dense regions (1–4 and 5–7), the edges incident to node 3 are expected to gain higher betweenness, making edges such as (3,5) or (3,7) the next...
Leia mais

Traveling Salesperson Problem

Imagem
A post office must plan a route to visit five cities (A, B, C, D, E) and return to the start. Distances (cost units) are given in the graph below. The graph satisfies the triangle inequality and is undirected. Apply the cheapest insertion heuristic (from the traveling salesperson problem), starting with triangle ABC (initial cycle: A → B → C → A). At each step, insert the vertex that yields the smallest cost increase according to the cheapest insertion heuristic. Which final cycle is obtained and what is its total cost? A) A → B → D → C → E → A, total cost 25 B) A → B → E → D → C → A, total cost 27 C) A → C → B → D → E → A, total cost 29 D) A → D → B → E → C → A, total cost 27 E) None of the above Original idea by: Thiago Soares Laitz
Leia mais

DFS

 Consider the execution of Depth-First Search (DFS) on a graph G. Analyze the following statements: I. The existence of at least one backward edge during the DFS traversal guarantees that G contains at least one cycle. II. In an undirected graph, DFS can generate forward and cross edges if the graph is disconnected. III. After running DFS on a graph, if a backward edge is found, it is still possible to produce a valid topological sort of its vertices. IV. Cross edges alone are sufficient to guarantee that G contains a cycle. Which of the following combinations of statements is true? A) I and III only. B) I and II only. C) Only I. D) II and IV only. E) None of the above. Original idea by: Thiago Laitz
Leia mais