Skip to main content

GraphCentrality

aprender::graph

Trait GraphCentrality 

Source 
pub trait GraphCentrality {
    // Required methods
    fn degree_centrality(&self) -> HashMap<usize, f64>;
    fn pagerank(
        &self,
        damping: f64,
        max_iter: usize,
        tol: f64,
    ) -> Result<Vec<f64>, String>;
    fn betweenness_centrality(&self) -> Vec<f64>;
    fn closeness_centrality(&self) -> Vec<f64>;
    fn eigenvector_centrality(
        &self,
        max_iter: usize,
        tol: f64,
    ) -> Result<Vec<f64>, String>;
    fn katz_centrality(
        &self,
        alpha: f64,
        max_iter: usize,
        tol: f64,
    ) -> Result<Vec<f64>, String>;
    fn harmonic_centrality(&self) -> Vec<f64>;
}
Expand description

Extension trait for graph centrality measures.

Provides methods to compute various centrality metrics that measure the importance or influence of nodes in a graph.

Required Methods§

Source

fn degree_centrality(&self) -> HashMap<usize, f64>

Compute degree centrality for all nodes.

Uses Freeman’s normalization (1978): C_D(v) = deg(v) / (n - 1)

§Returns

HashMap mapping NodeId to centrality score in [0, 1]

§Performance

O(n + m) where n = nodes, m = edges

Source

fn pagerank( &self, damping: f64, max_iter: usize, tol: f64, ) -> Result<Vec<f64>, String>

Compute PageRank using power iteration with Kahan summation.

Uses the PageRank algorithm (Page et al. 1999) with numerically stable Kahan summation (Higham 1993) to prevent floating-point drift in large graphs (>10K nodes).

§Arguments
  • damping - Damping factor (typically 0.85)
  • max_iter - Maximum iterations (default 100)
  • tol - Convergence tolerance (default 1e-6)
§Returns

Vector of PageRank scores (one per node)

Source

fn betweenness_centrality(&self) -> Vec<f64>

Compute betweenness centrality using parallel Brandes’ algorithm.

Uses Brandes’ algorithm (2001) with Rayon parallelization for the outer loop.

§Returns

Vector of betweenness centrality scores (one per node)

Source

fn closeness_centrality(&self) -> Vec<f64>

Compute closeness centrality for all nodes.

Closeness is the reciprocal of the sum of shortest path distances.

§Returns

Vector of closeness centrality scores

Source

fn eigenvector_centrality( &self, max_iter: usize, tol: f64, ) -> Result<Vec<f64>, String>

Compute eigenvector centrality using power iteration.

§Arguments
  • max_iter - Maximum power iterations
  • tol - Convergence tolerance
Source

fn katz_centrality( &self, alpha: f64, max_iter: usize, tol: f64, ) -> Result<Vec<f64>, String>

Compute Katz centrality with attenuation factor.

§Arguments
  • alpha - Attenuation factor (must be in (0, 1))
  • max_iter - Maximum iterations
  • tol - Convergence tolerance
Source

fn harmonic_centrality(&self) -> Vec<f64>

Compute harmonic centrality for all nodes.

Harmonic centrality is the sum of reciprocal distances to all other nodes.

Dyn Compatibility§

This trait is dyn compatible.

In older versions of Rust, dyn compatibility was called "object safety".

Implementors§