Yog.Community.Infomap (YogEx v0.97.1)

Copy Markdown View Source

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

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

Map Equation

The Map Equation L(M) = q↷ H(Q) + Σ p↻^i H(P^i)

where:

  • q_↷ is the probability of entering any community (exit rate)
  • H(Q) is the entropy of community transitions
  • p_↻^i is the probability of being in community i and exiting
  • H(P^i) is the entropy of node transitions within community i

When to Use

Use CaseRecommendation
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

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
communities = Yog.Community.Infomap.detect(graph)
IO.inspect(communities.num_communities)

# With custom options
options = %{
  teleport_prob: 0.15,
  tolerance: 0.000001,
  max_pagerank_iters: 200
}
communities = Yog.Community.Infomap.detect_with_options(graph, options)

References

Summary

Types

options()

Options for Infomap algorithm

Functions

default_options()

Returns default options for Infomap.

detect(graph)

Detects communities using the Infomap algorithm with default options.

detect_with_options(graph, opts)

Detects communities using Infomap with custom options.

Types

options()

@type options() :: %{
  teleport_prob: float(),
  tolerance: float(),
  max_pagerank_iters: integer()
}

Options for Infomap algorithm

Functions

default_options()

@spec default_options() :: options()

Returns default options for Infomap.

Defaults

  • teleport_prob: 0.15 - Teleportation probability for PageRank
  • tolerance: 0.000001 - Stop when relative improvement is less than this
  • max_pagerank_iters: 200 - Max iterations for steady-state calculation

detect(graph)

@spec detect(Yog.graph()) :: Yog.Community.Result.t()

Detects communities using the Infomap algorithm with default options.

Example

communities = Yog.Community.Infomap.detect(graph)
IO.inspect(communities.num_communities)

detect_with_options(graph, opts)

@spec detect_with_options(Yog.graph(), options() | keyword()) ::
  Yog.Community.Result.t()

Detects communities using Infomap with custom options.

Options

  • :teleport_prob - Teleportation probability for PageRank (default: 0.15)
  • :tolerance - Stop when relative improvement is less than this (default: 0.000001)
  • :max_pagerank_iters - Max iterations for steady-state calculation (default: 200)

Example

options = %{teleport_prob: 0.1, max_pagerank_iters: 300}
communities = Yog.Community.Infomap.detect_with_options(graph, options)