# `Yog.Community`
[🔗](https://github.com/code-shoily/yog_ex/blob/v0.97.0/lib/yog/community.ex#L1)

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.

<div class="graphviz">
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];
}
</div>

    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.

<div class="graphviz">
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;
}
</div>

## Hierarchical Structure (Dendrogram)

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

<div class="graphviz">
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;
}
</div>

## 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

# `communities`

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

Community assignment for nodes

# `community_id`

```elixir
@type community_id() :: integer()
```

Community identifier

# `dendrogram`

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

Hierarchical community structure

# `overlapping_communities`

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

Overlapping communities (nodes can belong to multiple)

# `average_clustering_coefficient`

```elixir
@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`

```elixir
@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`

```elixir
@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`

```elixir
@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`

```elixir
@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`

```elixir
@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`

```elixir
@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`

```elixir
@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`

```elixir
@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`

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`

```elixir
@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`

```elixir
@spec sizes(communities()) :: %{required(community_id()) =&gt; 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`

```elixir
@spec to_dict(communities()) :: %{required(community_id()) =&gt; 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`

```elixir
@spec triangles_per_node(Yog.graph()) :: %{required(Yog.node_id()) =&gt; 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}

---

*Consult [api-reference.md](api-reference.md) for complete listing*