Skip to main content

cheeger_bounds

Function cheeger_bounds 

Source
pub fn cheeger_bounds(graph: &Graph) -> IgraphResult<(f64, f64)>
Expand description

Compute Cheeger constant bounds from the normalized Laplacian.

The Cheeger inequality relates the isoperimetric number h(G) to the normalized algebraic connectivity μ_2:

μ_2/2 ≤ h(G) ≤ √(2·μ_2)

Returns (lower_bound, upper_bound).

§Examples

use rust_igraph::{Graph, cheeger_bounds};

let g = Graph::from_edges(&[(0,1),(1,2),(0,2)], false, Some(3)).unwrap();
let (lo, hi) = cheeger_bounds(&g).unwrap();
assert!(lo <= hi + 1e-10);
assert!(lo >= 0.0);