Graph Constructors

The primary function for creating graphs to test community detection algorithms on is the generate function which implements different constructions as methods using Julia's multiple dispatch.

GraphCommunities.ChainedCliques — Type

ChainedCliques <: CommunityGraph

A graph structure that represents a series of connected cliques.

Fields

num_cliques::Int: The number of cliques in the graph.
clique_size::Int: The number of nodes in each clique.

Examples

graph_info = ChainedCliques(num_cliques=5, clique_size=4)
graph = generate(graph_info)

source

GraphCommunities.PlantedPartition — Type

PlantedPartition <: CommunityGraph

The PlantedPartition model, also known as the Stochastic Block Model (SBM), is a probabilistic model commonly used for generating synthetic networks with inherent community structures. This model creates a graph by partitioning nodes into distinct communities and then adding edges between nodes based on intra-community and inter-community probabilities.

Arguments

n_communities::Int: Number of communities or blocks in the graph.
nodes_per_community::Int: Number of nodes within each community.
pintra::Float64: Probability of creating an edge between two nodes within the same community. This defines the density of intra-community edges.
pinter::Float64: Probability of creating an edge between two nodes from different communities. This defines the sparsity of inter-community edges.

Typically, pintra is set to be much larger than pinter to ensure dense intra-community connections and sparse inter-community connections, thereby creating discernible community structures.

Usage

graph1 = generate(PlantedPartition())  # Using default parameters
graph2 = generate(PlantedPartition(n_communities=5, nodes_per_community=10, pintra=0.8, pinter=0.02))

References

Holland, P. W., Laskey, K. B., & Leinhardt, S. (1983). Stochastic blockmodels: First steps. Social networks, 5(2), 109-137.

source

GraphCommunities.KarateClub — Type

KarateClub <: CommunityGraph

The KarateClub graph, often referred to as the "Zachary's Karate Club", is a social network of friendships between 34 members of a karate club at a US university in the 1970s. This dataset has become a standard benchmark in community detection literature because of its well-documented community structure.

The graph captures the observed friendships between the 34 members. During the course of the study, the club split into two communities due to a conflict, making it a valuable dataset for studying community detection algorithms.

Usage

graph = generate(KarateClub())

References

Zachary, W. W. (1977). An information flow model for conflict and fission in small groups. Journal of anthropological research, 452-473.

source

GraphCommunities.generate — Function

generate(structure::ChainedCliques)::SimpleGraph

Create a graph consisting of structure.r cliques, each of size structure.k, chained together.

structure.r represents the number of cliques.
structure.k represents the size of each clique.

Returns a SimpleGraph with the chained cliques.

source

generate(structure::PlantedPartition)::SimpleGraph

Generate a graph based on the planted partition model.

structure.n_communities is the number of communities.
structure.nodes_per_community denotes the number of nodes per community.
structure.pintra is the probability of an edge within a community.
structure.pinter is the probability of an edge between communities.

Returns a SimpleGraph constructed based on the planted partition model.

source

generate(structure::KarateClub)::SimpleGraph

Construct the famous Zachary's Karate Club graph. This graph represents the friendships between the 34 members of a karate club studied by Wayne W. Zachary in 1977.

Returns a SimpleGraph representing the Karate Club network.

source

GraphCommunities.draw_communities — Function

draw_communities(g::AbstractGraph, communities::Dict)

Draw the graph g with nodes colored based on their community assignments.

Arguments

g::AbstractGraph: The input graph.
communities::Dict: A dictionary mapping each vertex to its community.

Returns

A plot with nodes colored based on their community.

Note

This function will only work if each node in the graph is assigned to a community.

source

draw_communities(g::AbstractGraph, node_labels::Vector{Tuple{Int, Int}})

Draw the graph g with nodes colored based on their label assignments.

Arguments

g::AbstractGraph: The input graph.
node_labels::Vector{Tuple{Int, Int}}: A vector of tuples, each containing a node and its label.

Returns

A plot with nodes colored based on their labels.

Example

julia> g = generate(KarateClub())

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

julia> draw_communities(g, communities)

Note

This function will only work if each node in the graph is included in the node_labels vector.

source