Community Detection Algorithms

Louvain <: CommunityDetectionAlgorithm

The Louvain algorithm for community detection in networks.

This method optimizes the modularity of partitions of the graph. It follows a greedy optimization approach that generally operates in time (O(n \log n)) , making it efficient for large-scale networks.

Usage

communities = compute(Louvain(), graph)

References

• Blondel, V. D., Guillaume, J. L., Lambiotte, R., & Lefebvre, E. (2008). Fast unfolding

of communities in large networks. Journal of Statistical Mechanics: Theory and Experiment, 2008(10), P10008.

KClique <: CommunityDetectionAlgorithm

The K-Clique Percolation algorithm for community detection in networks.

This method identifies communities based on the presence of K-clique (with K = 3) structures within the graph, where a K-clique is a fully connected subgraph of K nodes. Two K-cliques are adjacent if they share K-1 nodes, and a community is defined as the union of K-cliques that can be reached from each other through a series of adjacent K-cliques.

Usage

communities = compute(KClique(), graph)

References

• Palla, G., Derényi, I., Farkas, I., & Vicsek, T. (2005). Uncovering the overlapping community structure of complex networks in nature and society. Nature, 435(7043), 814-818.

LabelPropagation <: CommunityDetectionAlgorithm

The Label Propagation algorithm for community detection in networks.

The Label Propagation algorithm identifies communities based on the diffusion of labels throughout the graph. Nodes adopt the label that is most common among their neighbors. This process iteratively refines labels until a consensus or stable state is reached, where nodes have predominantly the same label as their neighbors.

The algorithm can be run in either synchronous or asynchronous mode:

• Synchronous: All nodes update their labels simultaneously in each iteration.
• Asynchronous: Nodes update their labels in a random order.

Arguments

• synchronous::Bool: If true, updates labels in synchronous mode; if false (default),

updates labels in asynchronous mode.

• max_iter::Int: Maximum number of iterations (default is 100). If the algorithm doesn't

converge within this number of iterations, it will halt and return the current vector.

Usage

communities = compute(LabelPropagation(), graph)            # Asynchronous (default)
communities = compute(LabelPropagation(sync=true), graph)   # Synchronous

References

• Raghavan, U. N., Albert, R., & Kumara, S. (2007). Near linear time algorithm to detect

community structures in large-scale networks. Physical review E, 76(3), 036106.

FastLPA <: CommunityDetectionAlgorithm

The (Fast) Label Propagation algorithm for community detection in networks.

The Label Propagation algorithm identifies communities based on the diffusion of labels throughout the graph. Nodes adopt the label that is most common among their neighbors. This process iteratively refines labels until a consensus or stable state is reached, where nodes have predominantly the same label as their neighbors.

The algorithm can be run in either synchronous or asynchronous mode:

• Synchronous: All nodes update their labels simultaneously in each iteration.
• Asynchronous: Nodes update their labels in a random order (not yet implemented).

Arguments

• synchronous::Bool: If true, updates labels in synchronous mode; if false (default),

updates labels in asynchronous mode.

• max_iter::Int: Maximum number of iterations (default is 100). If the algorithm doesn't

converge within this number of iterations, it will halt and return the current vector.

Usage

communities = compute(FastLPA(), graph)            # Synchronous (default)

References

• Raghavan, U. N., Albert, R., & Kumara, S. (2007). Near linear time algorithm to detect

community structures in large-scale networks. Physical review E, 76(3), 036106.

PageRank <: CommunityDetectionAlgorithm

PageRank is an algorithm originally designed for ranking web pages in search results. However, it can also be used more broadly in networks to determine the importance of nodes within a graph. The underlying principle is that more important nodes are likely to receive more links from other nodes.

The algorithm computes a stationary distribution of a random walk on the graph where, at each step, with probability d, the walker randomly chooses an outgoing link from its current node and with probability 1 - d, it jumps to a random node in the graph.

Arguments

• d::Float64: Damping factor (default is 0.85). It represents the probability that the random walker follows an outgoing edge. Typically set between 0.85 and 0.9.
• tol::Float64: Tolerance for determining convergence (default is 1e-6). The algorithm stops iterating once the change between subsequent PageRank vectors is below this value.
• max_iter::Int: Maximum number of iterations (default is 100). If the algorithm doesn't converge within this number of iterations, it will halt and return the current vector.

Usage

pageranks = compute(PageRank(), graph)  # Using default parameters
pageranks = compute(PageRank(d=0.9, tol=1e-7, max_iter=150), graph)

References

• Page, L., Brin, S., Motwani, R., & Winograd, T. (1999). The PageRank citation ranking: Bringing order to the web. Stanford InfoLab.

compute(algo::LabelPropagation, g::SimpleGraph)::LabelArray

Detect communities in a graph g using the Label Propagation algorithm.

The algorithm works by initially assigning each node a unique label. Then, in each iteration, each node adopts the label that is most frequent among its neighbors. The algorithm terminates when no node changes its label or after reaching a maximum number of iterations.

Arguments

• algo::LabelPropagation: An instance indicating the settings of the Label Propagation algorithm.
• g::SimpleGraph: The graph on which to detect communities.

Returns

• A LabelArray where each index corresponds to a vertex and its value indicates its community label.

Example

julia> using GraphCommunities

julia> g = generate(KarateClub())

julia> communities = compute(LabelPropagation(), g)

Notes

