Question 2 - Strongly Connected Components

Barabasi's Network Science book describes the World Wide Web as a directed network where nodes are web pages and links are URLs. Imagine a small portion of this network for a university department:

  • A Homepage (H) links to an About page (A) and a Research page (R). 
  • The About page (A) links back to the Homepage (H).
  • The Research page (R) links to three specific Publication pages (P1, P2, P3).
  • Each Publication page (P1, P2, P3) links back to the main Research page (R).


Based on the concept of Strongly Connected Components (SCCs) and the Kosaraju-Sharir algorithm, consider the following propositions:

Propositions:

I. An SCC is any set of nodes where every node is mutually reachable from every other. Therefore, because a path exists from R to P1 and back, the set {R, P1} is a valid SCC.

II. In the context of the World Wide Web, an SCC represents a maximal set of web pages where a user can navigate between any pair of pages within that set. Based on this, the set {H, A} is a valid SCC.

III. The Kosaraju-Sharir algorithm "partitions" a directed graph into a set of disjoint SCCs covering all nodes. With it, the web graph decomposes completely into {H, A} and {R, P1, P2, P3}.

IV. A set of nodes S is an SCC if for any two nodes u and v in S, there exists at least one path from u to v. Therefore, the entire set of pages {H, A, R, P1, P2, P3} forms a single SCC.

Which of the following alternatives is correct?

A. Only propositions I and IV are true.

B. Only propositions II and III are true.

C. Only propositions I, III, and IV are true.

D. All propositions are true.

E. None of the above.


Original Idea by: Eduardo Bouhid

Comentários

  1. Joao Meidanis14 de setembro de 2025 às 13:51

    Boa questão, mas a afirmação II deixa uma dívida. Quando ela fala "a user can navigate between any pair os pages", está falando de links diretos ou podem ser indiretos? Esta dúvida pode ser a diferença entre a afirmação ser verdadeira ou falsa.

    ResponderExcluir

Postar um comentário

Postagens mais visitadas deste blog

Question 3 – Network Flow

Imagem
 The contractors for the new " Alphaville Barão Geraldo " luxury allotment have hired the brilliant students of the MO412 class to design a high-capacity water distribution network. The project's goal is to pump water from the campus lake (Node Lago ) through a series of seven interconnected retention dams (Nodes  A through G ) to the development site (Node Alpha) . The contract specifies that the network  must be able to deliver a minimum of 30,000 liters of water per minute . The students have produced the following design, with pipe capacities also measured in thousands of liters per minute: Analyze the following propositions regarding the network's performance and limitations. I.  Suppose that, to budget cuts, the pipe from  Dam E to Dam G  must be downgraded to a capacity of 5,000 L/min. With this hypothetical change, the contractual minimum delivery of 30,000 liters/minute would  still be met . II.  To improve performance, a proposal is mad...
Leia mais

Question 4 - Avg. next neighbor degree

Imagem
Consider the following example of a standard fully-connected Multilayer Perceptron (MLP), a type of artificial neural network. It has an input layer, a single hidden layer, and an output layer. In this architecture, neurons in one layer are connected to all neurons in the immediately following layer, but there are no connections within a layer or connections that skip layers. Here, the input and output layers have 5 neurons each, while the hidden layer has 10 neurons. Based on this description, would you expect the correlation exponent,  μ, to be: a) µ > 0 b) µ < 0 c) µ = 0 d) µ > 1 e) None of the above Original idea by: Eduardo Bouhid
Leia mais