yog - v5.1.1

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

Types

LocalCommunityOptions

</>

Options for local community detection.

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

Constructors 

  • LocalCommunityOptions(alpha: Float, max_iterations: Int)

    Arguments

    alpha

    Resolution parameter controlling the size of the community. Default is 1.0. Larger values yield smaller communities.

    max_iterations

    Maximum number of adjustment iterations to perform.

Operation

</> 
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)
}

Constructors 

  • Add(node: Int, new_k_in: Float, new_k_out: Float)
  • Remove(node: Int, new_k_in: Float, new_k_out: Float)

Values

default_options

</> 
pub fn default_options() -> LocalCommunityOptions

Default options for local community detection. alpha = 1.0, max_iterations = 1000

detect

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

Detects a local community starting from a list of seed nodes using default options.

Assumes unweighted edges (weight = 1.0) if the graph weights are not Floats. Use detect_float or detect_int or custom weight functions if needed. But for simplicity, we map uniform weights to 1.0 if not specified.

detect_with

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

Detects a local community from seeds using a specific weight function.

✨ Search Document