CM++ Pipeline

Customizable modular pipeline for testing an improved version of CM for generating well-connected clusters. Image below from arXiv preprint: Park et. al. (2023). https://github.com/illinois-or-research-analytics/cm_pipeline/tree/main with a GUI now available!

• CM++ Pipeline
  • Documentation
  • Overview
  • Main Features
  • CM Pipeline Overview
  • CM++ Overview
  • Requirements
  • Installation and Setup
    • Installation via Cloning
    • Installation via pip install
  • Example Commands
  • CM++
  • CM Pipeline
  • For Developers
  • Loading a Developer Environment
  • Customizing the Pipeline
  • Manuscript Data
  • Output Files
  • Archive
  • Citations

Figure: CM Pipeline Overview The Connectivity Modifier pipeline starts with an input network and a clustering algorithm. In the first step, an initial clustering on the entire network is obtained. Afterwards, clusters below size $B$ (default: $B=11$ ) and tree clusters are removed from this initial clustering. On this filtered clustering, each cluster is processed as follows. If a cluster has an edge cut below the threshold (default: $\log_{10}{n}$ where $n$ is the number of nodes in the cluster) the edge cut is removed and the two pieces are re-clustered. This process repeats until all clusters are well-connected. The final processing removes small clusters. Note the user can change the value for $B$ and the threshold for connectivity as these are user-defined. The user has the option to not apply the recursive clustering. See information on CC and WCC.

Documentation

For the full documentation see here

Overview

Main Features

By default, CM modifies an input clustering to ensure that each cluster is well-connected. CM does this by doing rounds of mincut and clustering. It is also possible to run CM in a way that does not recursively cluster (CC and WCC).

Default CM:

CM under default settings of $B=11$ and threshold= $\log_{10}{n}$ where $n$ is the number of nodes in the cluster, meaning remove tree clusters and clusters below size $B$ and also ensure that each cluster has a minimum edge cut size greater than the threshold.

CM without removing small clusters or tree clusters

WCC (Well Connected Components)

This is equivalent to running CM pipeline with the pre and post filtering steps turned off and not applying clustering recursively. Equivalently, each cluster is repeatedly cut until it is well-connected. The user has the option of adding in the filtering steps if desired.

CC (Connected Components)

Some clustering methods produce disconnected clusters. CC will take such a clustering and returns the connected components of these clusters. The user has the option of adding in the filtering steps if desired.

Clustering methods that can be used with CM

CM currently enables the use of Leiden optimizing the constant Potts Model, Leiden optimizing under modularity, Iterative K-Core, Markov CLustering, Infomap, and Stochastic Block Models. Example for Stochastic Block Model shown below.

CM Pipeline Overview

The CM Pipeline is a modular pipeline for community detection that contains the following modules:

• Graph Cleaning: Removal of parallel and duplicate edges as well as self loops

• Community Detection: Clusters an input network with one of Leiden, IKC, and InfoMap.

• Cluster Filtration: A pre-processing stage that allows users to filter out clusters that are trees or have size below a given threshold.

• Community Statistics Reporting: Generates node and edge count, modularity score, Constant Potts Model score, conductance, and edge-connectivity at multiple stages.

• Extensibility: Developers can design new stages and wire in new algorithms. Please see the following document for instructions on how to expand the list of supported clustering algorithms as a developer.

• CM++

CM++ Overview

CM++ is a module within the CM Pipeline, having the following features:

• Function: CM++ refines your existing graph clustering by carving them into well-connected clusters with high minimum cut values.

• Flexibility: Users can accompany their definition of a good community with well-connectedness. CM++ works with any clustering algorithm and presently provides build in support for Leiden, IKC, and Infomap.

• Dynamic Thresholding: Connectivity thresholds can be constants, or functions of the number of nodes in the cluster, or the minimum node degree of the cluster.

• Multi-processing: For better performance, users can specify a larger number of cores to process clusters concurrently.

Requirements

• MacOS or Linux operating system
• python3.9 or higher (UPDATE: We are looking into adding support for python3.12. For the time being, please use 3.9<=python<=3.11)
• cmake 3.2.0 or higher
• gcc@10 or higher
• R with the following packages:
  • data.table
  • feather

Installation and Setup

There are several strategies for installation

Installation via Cloning

• Clone the cm_pipeline repository
• Activate the venv which has the necessary packages
• Run pip install -r requirements.txt && pip install .
• Make sure everything installed properly by running cd tests && pytest

Installation via pip install

Simply run pip install git+https://github.com/illinois-or-research-analytics/cm_pipeline. This will install CM++, but to use pipeline functionality, please setup via cloning.

Example Commands

CM++

• python3 -m hm01.cm -i network.tsv -e clustering.tsv -o output.tsv -c leiden -g 0.5 --threshold 1log10 --nprocs 4 --quiet
  • Runs CM++ on a Leiden with resolution 0.5 clustering with connectivity threshold $log_{10}(n)$ (Every cluster with connectivity over the log of the number of nodes is considered "well-connected")
