infomap_communities

scirs2_graph::algorithms::community::infomap

Function infomap_communities 

Source 
pub fn infomap_communities<N, E, Ix>(
    graph: &Graph<N, E, Ix>,
    max_iterations: usize,
    tolerance: f64,
) -> InfomapResult<N>
where
    N: Node + Clone + Hash + Eq + Debug,
    E: EdgeWeight + Into<f64> + Copy,
    Ix: IndexType,
Expand description

Infomap algorithm for community detection

The Infomap algorithm uses information theory to find communities that minimize the description length of random walks on the graph. It optimizes the map equation which balances the cost of describing the partition with the cost of describing random walks within and between communities.

§Arguments

  • graph - The undirected graph to analyze
  • max_iterations - Maximum number of optimization iterations
  • tolerance - Convergence tolerance for code length improvement

§Returns

  • An InfomapResult with node assignments, code length, and modularity

§Time Complexity

O(k * m * log n) where k is the number of iterations, m is the number of edges, and n is the number of nodes. Each iteration involves computing flow probabilities and optimizing the map equation across all nodes and edges.

§Space Complexity

O(n + m) for storing flow probabilities, community assignments, and the hierarchical module structure required by the map equation.