CDlib

CDlib is a Python software package designed for working with communities in complex networks. Its primary capabilities include:

• Extracting: Running community detection algorithms on networks.
• Comparing: Measuring similarities or differences between different community structures.
• Evaluating: Assessing the quality or properties of detected communities.

The library provides a standardized input/output interface for various community detection algorithms, many of which are inherited from existing specialized projects.

The cdlib library is organized into several specialized modules, each targeting a specific stage or type of community detection task. When building workflows, you can navigate the library using these core modules:

• Algorithms: Core community detection algorithms.
• Classes: High-level abstractions and data structures.
• Temporal Clustering: Methods for detecting communities in dynamic/temporal networks.
• Events: Detection and analysis of events within networks.
• Evaluation: Metrics and methods to evaluate the quality of detected communities.
• Validation: Methods to validate community structures.
• Viz: Visualization tools for networks and communities.
• Readwrite: Utilities for importing and exporting network and community data.
• Utils: General helper functions.

To evaluate community detection algorithms where topological ground truth is required, cdlib provides synthetic network generators. These generators create networks with planted community structures.

For static networks, all generators in the cdlib.benchmark module return a tuple containing:

1. A networkx.Graph object representing the generated network.
2. A cdlib.NodeClustering object representing the ground truth community structure.

Available static network generators include:

• GRP
• LFR
• PP
• RPG
• SBM
• XMark (for node-attributed static networks)

To facilitate standard evaluation tasks, cdlib provides synthetic network generators that include topological community ground truth annotations. These benchmarks are categorized by the type of community discovery being performed:

• Static community discovery.
• Dynamic community discovery.
• Feature-rich (node-attributed) community discovery.

These benchmarks allow you to test how well your algorithms identify communities against a known, mathematically generated ground truth.

For testing against real-world data, cdlib integrates well-known medium-size network datasets that come with ground-truth community annotations.

Because these datasets are large, cdlib uses a specialized API to fetch them transparently from a dedicated remote repository. This allows you to evaluate topological partitions against semantic ground truths without manually managing large data files.

CDlib provides two primary ways to handle multiple instantiations of community detection:

1. Varying parameters of a single algorithm: Use grid_execution to run the same method multiple times while varying its input parameters across a defined grid.
2. Comparing multiple different algorithms: Use pool to manage and compare results from a collection of different community detection algorithms.

# Conceptual usage pattern
# Use grid_execution to vary parameters of one algorithm
# Use pool to compare multiple different algorithms

CDlib standardizes network community representations through several Clustering classes. Each class is designed to capture specific community characteristics. Depending on the algorithm used, CDlib outputs one of the following types:

• NodeClustering: Represents node communities, either as crisp partitions (disjoint sets) or overlapping groups.
• FuzzyNodeClustering: Represents overlapping node communities where each node has an explicit belonging score to a community.
• BiNodeClustering: Used for clustering Bipartite graphs, representing class-homogeneous communities.
• AttrNodeClustering: Used for clustering feature-rich (node-attributed) graphs.
• EdgeClustering: Represents communities formed by edges.
• TemporalClustering: Represents communities within Temporal Networks.

Temporal Trade-off algorithms process network evolution iteratively. Unlike Instant Optimal approaches, they do not treat snapshots in isolation; instead, they use the network state and the communities identified in the previous step (or $n$ previous steps) to inform the community detection in the current step.

The process follows an iterative pattern:

1. Initialization: Find communities for the initial state of the network.
2. Update: Find communities at step $t$ by using the graph at $t$ combined with information from past steps.

This class of algorithms is designed for scenarios where the temporal continuity of communities is a core part of the discovery process.

CDlib provides a wide range of static community discovery algorithms. These are categorized by the type of partition they produce. When choosing an algorithm, identify which partition type matches your network and research goals:

• Crisp partition: Hard clustering where each node belongs to exactly one community.
• Overlapping clustering: Nodes can belong to multiple communities.
• Fuzzy partition: Soft clustering where nodes have varying degrees of membership.
• Bipartite clustering: Specifically designed for clustering bipartite networks.
• Feature-rich (node attributed) clustering: Leverages both network topology and node features/attributes.
• Antichains clustering in DAG: Specifically for directed acyclic graphs.