tessl/pypi-igraph

High performance graph data structures and algorithms for Python

—

Pending

Overview

Eval results

Files

Community Detection

Name: tessl/pypi-igraph
Author: tessl

Advanced community detection algorithms for identifying groups and clusters within networks. igraph provides over 10 different algorithms for finding communities, from fast heuristics to sophisticated optimization methods.

Capabilities

Modularity-Based Methods

Community detection algorithms based on optimizing modularity, a measure of community structure quality.

class Graph:
    def community_leiden(self, weights=None, resolution=1.0, beta=0.01, initial_membership=None, n_iterations=2):
        """
        Leiden algorithm for community detection (improved Louvain).
        
        Parameters:
        - weights: str/list, edge weights or attribute name
        - resolution: float, resolution parameter (higher = smaller communities)
        - beta: float, randomness in moving vertices
        - initial_membership: list, starting community assignment
        - n_iterations: int, number of iterations
        
        Returns:
        VertexClustering, community assignment
        """

    def community_multilevel(self, weights=None, resolution=1.0):
        """
        Louvain method for community detection (multilevel optimization).
        
        Parameters:
        - weights: edge weights
        - resolution: resolution parameter
        
        Returns:
        VertexClustering, community assignment
        """

    def community_fastgreedy(self, weights=None):
        """
        Fast greedy modularity optimization.
        
        Parameters:
        - weights: edge weights
        
        Returns:
        VertexDendrogram, hierarchical community structure
        """

Usage Examples:

import igraph as ig

# Create sample network
g = ig.Graph.Famous("Zachary")  # Karate club network

# Leiden algorithm (recommended)
leiden_comm = g.community_leiden(resolution=1.0)
print(f"Leiden communities: {len(leiden_comm)}")
print(f"Modularity: {leiden_comm.modularity:.3f}")

# Louvain method  
louvain_comm = g.community_multilevel()
print(f"Louvain communities: {len(louvain_comm)}")

# Fast greedy (returns dendrogram)
fg_dendro = g.community_fastgreedy()
fg_comm = fg_dendro.as_clustering()  # Convert to flat clustering
print(f"Fast greedy communities: {len(fg_comm)}")

# With edge weights
g.es["weight"] = [1 + i*0.1 for i in range(g.ecount())]
weighted_comm = g.community_leiden(weights="weight", resolution=0.8)

# Compare different resolutions
for res in [0.5, 1.0, 2.0]:
    comm = g.community_leiden(resolution=res)
    print(f"Resolution {res}: {len(comm)} communities, modularity {comm.modularity:.3f}")

Information-Theoretic Methods

Community detection based on information theory and compression principles.

class Graph:
    def community_infomap(self, edge_weights=None, vertex_weights=None, trials=10):
        """
        Infomap algorithm based on information theory.
        
        Parameters:
        - edge_weights: str/list, edge weights
        - vertex_weights: str/list, vertex weights  
        - trials: int, number of attempts
        
        Returns:
        VertexClustering, community assignment
        """

    def community_label_propagation(self, weights=None, initial=None, fixed=None):
        """
        Label propagation algorithm.
        
        Parameters:
        - weights: edge weights
        - initial: list, initial labels
        - fixed: list of bool, which vertices have fixed labels
        
        Returns:
        VertexClustering, community assignment
        """

Usage Examples:

# Infomap algorithm
infomap_comm = g.community_infomap(trials=100)
print(f"Infomap communities: {len(infomap_comm)}")

# Label propagation
lp_comm = g.community_label_propagation()
print(f"Label propagation communities: {len(lp_comm)}")

# With vertex weights (e.g., based on degree)
g.vs["weight"] = g.degree()
weighted_infomap = g.community_infomap(vertex_weights="weight")

Hierarchical Methods

Algorithms that produce hierarchical community structures (dendrograms).

