Pular para o conteúdo principal

Featured

Postado por

Community Detection and Modularity

In the context of community detection in complex networks, which of the following statements most accurately describes the "resolution limit" inherent in modularity (Q) optimization? Answer Options: A. The resolution limit refers to the inability of the Girvan-Newman algorithm to efficiently recalculate edge betweenness in large-scale networks, thus preventing its practical application. B. The resolution limit refers exclusively to divisive methods, indicating that iterative edge removal always fragments the network into individual components before a maximum of modularity can be achieved. C. The resolution limit is an artifact of the configuration model used in the modularity formula, causing the method to fail to detect small communities, even if they are strongly internally connected (such as cliques), favoring their merging into larger communities to maximize the overall Q. D. The resolution limitation states that modularity (Q) will always assign a negative value to any ...
1 comentário
Read more »
Postado por

TSP with Triangular Inequality: Performance Guarantees and Tour Construction


Considering the Traveling Salesman Problem (TSP) in a complete graph where the triangular inequality holds, which of the following statements most accurately describes the fundamental difference in tour construction and performance guarantee between the Rosenkrantz-Stearns-Lewis algorithm and the Christofides algorithm?


A. Christofides' algorithm uses minimum perfect matching over the odd degree nodes of the minimum spanning tree (MST) to construct an Eulerian graph, achieving an approximation guarantee of 1.5 x optimal cost. In contrast, the Rosenkrantz-Stearns-Lewis algorithm duplicates all edges of the MST, resulting in a guarantee of 2 x optimal cost.

B. Both algorithms are based on the "Farthest Insertion" heuristic, but Christofides applies additional optimization using dynamic programming to achieve a 1.5 x optimal cost guarantee, while Rosenkrantz-Stearns-Lewis does not.

C. The Rosenkrantz-Stearns-Lewis algorithm duplicates the edges of the MST to form an Eulerian tour, and the Christofides algorithm improves on this by finding a minimum perfect match on all nodes in the graph (not just those of odd degree), but both algorithms share the same 2 x cost-optimal performance guarantee.

D. The Rosenkrantz-Stearns-Lewis algorithm uses a minimum perfect match over the odd degree nodes of the MST, achieving a 1.5 x optimal cost guarantee, while the Christofides algorithm duplicates all MST edges, achieving a 2 x optimal cost guarantee.

E. None of the above.

Original idea by: Juan Jose Rodriguez Rodriguez


Comentários

Postar um comentário