Cheeger constant (graph theory)

• https://en.wikipedia.org/wiki/Cheeger_constant_(graph_theory)

$$\partial A := \{ (x, y) \in E(G) \ : \ x \in A, y \in V(G) \setminus A \}$$

$$h(G) := \min \left\{\frac{| \partial A |}{| A |} \ : \ A \subseteq V(G), 0 < | A | \leq \tfrac{1}{2} | V(G)| \right\}.$$

In other words, it’s about finding a set of the most strongly clustered vertices and quantifying how isolated the subgraph is.