A general purpose algorithm for counting simple cycles and simple paths of any length

Pierre-Louis Giscard, Nils M. Kriege, Richard C. WilsonAlgorithmica 2016 · DOI · OpenReview

TL;DR

This paper introduces a novel, general-purpose algorithm for counting simple cycles and paths in graphs. Its key innovation lies in its time complexity, which depends on the number of connected induced subgraphs rather than the total number of cycles, making it significantly faster for sparse, real-world networks.

What Problem Does This Paper Address?

Counting simple cycles and paths in graphs is a fundamental problem with applications in various fields, from network analysis to bioinformatics. However, for general graphs, these problems are computationally hard (#P-complete). Existing algorithms often have exponential time complexities, making them impractical for large graphs. While some algorithms are efficient for specific graph types (like dense graphs or very short cycles), there's a need for a general-purpose algorithm that performs well on the sparse, complex networks commonly encountered in real-world scenarios. The authors aim to fill this gap by developing an algorithm whose performance is better characterized by graph sparsity and structural properties rather than just the sheer number of cycles.

Methods

The core of the paper is a new algorithm based on an algebraic combinatorics result that relates the generating function of simple cycles to a sum over weakly connected induced subgraphs. The algorithm's main steps involve:

  1. Finding Weakly Connected Induced Subgraphs: It efficiently identifies all weakly connected induced subgraphs of a given size limit ($\ell$). This is achieved using a standard reverse search algorithm.
  2. Evaluating an Explicit Formula: The algorithm then evaluates an explicit formula derived from the algebraic result, which directly counts the cycles or paths based on these subgraphs.

The novelty lies in focusing on connected induced subgraphs, which are typically far fewer than all induced subgraphs, leading to a significant speedup. The paper also extends this approach to handle labeled vertices.

Datasets

The authors evaluated their algorithm on:

  • Erdős-Rényi Random Graphs: These are standard benchmarks for graph algorithms, allowing for systematic study of performance as a function of edge probability and graph size.
  • Real-World Networks:
    • ACTORS: A network representing collaborations between movie actors.
  • INFECTIOUS: A network of face-to-face contacts from an exhibition.
  • WIKIELECTIONS: A directed, weighted network representing Wikipedia user votes.

These real-world datasets are used to demonstrate the algorithm's practical performance on networks with varying sparsity and structure.

Key Insights and Ideas

  • Connected Induced Subgraphs as a Key Parameter: The most significant insight is that the number of connected induced subgraphs (denoted $|S_\ell|$) is a more relevant complexity parameter for counting cycles in sparse graphs than the total number of cycles ($|\text{Cycle}_\ell|$). This is because the algorithm's complexity scales with $|S_\ell|$, which is often much smaller than $|\text{Cycle}_\ell|$.
  • Sparsity is Crucial: The algorithm's advantage is most pronounced on sparse graphs. For Erdős-Rényi random graphs, this advantage emerges when the edge probability is roughly $4/N$, a condition met by many real-world networks.
  • Trade-off with Other Algorithms: While Alon, Yuster, and Zwick's algorithm is faster for counting very short cycles (up to length 7) on undirected graphs, the authors' algorithm offers better scalability for longer cycles and larger graphs due to its lower memory footprint.
  • Labeled Graphs: The algorithm can be extended to count label sequences of cycles/paths, with a complexity that depends on the number of distinct labels ($n$).

Key Results

  • Theoretical Complexity: The algorithm achieves a time complexity of $O(N + M + (\ell^\omega + \ell\Delta)|S_\ell|)$, where $|S_\ell|$ is the number of connected induced subgraphs of size at most $\ell$, $\Delta$ is the maximum degree, and $\omega$ is the matrix multiplication exponent. This is a significant improvement over algorithms whose complexity depends on the total number of cycles.
  • Empirical Performance:
    • On Erdős-Rényi random graphs, the authors' algorithm outperforms Johnson's algorithm when the edge probability $p > 4/N$.
  • For real-world networks like ACTORS, their algorithm is generally faster than Johnson's.
  • The algorithm is memory-efficient, allowing it to handle networks with over 300,000 vertices, whereas AYZ struggles with graphs larger than 12,000 vertices due to its $O(N^2)$ memory requirement.
  • Labeled Graph Complexity: For labeled graphs, the time complexity becomes $O(N + M + (n^\ell \ell^\omega + \ell\Delta)|S_\ell|)$.

Limitations and Future Work

  • "Out of Memory" for AYZ: The authors encountered memory limitations with the AYZ algorithm on larger graphs, preventing direct comparison in all scenarios. This highlights AYZ's significant memory overhead.
  • "Effective" Scaling Parameter: Empirically, the algorithm's time scales with an "effective" parameter $A_{eff} < \Delta$, but its relationship to graph properties like mean or median degree remains unclear, suggesting an area for future investigation.
  • Comparison with Johnson's: While the authors' algorithm is generally better for sparse graphs, Johnson's algorithm can still be faster for counting all simple cycles when graphs are very sparse (average degree $\approx 4$ or less). Deciding which algorithm to use a priori is challenging.
  • Monte Carlo Methods: For very large networks where even this algorithm might be too slow for counting all cycles up to a certain length, the authors suggest using it in conjunction with Monte Carlo methods, as demonstrated in a separate publication.
  • Label Complexity: The $n^\ell$ term in the labeled graph complexity suggests that the algorithm's performance can degrade significantly with a large number of labels and cycle lengths.

Summary updated

Abstract

We describe a general purpose algorithm for counting simple cycles and simple paths of any length $\ell$ on a (weighted di)graph on $N$ vertices and $M$ edges, achieving a time complexity of $O\left(N+M+\big(\ell^\omega+\ell\Delta\big) |S_\ell|\right)$. In this expression, $|S_\ell|$ is the number of (weakly) connected induced subgraphs of $G$ on at most $\ell$ vertices, $\Delta$ is the maximum degree of any vertex and $\omega$ is the exponent of matrix multiplication. We compare the algorithm complexity both theoretically and experimentally with most of the existing algorithms for the same task. These comparisons show that the algorithm described here is the best general purpose algorithm for the class of graphs where $(\ell^{\omega-1}\Delta^{-1}+1) |S_\ell|\leq |\text{Cycle}_\ell|$, with $|\text{Cycle}_\ell|$ the total number of simple cycles of length at most $\ell$, including backtracks and self-loops. On Erd\H{o}s-R\'enyi random graphs, we find empirically that this happens when the edge probability is larger than circa $4/N$. In addition, we show that some real-world networks also belong to this class. Finally, the algorithm permits the enumeration of simple cycles and simple paths on networks where vertices are labeled from an alphabet on $n$ letters with a time complexity of $O\left(N+M+\big(n^\ell\ell^\omega+\ell\Delta\big) |S_\ell|\right)$. A Matlab implementation of the algorithm proposed here is available for download.
BibTeX
@inproceedings{giscard2016general,
  author = {Pierre-Louis Giscard and Nils M. Kriege and Richard C. Wilson},
  title = {{A general purpose algorithm for counting simple cycles and simple paths of any length}},
  booktitle = {Algorithmica},
  year = {2016},
  doi = {10.1007/s00453-019-00552-1},
}
Figure