Suggest edit — strongly connected components

Title

Name

Note

---
title: "strongly connected components"
type: concept
related: [Equivalence, Strongly Connected Components, Eigenvalue]
source: https://www.jemoka.com/posts/kbhstrongly_connected_components/
confidence: high
status: active
---

strongly connected components expose local communities in a graph.
constituents graph \(V,E\)
requirements strongly connected: for all \(v,w \in V\), there is a path from \(v \to w\), and there&rsquo;s a path for \(w \to v\).
We can decompose a graph into strongly connected components where a subgraph is strongly connected. (i.e. they form equivalence class under &ldquo;is strongly connected.&rdquo;)
additional information Kosaraju&rsquo;s Algorithm A way to find strongly connected components in linear time \(O\qty(n+m)\).
naive solution Use \(O\qty(n^{2})\) rounds to DFS from each node and check if the nodes are in a particular strongly connected component, or make a new one.
why do we care? they tell you about communities in a graph structure some algorithms only make sense on SCCs (PageRank eigenvector centrality) condensation graph strongly connected components form a directed acyclic graph, which is useful for analysis.
The condensation graph forms a DAG
Proof idea: if there are edges both ways, there would be a way to go from each component to another and hence the SCC would collapse.
finishing time: largest finish time of any element starting time: smallest starting time of any element