class Graph:
    def community_walktrap(self, weights=None, steps=4):
        """
        Walktrap algorithm based on random walks.
        
        Parameters:
        - weights: edge weights
        - steps: int, length of random walks
        
        Returns:
        VertexDendrogram, hierarchical community structure
        """

    def community_edge_betweenness(self, weights=None, directed=True):
        """
        Girvan-Newman algorithm using edge betweenness.
        
        Parameters:
        - weights: edge weights
        - directed: bool, respect edge directions
        
        Returns:
        VertexDendrogram, hierarchical structure
        """

    def community_leading_eigenvector(self, clusters=None, weights=None, arpack_options=None):
        """
        Newman's leading eigenvector method.
        
        Parameters:
        - clusters: int, desired number of clusters (None for automatic)
        - weights: edge weights
        - arpack_options: ARPACKOptions, eigensolver options
        
        Returns:
        VertexClustering, community assignment
        """

Usage Examples:

# Walktrap algorithm
wt_dendro = g.community_walktrap(steps=4)
wt_comm = wt_dendro.as_clustering()
print(f"Walktrap communities: {len(wt_comm)}")

# Edge betweenness (Girvan-Newman)
eb_dendro = g.community_edge_betweenness()
eb_comm = eb_dendro.as_clustering()
print(f"Edge betweenness communities: {len(eb_comm)}")

# Leading eigenvector
le_comm = g.community_leading_eigenvector(clusters=3)
print(f"Leading eigenvector communities: {len(le_comm)}")

# Working with dendrograms
print(f"Optimal cut for walktrap: {wt_dendro.optimal_count}")
for n_clusters in [2, 3, 4, 5]:
    comm_n = wt_dendro.as_clustering(n_clusters)
    print(f"{n_clusters} clusters: modularity {comm_n.modularity:.3f}")

Specialized Methods

Algorithms for specific types of networks or community structures.

class Graph:
    def community_spinglass(self, weights=None, spins=25, parupdate=False, start_temp=1, stop_temp=0.01, cool_fact=0.99, update_rule="config", gamma=1.0):
        """
        Spinglass algorithm for community detection.
        
        Parameters:
        - weights: edge weights
        - spins: int, number of spins (max communities)
        - parupdate: bool, parallel update
        - start_temp: float, starting temperature
        - stop_temp: float, stopping temperature
        - cool_fact: float, cooling factor
        - update_rule: str, update rule ("config", "random", "simple")
        - gamma: float, resolution parameter
        
        Returns:
        VertexClustering, community assignment
        """

    def community_optimal_modularity(self):
        """
        Exact modularity optimization (small graphs only).
        
        Returns:
        VertexClustering, optimal community assignment
        """

Usage Examples:

# Spinglass (works best on smaller graphs)
if g.vcount() <= 100:  # Limit to smaller graphs
    sg_comm = g.community_spinglass(spins=10)
    print(f"Spinglass communities: {len(sg_comm)}")

# Optimal modularity (very small graphs only)
small_g = ig.Graph.Ring(12)
optimal_comm = small_g.community_optimal_modularity()
print(f"Optimal modularity: {optimal_comm.modularity:.3f}")

Community Comparison

Methods for comparing different community structures and measuring their similarity.

def compare_communities(comm1, comm2, method="vi", remove_none=False):
    """
    Compare two community structures.
    
    Parameters:
    - comm1, comm2: Clustering objects to compare
    - method: str, comparison method
      ("vi" - variation of information, "nmi" - normalized mutual information,
       "split-join", "rand", "adjusted_rand")
    - remove_none: bool, ignore vertices not in any community
    
    Returns:
    float, similarity/distance measure
    """

def split_join_distance(comm1, comm2):
    """
    Calculate split-join distance between clusterings.
    
    Parameters:
    - comm1, comm2: Clustering objects
    
    Returns:
    int, split-join distance
    """

Usage Examples:

from igraph import compare_communities, split_join_distance

# Compare different algorithms
leiden_comm = g.community_leiden()
louvain_comm = g.community_multilevel()
infomap_comm = g.community_infomap()

# Variation of information (lower = more similar)
vi_leiden_louvain = compare_communities(leiden_comm, louvain_comm, method="vi")
vi_leiden_infomap = compare_communities(leiden_comm, infomap_comm, method="vi")

