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’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 “is strongly connected.”)
additional information
Kosaraju’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