Yog.Community.LocalCommunity (YogEx v0.97.1)

Copy Markdown View Source

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.

Algorithm

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)
  • alpha is a resolution parameter controlling community size

When to Use

Use CaseRecommendation
Focus on specific node's neighborhood✓ Ideal
Massive graphs✓ Only explores local region
Streaming/infinite graphs✓ No full graph scan needed
Global community structureUse Louvain instead

Example

# Find the local community around node 5
community = Yog.Community.LocalCommunity.detect(graph, seeds: [5])
# Returns a MapSet containing node IDs in the local community

# With custom options
options = [alpha: 0.8, max_iterations: 500]
community = Yog.Community.LocalCommunity.detect_with_options(graph, [5], options)

References

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

Summary

Types

local_options()

Options for local community detection

Functions

default_options()

Returns default options for local community detection.

detect(graph, list)

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

detect_with(graph, seeds, options, weight_fn)

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

detect_with_options(graph, seeds, opts)

Detects a local community from seeds with custom options.

Types

local_options()

@type local_options() :: %{alpha: float(), max_iterations: integer()}

Options for local community detection

Functions

default_options()

@spec default_options() :: local_options()

Returns default options for local community detection.

  • alpha: 1.0 (resolution parameter)
  • max_iterations: 1000

detect(graph, list)

@spec detect(Yog.graph(), [{:seeds, [Yog.node_id()]}]) :: MapSet.t(Yog.node_id())

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

Example

iex> graph = Yog.undirected() |> Yog.add_edge_ensure(1, 2, 1, default: nil) |> Yog.add_edge_ensure(2, 3, 1, default: nil)
iex> community = Yog.Community.LocalCommunity.detect(graph, seeds: [2])
iex> MapSet.member?(community, 2)
true

detect_with(graph, seeds, options, weight_fn)

@spec detect_with(Yog.graph(), [Yog.node_id()], local_options(), (any() -> float())) ::
  MapSet.t(Yog.node_id())

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

The weight function transforms edge weights to floats for calculations.

detect_with_options(graph, seeds, opts)

@spec detect_with_options(Yog.graph(), [Yog.node_id()], keyword()) ::
  MapSet.t(Yog.node_id())

Detects a local community from seeds with custom options.

Options

  • :alpha - Resolution parameter (default: 1.0). Larger values yield smaller communities.
  • :max_iterations - Maximum iterations (default: 1000)

Example

iex> graph = Yog.undirected() |> Yog.add_edge_ensure(1, 2, 1, default: nil) |> Yog.add_edge_ensure(2, 3, 1, default: nil)
iex> opts = [alpha: 0.5, max_iterations: 100]
iex> community = Yog.Community.LocalCommunity.detect_with_options(graph, [2], opts)
iex> MapSet.member?(community, 2)
true