• python3 -m hm01.cm -i network.tsv -e clustering.tsv -o output.tsv -c ikc -k 10 --threshold 1log10 --nprocs 4 --quiet
  • Similar idea but with IKC having hyperparameter $k=10$.
• python3 -m hm01.cm -i network.tsv -e clustering.tsv -o output.tsv -c nop --threshold 0.1 --nprocs 4 --quiet
  • Similar idea but with a nop clusterer, meaning it won't recursively cluster, and only ensure that every cluster is connected. This is sometimes called CM-cc or just -cc for short.
• python3 -m hm01.cm -i network.tsv -e clustering.tsv -o output.tsv -c nop --threshold 1log10 --nprocs 4 --quiet
  • Similar idea but with a nop clusterer, meaning it won't recursively cluster, and only ensure that every cluster is well-connected by performing repeated mincuts. This is sometimes called CM-wcc or just -wcc for short.

CM Pipeline

• Suppose you have a pipeline like the one here. Call it pipeline.json
• Then from the root of this repository run:
  • python -m main pipeline.json

For Developers

Loading a Developer Environment

To quickly set up a developer environment for the CM++ Pipeline, simply run the following commands. (NOTE: Make sure you have Conda installed)

bash conda env create -f environment.yml conda activate

Customizing the Pipeline

• The CM++ Pipeline also allows for users to add their own pipeline stages and clustering methods.
• Please refer to the customization documentation on how to modify the code to allow for your own pipeline stages and .

Manuscript Data

The data used to generate the speedup curve in the manuscript can be found in the Illinois Databank. In all runs, we followed the command:

python3 -m hm01.cm -i (network file) -e (clustering file) -t 1log10 -g 0.001 -c leiden -q -n (1|2|4|8|16|32)

• CEN: cen_pipeline.tar.gz
  • Network: cencmquietpipeline/cen-cm-new-pp-output-20230227-22:50:52/S1cen_cleaned.tsv
  • Clustering: cencmquietpipeline/cen-cm-new-pp-output-20230227-22:50:52/res-0.001/S2cen_leiden.0.001.tsv
• CITPatents: citpatents_networks.tar.gz
  • Network: citpatentsprocessedcm/citpatents_cleaned.tsv
  • Clustering: citpatentsprocessedcm/citpatents_leiden.001.tsv
• Orkut:
  • Network
  • Clustering

Output Files

• The commands executed during the workflow are captured in {output_dir}/{run_name}-{timestamp}/commands.sh. This is the shell script generated by the pipeline that is run to generate outputs.
• The output files generated during the workflow are stored in the folder {output_dir}/{run_name}-{timestamp}/
• The descriptive analysis files can be found in the folder {output_dir}/{run_name}-{timestamp}/analysis with the *.csv file for each of the resolution values.

Archive

• View Old Release Notes

Citations

If you use CM++ in your research, please use the following citation:

bibtex @article{Ramavarapu2024, doi = {10.21105/joss.06073}, url = {https://doi.org/10.21105/joss.06073}, year = {2024}, publisher = {The Open Journal}, volume = {9}, number = {93}, pages = {6073}, author = {Vikram Ramavarapu and Fábio Jose Ayres and Minhyuk Park and Vidya Kamath Pailodi and João Alfredo Cardoso Lamy and Tandy Warnow and George Chacko}, title = {CM++ - A Meta-method for Well-Connected Community Detection}, journal = {Journal of Open Source Software} }

Other Citations

```bibtex @article{Park2024, title = {Well-connectedness and community detection}, volume = {1}, ISSN = {2837-8830}, url = {http://dx.doi.org/10.1371/journal.pcsy.0000009}, DOI = {10.1371/journal.pcsy.0000009}, number = {3}, journal = {PLOS Complex Systems}, publisher = {Public Library of Science (PLoS)}, author = {Park, Minhyuk and Tabatabaee, Yasamin and Ramavarapu, Vikram and Liu, Baqiao and Pailodi, Vidya Kamath and Ramachandran, Rajiv and Korobskiy, Dmitriy and Ayres, Fabio and Chacko, George and Warnow, Tandy}, editor = {Albert, Réka}, year = {2024}, month = nov, pages = {e0000009} }

@software{vikramramavarapu2024_10501118, author={Vikram Ramavarapu and Fabio Jose Ayres and Minhyuk Park and Vidya Kamath P and João Alfredo Cardoso Lamy and Tandy Warnow and George Chacko}, title={{CM++ - A Meta-method for Well-Connected Community Detection}}, month=jan, year=2024, publisher={Zenodo}, version={v4.0.1}, doi={10.5281/zenodo.10501118}, url={https://doi.org/10.5281/zenodo.10501118} }

@misc{park2023wellconnected, title={Well-Connected Communities in Real-World and Synthetic Networks}, author={Minhyuk Park and Yasamin Tabatabaee and Vikram Ramavarapu and Baqiao Liu and Vidya Kamath Pailodi and Rajiv Ramachandran and Dmitriy Korobskiy and Fabio Ayres and George Chacko and Tandy Warnow}, year={2023}, eprint={2303.02813}, archivePrefix={arXiv}, primaryClass={cs.SI} } ```