yog/community/local_community

Local community detection using fitness maximization.

This module implements a local community detection algorithm that starts from a set of seed nodes and iteratively expands (or shrinks) the community to maximize a local fitness function. It is particularly useful for extracting the community surrounding a specific node without calculating the global community structure of the entire graph, making it efficient for massive or infinite (implicit) graphs.

The fitness function used is based on Lancichinetti et al. (2009): f(S) = k_in / (k_in + k_out)^alpha where k_in is the sum of internal degrees (twice the internal edge weights), k_out is the sum of external degrees (edges to outside S), and alpha is a resolution parameter controlling community size.

Example

import yog/community/local_community

// Find the local community around node 5
let community = local_community.detect(graph, seeds: [5], alpha: 1.0)
// Returns a Set(NodeId) containing the local community

References

• Lancichinetti et al. (2009). Detecting the overlapping and hierarchical community structure in complex networks.
• Clauset, A. (2005). Finding local community structure in networks.

pub type LocalCommunityOptions {
  LocalCommunityOptions(alpha: Float, max_iterations: Int)
}

pub type Operation {
  Add(node: Int, new_k_in: Float, new_k_out: Float)
  Remove(node: Int, new_k_in: Float, new_k_out: Float)
}

pub fn default_options() -> LocalCommunityOptions

pub fn detect(
  graph: model.Graph(n, e),
  seeds: List(Int),
) -> set.Set(Int)

pub fn detect_with(
  graph: model.Graph(n, e),
  seeds: List(Int),
  options: LocalCommunityOptions,
  weight_fn: fn(e) -> Float,
) -> set.Set(Int)