# Normalized mutual information (higher = more similar)
nmi_leiden_louvain = compare_communities(leiden_comm, louvain_comm, method="nmi")
nmi_leiden_infomap = compare_communities(leiden_comm, infomap_comm, method="nmi")

print(f"Leiden vs Louvain - VI: {vi_leiden_louvain:.3f}, NMI: {nmi_leiden_louvain:.3f}")
print(f"Leiden vs Infomap - VI: {vi_leiden_infomap:.3f}, NMI: {nmi_leiden_infomap:.3f}")

# Split-join distance
sj_dist = split_join_distance(leiden_comm, louvain_comm)
print(f"Split-join distance: {sj_dist}")

# Compare with ground truth (if available)
# g.vs["true_community"] = [...] # True community labels
# true_clustering = ig.VertexClustering.FromAttribute(g, "true_community")
# accuracy = compare_communities(leiden_comm, true_clustering, method="nmi")

Community Evaluation

Methods for evaluating and validating community structures.

class VertexClustering:
    def modularity(self):
        """
        Calculate modularity of the clustering.
        
        Returns:
        float, modularity value (-0.5 to 1.0)
        """

    def crossing(self):
        """
        Get edges that cross between communities.
        
        Returns:
        list of bool, True for crossing edges
        """

    def giant(self):
        """
        Get largest community.
        
        Returns:
        list of int, vertices in largest community
        """

    def size(self, idx):
        """
        Get size of specific community.
        
        Parameters:
        - idx: int, community index
        
        Returns:
        int, number of vertices in community
        """

    def sizes(self):
        """
        Get sizes of all communities.
        
        Returns:
        list of int, community sizes
        """

Usage Examples:

# Evaluate community structure
comm = g.community_leiden()

# Basic statistics
print(f"Number of communities: {len(comm)}")
print(f"Modularity: {comm.modularity:.3f}")
print(f"Community sizes: {comm.sizes()}")
print(f"Largest community size: {comm.size(comm.giant())}")

# Edge analysis
crossing_edges = comm.crossing()
n_crossing = sum(crossing_edges)
print(f"Edges crossing communities: {n_crossing}/{g.ecount()}")

# Community size distribution
sizes = comm.sizes()
print(f"Size distribution - Mean: {sum(sizes)/len(sizes):.1f}, "
      f"Min: {min(sizes)}, Max: {max(sizes)}")

# Identify vertices in specific community
comm_0_vertices = [i for i, c in enumerate(comm.membership) if c == 0]
print(f"Vertices in community 0: {comm_0_vertices}")

Resolution and Parameter Tuning

Techniques for selecting optimal parameters and exploring different resolution scales.

Usage Examples:

# Resolution parameter exploration for Leiden
modularities = []
n_communities = []
resolutions = [0.1, 0.2, 0.5, 1.0, 1.5, 2.0, 3.0, 5.0]

for res in resolutions:
    comm = g.community_leiden(resolution=res)
    modularities.append(comm.modularity)
    n_communities.append(len(comm))

# Find resolution with best modularity
best_idx = modularities.index(max(modularities))
best_resolution = resolutions[best_idx]
print(f"Best resolution: {best_resolution} (modularity: {modularities[best_idx]:.3f})")

# Stability analysis - run multiple times
stability_results = []
for _ in range(10):
    comm = g.community_leiden(resolution=1.0)
    stability_results.append((len(comm), comm.modularity))

avg_communities = sum(r[0] for r in stability_results) / len(stability_results)
avg_modularity = sum(r[1] for r in stability_results) / len(stability_results)
print(f"Stability - Avg communities: {avg_communities:.1f}, Avg modularity: {avg_modularity:.3f}")

# Multi-scale analysis with hierarchical methods
dendro = g.community_walktrap()
for n_clusters in range(2, min(11, g.vcount())):
    comm = dendro.as_clustering(n_clusters)
    print(f"{n_clusters} clusters: modularity {comm.modularity:.3f}")

Install with Tessl CLI