Cycle Density for Community Detection

Algorithms for computing node, edge, and edge pair cycle densities considering cycles up to length 6.

The package operates broadly follows scikit-network and works directly with scipy sparse matrices.

What is it doing

Cycle density is a measure of how many cycles pass through a node, edge, or edge pair, weighted by how much we think this cycle indicates similarity. For a cycle $C \subseteq G$, the weight (or belief that it represents similarity) is $$ w(C) = \left( \prod_{v \in C} deg_G(v) \right)^{-1}. $$ The cycle density through a node is thus $$ cd(v) = \sum_{C \subseteq G, v \in C} w(C),$$ through an edge $$ cd(u,v) = \sum_{C \subseteq G, u,v \in C} w(c),$$ or through an edge pair $$ cd(uv, xy) = \sum_{C \subseteq G, uv, xy \in C} w(C).$$

Each of these definitions effectively replaces each cycle in the graph with a weighted clique (not applicable for node density). However, for large graphs it's likely this will take too much memory, so we also define options to restrict similarity to adjacent pairs of nodes or edges. $$ cd_{cycle}(u,v) = \sum_{C \subseteq G, uv \in C} w(c)$$ $$ cd_{cycle}(uv, vy) = \sum_{C \subseteq G, uv, vy \in C} w(C)$$

Our idea is that running community detection on these similarity graphs will be helpful.

Getting Started

You can locally install with pip by first cloning this repository.

git clone https://github.com/ryandewolfe33/cycledensity.git
cd cycledensity
pip install .

Check out the example notebook for a quick overview of the syntax. More experiments are also available in the notebooks folder, although they are not (yet) well documented.

This package is still at an early stage of development. Breaking changes may happen without warning and between 0.0.x versions.