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\left(n+m\right). naive solution Use O\left(n^{2}\right) 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