infomap

Infomap community detection algorithm.

Uses information theory to find the most efficient way to describe the flow of a random walker on the network. The optimal partition minimizes the description length of the walker’s path (Map Equation).

Algorithm

Calculate steady-state PageRank probabilities (random walker flow)
Initialize each node in its own community
Optimize the Map Equation greedily by merging communities
Repeat until no improvement in description length

When to Use

Use Case	Recommendation
Flow-based communities	✓ Excellent
Random walk structure	✓ Designed for this
Directed graphs	✓ Good (uses PageRank flow)
Information-theoretic interpretation	✓ Provides description length

Complexity

Time: O(V + E) per iteration, typically converges quickly
Space: O(V + E)

Example

import yog
import yog/community/infomap

let graph =
  yog.directed()
  |> yog.add_node(1, "Home")
  |> yog.add_node(2, "About")
  |> yog.add_node(3, "Contact")
  |> yog.add_edges([#(1, 2, 1), #(2, 1, 1), #(2, 3, 1)])

// Basic usage
let communities = infomap.detect(graph)
io.debug(communities.num_communities)

// With custom options
let options = infomap.InfomapOptions(
  teleport_prob: 0.15,
  tolerance: 0.000001,
  max_pagerank_iters: 200,
)
let communities = infomap.detect_with_options(graph, options)

References

Types

InfomapOptions

</>

Options for Infomap algorithm.

pub type InfomapOptions {
  InfomapOptions(
    teleport_prob: Float,
    tolerance: Float,
    max_pagerank_iters: Int,
  )
}

Constructors

```
InfomapOptions(
  teleport_prob: Float,
  tolerance: Float,
  max_pagerank_iters: Int,
)
```
Arguments

teleport_prob

Teleportation probability for PageRank (typically 0.15).

tolerance

Stop when relative improvement is less than this.

max_pagerank_iters

Max iterations for steady-state calculation.

Values

default_options

</>

pub fn default_options() -> InfomapOptions

Default options for Infomap.

detect

</>

pub fn detect(graph: model.Graph(n, e)) -> community.Communities

Detects communities using the Infomap algorithm with default options.

detect_with_options

</>

pub fn detect_with_options(
  graph: model.Graph(n, e),
  options: InfomapOptions,
) -> community.Communities

Detects communities using Infomap with custom options.