Yog.Community (YogEx v0.97.0)

Community detection and clustering algorithms.

Provides types and utility functions for working with community structures in graphs. Community detection algorithms identify groups of nodes that are more densely connected internally than with the rest of the graph.

Algorithms

Algorithm	Module	Best For
Louvain	`Yog.Community.Louvain`	Large graphs, modularity optimization
Leiden	`Yog.Community.Leiden`	Quality guarantee, well-connected communities
Label Propagation	`Yog.Community.LabelPropagation`	Speed, near-linear time
Girvan-Newman	`Yog.Community.GirvanNewman`	Hierarchical structure, edge betweenness
Infomap	`Yog.Community.Infomap`	Information-theoretic, flow-based
Clique Percolation	`Yog.Community.CliquePercolation`	Overlapping communities
Walktrap	`Yog.Community.Walktrap`	Random walk-based distances
Local Community	`Yog.Community.LocalCommunity`	Massive graphs, seed expansion
Fluid Communities	`Yog.Community.FluidCommunities`	Exact `k` partitions, fast

Core Types

Communities - Community assignment mapping nodes to community IDs
Dendrogram - Hierarchical community structure with multiple levels
CommunityId - Integer identifier for a community

Performance Notes

For frequent community-level queries, use to_dict/1 to convert the assignments map to a community-centric structure (community_id -> nodes). Functions like sizes/1, nodes_in/2, and largest/1 perform O(V) scans; to_dict/1 performs a single O(V) conversion that enables O(1) lookups for all subsequent community operations.

Community Structure Visualization

Communities are groups of nodes with dense internal connections and sparse connections to other groups.