The algorithm may not return the same community structure on different runs due to its heuristic nature. However, the structures should be reasonably similar and of comparable quality.

compute(algo::FastLPA, g::SimpleGraph)

Execute the Fast Label Propagation algorithm on a graph.

This function processes a SimpleGraph using the Fast Label Propagation algorithm to perform community detection or labeling. It first preprocesses the graph to generate an edge list and the number of vertices, then applies synchronous label propagation if enabled.

Arguments

• algo::FastLabelPropagation: The Fast Label Propagation algorithm instance.
• g::SimpleGraph: The graph to be processed, represented as a SimpleGraph.

Returns

• If algo.synchronous is true, it returns the result of synchronous label propagation; otherwise, it returns nothing.

Notes

• The graph g is first converted into an edge list and the number of vertices is determined.
• This function delegates to _sync_label_propagation for the actual label propagation process.
• Currently, only synchronous label propagation is implemented. If algo.synchronous is false, the function will return nothing.

Example

julia> g = generate(PlantedPartition())

julia> compute(FastLPA(), g)

compute(algo::FastLPA, edge_list::Vector{Tuple{Int,Int}}, num_vertices::Int)

Execute the Fast Label Propagation algorithm using a precomputed edge list.

This variant of the compute function allows for direct input of a graph's edge list and number of vertices. It's particularly useful when the edge list has been precomputed or when working with a graph representation that doesn't conform to a SimpleGraph.

Arguments

• algo::FastLPA: The Fast Label Propagation algorithm instance.
• edge_list::Vector{Tuple{Int,Int}}: The edge list of the graph, where each edge is represented as a tuple of vertex indices.
• num_vertices::Int: The number of vertices in the graph.

Returns

• If algo.synchronous is true, it returns the result of synchronous label propagation; otherwise, it returns nothing.

Notes

• The edge list should be lexicographically sorted and represent a valid graph.
• Only synchronous label propagation is currently implemented.

compute(algo::FastLPA, g::SimpleWeightedGraph)

Execute the Fast Label Propagation algorithm on a graph.

This function processes a SimpleWeightedGraph using the Fast Label Propagation algorithm to perform community detection or labeling. It first preprocesses the graph to generate an edge list and the number of vertices, then applies synchronous label propagation if enabled.

Arguments

• algo::FastLabelPropagation: The Fast Label Propagation algorithm instance.
• g::SimpleWeightedGraph: The graph to be processed, represented as a SimpleWeightedGraph.

Returns

• If algo.synchronous is true, it returns the result of synchronous label propagation; otherwise, it returns nothing.

Notes

• The graph g is first converted into an edge list and the number of vertices is determined.
• This function delegates to _sync_label_propagation for the actual label propagation process.
• Currently, only synchronous label propagation is implemented. If algo.synchronous is false, the function will return nothing.

Example

julia> compute(FastLPA(), g)

compute(algo::Louvain, g::SimpleGraph)

Detect communities in a graph g using the Louvain algorithm, a method based on modularity optimization.

The algorithm consists of two phases that are repeated iteratively:

1. Local Phase: Each node is moved to the community that yields the highest modularity gain.
2. Aggregation Phase: A new graph is constructed where nodes represent communities from the previous phase.

These phases are repeated until the modularity ceases to increase significantly.

Arguments

• algo::Louvain: Indicates that the Louvain algorithm should be used for community detection.
• g::SimpleGraph: The graph on which to detect communities.

Returns

• A dictionary mapping node IDs in the original graph to their respective community IDs.

Example

julia> using GraphCommunities

julia> g = generate(PlantedPartition())

julia> compute(Louvain(), g)

Notes

The algorithm may not return the same community structure on different runs due to its heuristic nature. However, the structures should be reasonably similar and of comparable quality.

compute(algo::KClique, g::SimpleGraph)::Dict{Int, Int}

Detect communities in a graph g using the K-Clique algorithm.

The function first finds triangles (or 3-cliques) in the graph. It then constructs a k-clique graph where nodes represent triangles, and edges indicate overlap. The connected components of this k-clique graph give the communities in the original graph.

Arguments

• algo::KClique: Indicates that the K-Clique algorithm should be used for community detection.
• g::SimpleGraph: The graph on which to detect communities.

Returns

• A dictionary mapping node IDs in the original graph to their respective community IDs.

Example

julia> using GraphCommunities

julia> g = generate(KarateClub())

julia> compute(KClique(), g)

Notes

Currently, the implementation is restricted to 3-cliques (triangles). Future versions might support other clique sizes.

compute(algo::PageRank, g::AbstractGraph)::Vector{Float64}

Compute the PageRank values of the nodes in graph g using the PageRank algorithm.

Arguments

• algo::PageRank: The PageRank algorithm configuration object. This should contain properties like damping factor (d), maximum number of iterations (max_iter), and tolerance (tol).

• g::AbstractGraph: The graph for which to compute the PageRank. This can be a simple graph, directed graph, or a weighted version of these.

Returns

• A vector of Float64 where each entry represents the PageRank value of the corresponding node in the graph.

Details

The function uses the power iteration method to compute the PageRank values. If the graph is weighted, the weights of the edges are taken into account while calculating the rank.

The algorithm iteratively refines the PageRank values until either the maximum number of iterations is reached or the values converge within the specified tolerance.

Example

julia> g = generate(PlantedPartition())

julia> algo = PageRank(d=0.85, max_iter=100, tol=1e-6)

julia> compute(algo, g)