Community Detection

A divisive hierarchical algorithm that progressively removes edges with the highest betweenness centrality to reveal community structure. It operates on the principle that inter-community edges have high betweenness.

• Process: Calculates edge betweenness for all edges, removes the edge(s) with the highest score, and recalculates. This repeats until no edges remain.
• Output: A dendrogram showing the hierarchical decomposition of the network.
• Use Case: Effective for analyzing the modular structure of smaller to medium-sized interaction graphs to find critical communication bridges between agent teams.
• Limitation: Computationally expensive for large graphs due to repeated betweenness calculations.

A greedy, hierarchical algorithm that maximizes modularity, a measure of the density of links inside communities versus links between communities.

• Process: Iteratively moves nodes between communities to increase modularity, then aggregates nodes in the same community to form a new network, repeating the process.
• Key Metric: Modularity (Q), where Q > 0 indicates community structure. Values typically range from 0.3 to 0.7.
• Use Case: Extremely fast and scalable, ideal for detecting communities in large-scale agent telemetry graphs with millions of interactions.
• Output: Non-overlapping communities and a hierarchy of partitions.

A near-linear time, semi-supervised algorithm where nodes adopt the label that is most frequent among their neighbors.

• Process: Each node is initialized with a unique label. Iteratively, each node updates its label to the one most common in its neighborhood. The process converges as labels propagate through dense clusters.
• Characteristics: Very fast, requires no prior optimization function, and can naturally identify overlapping communities in some variants.
• Use Case: Excellent for real-time or streaming analysis of dynamic agent interaction graphs where speed is critical.
• Limitation: Results can be somewhat random and unstable due to update order sensitivity.

An information-theoretic algorithm that finds communities by compressing the description of information flow on the network, using the map equation.

• Principle: Models a random walker on the graph. The goal is to find a partition that minimizes the expected description length of the walker's path, effectively finding modules where the walker tends to stay longer.
• Strengths: Naturally handles weighted and directed edges, making it suitable for modeling asymmetric message flows between agents. Often finds more accurate partitions than modularity-based methods.
• Use Case: Analyzing directed communication graphs in multi-agent systems to find information bottlenecks and functional subunits.

A method for finding overlapping communities based on the interconnection of k-cliques (complete subgraphs of size k).

• Process: Finds all cliques of size k in the network. Two k-cliques are considered adjacent if they share k-1 nodes. A community is defined as the union of all k-cliques that can be reached from each other through a series of adjacent k-cliques.
• Output: Communities where nodes can belong to multiple groups, reflecting agents that participate in several functional teams.
• Use Case: Identifying cross-functional agent teams or agents that serve as liaisons between different communities in an interaction network.
• Parameter: The clique size k controls the granularity; higher k finds larger, more robust communities.

A technique that uses the eigenvalues and eigenvectors of a graph matrix (like the Laplacian) to perform dimensionality reduction before clustering nodes in the eigenvector space.

• Process: Constructs a graph Laplacian matrix, computes the first k eigenvectors, and uses them as features to cluster nodes (e.g., with k-means).
• Mathematical Basis: Relies on the property that the multiplicity of the zero eigenvalue of the Laplacian equals the number of connected components. The next eigenvectors provide a basis for partitioning.
• Use Case: Effective for partitioning graphs where communities are not necessarily dense but are separated by minimal graph cuts. Useful for initial analysis of agent network topology.
• Consideration: Requires specifying the number of communities k in advance and is less scalable for very large graphs.

Graph partitioning is the computational task of dividing a graph's nodes into distinct, non-overlapping groups (partitions) to optimize specific criteria, such as minimizing the number of edges between partitions (the cut) while balancing partition sizes. This is a foundational problem for distributing computational workloads and is closely related to community detection, though it often requires pre-specifying the number of partitions.

• Key Algorithms: Kernighan–Lin algorithm, spectral partitioning, multi-level methods like Metis.
• Use Case: In multi-agent systems, partitioning can be used to shard an interaction graph across servers to optimize communication latency and computational load.

Modularity (Q) is a scalar metric, ranging from -1 to 1, that quantifies the strength of division of a network into modules (communities). A high modularity score indicates dense connections within communities and sparse connections between them. Modularity maximization is a leading objective function for community detection algorithms.

• Formula: Compares the actual density of intra-community edges to the expected density if edges were distributed randomly.
• Louvain Algorithm: A famous greedy, hierarchical optimization method that iteratively aggregates nodes to maximize modularity gain, enabling fast detection of communities in large graphs.

Label Propagation is a fast, near-linear time community detection algorithm that operates by iteratively having each node adopt the label that is most frequent among its neighbors. It requires no prior optimization function and is effective for identifying loosely connected communities.

• Process: Nodes are initialized with unique labels. In each iteration, a node updates its label based on a majority vote of its neighbors. Dense groups of nodes converge on a consensus label.
• Advantage: Extremely efficient for large-scale graphs, making it suitable for real-time analysis of evolving agent interaction networks.

The Girvan-Newman algorithm is a classic hierarchical, divisive method for community detection. It progressively removes edges with the highest betweenness centrality—edges that act as the most critical bridges between communities—to reveal the underlying community structure.

• Method: 1. Calculate betweenness centrality for all edges. 2. Remove the edge(s) with the highest score. 3. Recalculate centrality for the remaining edges. 4. Repeat until no edges remain.
• Output: Produces a dendrogram showing the hierarchical decomposition of the graph, allowing analysis at different levels of granularity.

A Stochastic Block Model (SBM) is a generative probabilistic model for graphs that assumes nodes are partitioned into blocks (communities), and the probability of an edge between two nodes depends solely on their block memberships. It provides a statistical framework for inferring community structure.

• Inference: Given an observed graph, algorithms like variational inference or Markov Chain Monte Carlo (MCMC) are used to infer the most likely block assignments and inter-block connection probabilities.
• Advantage: Offers a principled, model-based approach that can handle overlapping communities and assess the statistical significance of detected clusters.

The Clique Percolation Method (CPM) detects overlapping communities by identifying adjacent k-cliques (complete subgraphs of size k). Communities are defined as the union of all k-cliques that can be reached from each other through a series of adjacent k-cliques (sharing k-1 nodes).

• Overlap: A node can belong to multiple communities if it is part of k-cliques that belong to different percolation clusters.
• Use Case: Ideal for analyzing agent collaboration networks where an agent (node) may be a core member of multiple distinct teams or projects simultaneously.