graph G { bgcolor="transparent"; node [shape=circle, fontname="inherit"]; edge [fontname="inherit", fontsize=10]; subgraph cluster_c1 { label="Community 1"; color="#6366f1"; style=rounded; 1 -- 2; 2 -- 3; 3 -- 1; } subgraph cluster_c2 { label="Community 2"; color="#f43f5e"; style=rounded; 4 -- 5; 5 -- 6; 6 -- 4; } // Bridge edge between communities 3 -- 4 [label="bridge", color="#94a3b8", style=dashed]; }

iex> alias Yog.Community
iex> graph = Yog.from_edges(:undirected, [
...>   {1, 2, 1}, {2, 3, 1}, {3, 1, 1},
...>   {4, 5, 1}, {5, 6, 1}, {6, 4, 1},
...>   {3, 4, 1}
...> ])
iex> communities = Community.Result.new(%{1 => 0, 2 => 0, 3 => 0, 4 => 1, 5 => 1, 6 => 1})
iex> Community.modularity(graph, communities) > 0.3
iex> Community.modularity(graph, communities) > 0.3
true

Overlapping Communities

In overlapping community detection, nodes can be members of multiple groups.

graph G { bgcolor="transparent"; node [shape=circle, fontname="inherit"]; edge [fontname="inherit", fontsize=10]; subgraph cluster_c1 { label="Community A"; color="#6366f1"; style=rounded; 1; 2; 4; } subgraph cluster_c2 { label="Community B"; color="#f43f5e"; style=rounded; 3; 5; 4; } 1 -- 2; 2 -- 4; 4 -- 1; 3 -- 5; 5 -- 4; 4 -- 3; }

Hierarchical Structure (Dendrogram)

Algorithms like Louvain and Girvan-Newman produce hierarchical results showing how nodes merge into larger functional units.

graph G { rankdir=BT; bgcolor="transparent"; node [shape=circle, fontname="inherit"]; Root [label="Full Graph", color="#10b981", penwidth=2.5, style=bold]; C1 [label="Comm 1", color="#6366f1", penwidth=2]; C2 [label="Comm 2", color="#f43f5e", penwidth=2]; Root -- C1; Root -- C2; C1 -- 1; C1 -- 2; C1 -- 3; C2 -- 4; C2 -- 5; C2 -- 6; }

Examples

# Create a graph with clear community structure (two cliques connected by a bridge)
iex> graph = Yog.undirected()
...> |> Yog.add_node(1, nil)
...> |> Yog.add_node(2, nil)
...> |> Yog.add_node(3, nil)
...> |> Yog.add_node(4, nil)
...> |> Yog.add_node(5, nil)
...> |> Yog.add_node(6, nil)
...> |> Yog.add_edge_ensure(from: 1, to: 2, with: 1)
...> |> Yog.add_edge_ensure(from: 2, to: 3, with: 1)
...> |> Yog.add_edge_ensure(from: 1, to: 3, with: 1)  # Triangle: 1-2-3
...> |> Yog.add_edge_ensure(from: 4, to: 5, with: 1)
...> |> Yog.add_edge_ensure(from: 5, to: 6, with: 1)
...> |> Yog.add_edge_ensure(from: 4, to: 6, with: 1)  # Triangle: 4-5-6
...> |> Yog.add_edge_ensure(from: 3, to: 4, with: 1)  # Bridge between communities
iex> communities = Yog.Community.Louvain.detect(graph)
iex> communities.num_communities >= 2
true
iex> communities_dict = Yog.Community.to_dict(communities)
iex> map_size(communities_dict) >= 2
true
iex> {:ok, _community_id} = Yog.Community.largest(communities)
iex> true
true

Choosing an Algorithm

Louvain: Fast and widely used, good for most cases
Leiden: Better quality than Louvain, guarantees well-connected communities
Label Propagation: Fastest option for very large graphs
Girvan-Newman: When you need hierarchical structure
Infomap: When flow/random walk structure matters
Clique Percolation: When nodes may belong to multiple communities
Walktrap: Good for capturing local structure via random walks
Local Community: When the graph is massive/infinite and you only care about the immediate community around specific seeds
Fluid Communities: Fast and allows finding exactly k communities

Summary

Types

communities()

Community assignment for nodes

community_id()

Community identifier

dendrogram()

Hierarchical community structure

overlapping_communities()

Overlapping communities (nodes can belong to multiple)

Functions

average_clustering_coefficient(graph)

Calculates the average clustering coefficient for the entire graph.

average_community_density(graph, communities)

Calculates the average density across all communities.

clustering_coefficient(graph, node)

Calculates the local clustering coefficient for a node.

community_density(graph, communities, community_id)

Calculates the density of edges within a specific community.

count_triangles(graph)

Counts the total number of triangles in the graph.

density(graph)

Calculates the graph density.

for_node(communities, node)

Returns the community ID for a specific node.

largest(communities)

Returns the community ID with the largest number of nodes.

merge(communities, list)

Merges two communities into one.

modularity(graph, communities, opts \\ [])

Calculates modularity for a given community partition.

nodes_in(communities, community_id)

Returns all nodes belonging to a specific community.

sizes(communities)

Returns a dictionary mapping community IDs to their sizes (number of nodes).

to_dict(communities)

Converts community assignments to a dictionary mapping community IDs to sets of node IDs.

triangles_per_node(graph)

Returns the number of triangles each node participates in.

Types

communities()

@type communities() :: Yog.Community.Result.t()

Community assignment for nodes

community_id()

@type community_id() :: integer()

Community identifier

dendrogram()

@type dendrogram() :: Yog.Community.Dendrogram.t()

Hierarchical community structure

overlapping_communities()

@type overlapping_communities() :: Yog.Community.Overlapping.t()

Overlapping communities (nodes can belong to multiple)

Functions

average_clustering_coefficient(graph)

@spec average_clustering_coefficient(Yog.graph()) :: float()

Calculates the average clustering coefficient for the entire graph.

Examples

iex> graph = Yog.undirected()
...> |> Yog.add_node(1, nil)
...> |> Yog.add_node(2, nil)
...> |> Yog.add_node(3, nil)
...> |> Yog.add_edge_ensure(from: 1, to: 2, with: 1)
...> |> Yog.add_edge_ensure(from: 2, to: 3, with: 1)
...> |> Yog.add_edge_ensure(from: 3, to: 1, with: 1)
iex> Yog.Community.average_clustering_coefficient(graph)
1.0

average_community_density(graph, communities)

@spec average_community_density(Yog.graph(), communities()) :: float()

Calculates the average density across all communities.

Examples

iex> graph = Yog.undirected()
...> |> Yog.add_node(1, nil)
...> |> Yog.add_node(2, nil)
...> |> Yog.add_edge_ensure(from: 1, to: 2, with: 1)
iex> communities = Yog.Community.Result.new(%{1 => 0, 2 => 0, 3 => 0})
iex> avg_cd = Yog.Community.average_community_density(graph, communities)
iex> is_float(avg_cd)
true

clustering_coefficient(graph, node)

@spec clustering_coefficient(Yog.graph(), Yog.node_id()) :: float()

Calculates the local clustering coefficient for a node.

Measures how close the node's neighbors are to forming a complete clique.

Range: [0.0, 1.0]. 1.0 means all neighbors are connected to each other.

Examples

iex> graph = Yog.undirected()
...> |> Yog.add_node(1, nil)
...> |> Yog.add_node(2, nil)
...> |> Yog.add_node(3, nil)
...> |> Yog.add_edge_ensure(from: 1, to: 2, with: 1)
...> |> Yog.add_edge_ensure(from: 2, to: 3, with: 1)
...> |> Yog.add_edge_ensure(from: 3, to: 1, with: 1)
iex> Yog.Community.clustering_coefficient(graph, 1)
1.0

community_density(graph, communities, community_id)

@spec community_density(Yog.graph(), communities(), community_id()) :: float()

Calculates the density of edges within a specific community.

Examples

iex> graph = Yog.undirected()
...> |> Yog.add_node(1, nil)
...> |> Yog.add_node(2, nil)
...> |> Yog.add_node(3, nil)
...> |> Yog.add_edge_ensure(from: 1, to: 2, with: 1)
iex> communities = Yog.Community.Result.new(%{1 => 0, 2 => 0, 3 => 0})
iex> cd = Yog.Community.community_density(graph, communities, 0)
iex> is_float(cd)
true

count_triangles(graph)

@spec count_triangles(Yog.graph()) :: integer()

Counts the total number of triangles in the graph.

A triangle is a set of three nodes where each pair is connected.

Examples

iex> graph = Yog.undirected()
...> |> Yog.add_node(1, nil)
...> |> Yog.add_node(2, nil)
...> |> Yog.add_node(3, nil)
...> |> Yog.add_edge_ensure(from: 1, to: 2, with: 1)
...> |> Yog.add_edge_ensure(from: 2, to: 3, with: 1)
...> |> Yog.add_edge_ensure(from: 3, to: 1, with: 1)
iex> Yog.Community.count_triangles(graph)
1

density(graph)

@spec density(Yog.graph()) :: float()

Calculates the graph density.

The ratio of actual edges to possible edges.

Examples

iex> graph = Yog.undirected()
...> |> Yog.add_node(1, nil)
...> |> Yog.add_node(2, nil)
...> |> Yog.add_node(3, nil)
...> |> Yog.add_edge_ensure(from: 1, to: 2, with: 1)
iex> d = Yog.Community.density(graph)
iex> is_float(d)
true

for_node(communities, node)

@spec for_node(communities(), Yog.node_id()) :: {:ok, community_id()} | :error

Returns the community ID for a specific node.

Returns :error if the node is not assigned to any community.

Examples

iex> communities = Yog.Community.Result.new(%{1 => 0, 2 => 0, 3 => 1})
iex> Yog.Community.for_node(communities, 1)
{:ok, 0}
iex> Yog.Community.for_node(communities, 999)
:error

largest(communities)

@spec largest(communities()) :: {:ok, community_id()} | :error

Returns the community ID with the largest number of nodes.

Returns :error if there are no communities (empty graph or no assignments).

Performance

This function performs a single-pass O(V) reduction. For repeated queries, consider using to_dict/1 first.

Examples

iex> communities = Yog.Community.Result.new(%{1 => 0, 2 => 0, 3 => 0, 4 => 1})
iex> Yog.Community.largest(communities)
{:ok, 0}

merge(communities, list)

@spec merge(communities() | map(), source: community_id(), target: community_id()) ::
  communities() | map()

Merges two communities into one.

All nodes from the source community are reassigned to the target community. The source community ID is effectively removed.

Parameters

communities - The current community partition (can be Result struct or legacy map)
source - The community ID to merge from (will be removed)
target - The community ID to merge into (will be kept)

Examples

iex> communities = Yog.Community.Result.new(%{1 => 0, 2 => 0, 3 => 1, 4 => 1})
iex> merged = Yog.Community.merge(communities, source: 1, target: 0)
iex> merged.assignments
%{1 => 0, 2 => 0, 3 => 0, 4 => 0}
iex> merged.num_communities
1

modularity(graph, communities, opts \\ [])

Calculates modularity for a given community partition.

Modularity measures the quality of a division of a network into modules (communities). High modularity indicates that the community structure captures significant structural patterns in the graph.

Range: [-0.5, 1.0]. Values > 0.3 indicate significant community structure.

Examples

iex> graph = Yog.undirected()
...> |> Yog.add_node(1, nil)
...> |> Yog.add_node(2, nil)
...> |> Yog.add_node(3, nil)
...> |> Yog.add_edge_ensure(from: 1, to: 2, with: 1)
...> |> Yog.add_edge_ensure(from: 2, to: 3, with: 1)
iex> communities = Yog.Community.Result.new(%{1 => 0, 2 => 0, 3 => 0})
iex> q = Yog.Community.modularity(graph, communities)
iex> is_float(q)
true

nodes_in(communities, community_id)

@spec nodes_in(communities(), community_id()) :: MapSet.t(Yog.node_id())

Returns all nodes belonging to a specific community.

Performance

This function performs an O(V) scan. For repeated queries or checking multiple communities, use to_dict/1 first for O(1) lookups.

Examples

iex> communities = Yog.Community.Result.new(%{1 => 0, 2 => 0, 3 => 0, 4 => 1})
iex> Yog.Community.nodes_in(communities, 0)
MapSet.new([1, 2, 3])

sizes(communities)

@spec sizes(communities()) :: %{required(community_id()) => integer()}

Returns a dictionary mapping community IDs to their sizes (number of nodes).

Performance

This function performs a single O(V) scan. For repeated queries, consider using to_dict/1 first.

Examples

iex> communities = Yog.Community.Result.new(%{1 => 0, 2 => 0, 3 => 1, 4 => 1, 5 => 1})
iex> Yog.Community.sizes(communities)
%{0 => 2, 1 => 3}

to_dict(communities)

@spec to_dict(communities()) :: %{required(community_id()) => MapSet.t(Yog.node_id())}

Converts community assignments to a dictionary mapping community IDs to sets of node IDs.

This is useful when you need to iterate over all nodes in each community rather than looking up the community for each node. This performs a single O(V) scan and produces a structure optimized for community-level queries.

Performance Tip: Use this function before making multiple community-level queries. Functions like sizes/1, nodes_in/2, and largest/1 each perform O(V) scans. Converting once with to_dict/1 enables O(1) lookups thereafter.

Examples

iex> communities = Yog.Community.Result.new(%{1 => 0, 2 => 0, 3 => 1})
iex> Yog.Community.to_dict(communities)
%{0 => MapSet.new([1, 2]), 1 => MapSet.new([3])}

triangles_per_node(graph)

@spec triangles_per_node(Yog.graph()) :: %{required(Yog.node_id()) => integer()}

Returns the number of triangles each node participates in.

Examples

iex> graph = Yog.undirected()
...> |> Yog.add_node(1, nil)
...> |> Yog.add_node(2, nil)
...> |> Yog.add_node(3, nil)
...> |> Yog.add_edge_ensure(from: 1, to: 2, with: 1)
...> |> Yog.add_edge_ensure(from: 2, to: 3, with: 1)
...> |> Yog.add_edge_ensure(from: 3, to: 1, with: 1)
iex> Yog.Community.triangles_per_node(graph)
%{1 => 1, 2 => 1, 3 => 1}