Question about Communities

A group of network scientists is analyzing a large social network to uncover community structures. They are evaluating several theoretical principles and algorithmic strategies to decide which framework better explains the observed patterns. After reviewing the literature, they make the following statements:

I. A community structure should balance internal density and external sparsity; however, a subgraph that maximizes internal density alone may fail to capture community boundaries consistent with the overall network topology.

II. In hierarchical clustering of networks, bottom-up strategies tend to merge nodes with high topological similarity or shared neighbors, while top-down strategies progressively dismantle inter-community links that maintain global connectivity.

III. The distinction between strong and weak communities reflects whether the internal–external link condition must hold for each vertex individually or only on average for the entire subgraph.

IV. Finding all cliques in a large network usually is computationally impractical, since the maximal clique problem is NP-complete.

Which of the statements above are correct?

A) Only I, II, and III are correct.
B) Only II and III are correct.
C) Only I and II are correct.
D) Only I, III, and IV are correct.
E) None of the above.


Original idea by: Mateus de Padua Vicente

Comentários

  1. Joao Meidanis15 de novembro de 2025 às 06:48

    Boa questão, mas fico na dúvida em relação à afirmação I. Parece correta, mas ela usa termos que não entendo direito. Por exemplo, como saber se uma 'community boundary' é consistente com a 'overall network topology'? Também, a IV parece querer implicar que achar todas as cliques é impraticável porque um certo problema lá é NP-completo. Mas, o minimal clique problem é bem fácil. Será que isto quereria dizer que achar todas as cliques é praticável? Ou, olhando por outro lado. Em grafos completos, o maximal clique problem é bem fácil. Será que isso torna achar todas as cliques praticável? São dúvidas que me ocorrem, e que podem ocorrer ao respondedor típico da questão, creio. Desta forma, prefiro deixá-la fora do blog.

    ResponderExcluir

Postar um comentário

Postagens mais visitadas deste blog

Question about DFS and BFS

Consider a graph G = ( V , E ) G = (V, E) , and the Depth-First Search (DFS) and Breadth-First Search (BFS) algorithms. Analyze the following statements: I. In a DFS execution on a directed graph, the classification of edges as tree, forward, backward, and cross edges depends on the order in which vertices are explored. II. In a BFS executed from a source vertex s s  in an unweighted graph, the order in which vertices are discovered at the same level may vary depending on the order of edges in the adjacency list of the graph, but the minimum distance from each vertex to s s  remains unchanged. III. In directed graphs, a back edge detected during DFS indicates the presence of at least one cycle that includes the origin vertex of the edge. IV. In undirected graphs, BFS can detect all cycles of length 3 (triangles), but it does not guarantee detection of larger cycles. V. DFS guarantees that in a connected undirected graph, the tree generated contains exactly ∣ V ∣ − 1 |V| -...
Leia mais

Question about Network Flow

Consider the flow network below, with vertices  V = { s , a , b , t } , source  s , and sink  t . The edge capacities are given as: ( s , a ) = 10 ,  ( s , b ) = 15 ,  ( a , b ) = 15 ,  ( a , t ) = 10 ,  ( b , t ) = 10 A student applies the Ford-Fulkerson algorithm, choosing augmenting paths in the order they are found by DFS, without using BFS or any other fixed rule. After a few iterations, the student notices that the total flow found is 15, but there still exists an augmenting path in the residual graph. What does this example illustrate about the Ford-Fulkerson method? A)  This behavior only occurs if there are cycles in the graph, which is not the case here . B) The Ford-Fulkerson algorithm may stop before the optimum if the choice of augmenting paths is not made carefully. C) The choice of augmenting paths may affect the number of iterations and efficiency, but the algorithm still finds the maximum flow in the end. D)  The Ford-Fulkers...
Leia mais

Question about Strongly Connected Components (SCCs)

Consider a directed graph  G = ( V , E )  and the Kosaraju-Sharir's algorithm for finding strongly connected components (SCCs). Analyze the following statements: I.   The SCC decomposition of a directed graph is unique, but the particular order in which SCCs are discovered by Kosaraju’s algorithm may depend on the order of adjacency lists. II.   If a directed graph has no back edges in a DFS traversal, then each vertex forms a distinct SCC. III.  If  G  is strongly connected, then the second DFS in Kosaraju’s algorithm produces a single tree covering all vertices, regardless of the order of exploration. IV.   The order of vertices given by decreasing finishing times of the first DFS guarantees that the second DFS on the transposed graph  G T  discovers one SCC at a time. Select the correct alternative: A) Only I and II are correct. B) Only I and IV are correct. C) Only I, II and IV are correct. D) Only I, III and IV are correct. E) ...
Leia mais