modularity

scirs2_graph::algorithms::community::modularity

Function modularity 

Source 
pub fn modularity<N, E, Ix>(
    graph: &Graph<N, E, Ix>,
    communities: &HashMap<N, usize>,
) -> f64
where
    N: Node + Debug,
    E: EdgeWeight + Into<f64> + Copy,
    Ix: IndexType,
Expand description

Computes the modularity of a given community partition

Modularity measures the quality of a partition by comparing the number of edges within communities to what would be expected in a random graph.

§Arguments

  • graph - The graph to analyze
  • communities - Map from nodes to community IDs

§Returns

  • The modularity score (typically between -1 and 1, higher is better)

§Time Complexity

O(m + n) where m is the number of edges and n is the number of nodes. This is the optimized implementation that avoids the O(n²) naive approach.

§Space Complexity

O(n) for storing degree information and community assignments.