pivoterpy 1.2.4

Parallelized Python (and Rust) implementation of the Pivoter clique counting algorithm.

pivoterpy

Parallelized Python implementation of the Pivoter clique counting algorithm.

Based on The Power of Pivoting for Exact Clique Counting by S. Jain, C. Seshadhri.

quick start

# pip install pivoterpy

import pivoterpy as piv

G = piv.from_adj_matrix(array)

G.count()

G.global_counts

Documentation

usage

Requires a N x N binary matrix. Only upper triangle is used.

Edges are created for entries > 0 (or True).

G = Pivoter.from_adj_matrix(array)

Requires a M x 2 edge matrix and the positive integer number of nodes $n$.

Note: all elements must be non-negative tuples $(u,v)$. $n$ defaults to the largest $u+1$.

G = Pivoter.from_edge_list(array, n)

Values available after construction.

G.neighborhoods
G.degrees
G.by_degrees
G.degeneracy
G.node_by_degen_order
G.degen_order_by_node
G.degen_order_nbhds

counting

Multiprocessing is generally only beneficial for especially large or dense graphs.

G.count(procs=4) # default is 0 (avoids mp.Pool)
G.count(vertex=True) # finds vertex counts
G.count(edge=True) # finds edge counts
G.count(rust=True) # uses Rust backend

Results available after completion:

G.max_k         # max clique size
G.global_ec     (alternating sum of counts)
G.global_counts

if vertex is True:

G.vertex_ec   # also G.curvatures
G.vertex_counts

Extras

the lore...

April 1971

• Bron-Kerbosch algorithm created by... C. Bron and J. Kerbosch.
• Algorithm 457, Finding All Cliques of an Undirected Graph [H]

October 2006

• E. Tomitaa, A. Tanaka, H. Takahashia say this is a difficult problem.
• The worst-case time complexity for generating all maximal cliques and computational experiments

Jun 2010, March 2011

• Double header by D. Eppstein, M. Loffler, D. Strash. (code)
• Listing All Maximal Cliques in Sparse Graphs in Near-optimal Time
• Listing All Maximal Cliques in Large Sparse Real-World Graph
• D. Strash creates quick-clicks for maximal cliques. (code)

January 2020

• S. Jain, C. Seshadhri drop an absolute banger: Pivoter.
• The Power of Pivoting for Exact Clique Counting
• Code available on GitHub and BitBucket

implementations

• Pivoter - Julia implementation by charunupara. (code)

• PyPivoter - Cython implementation by rckormos. (code)

• pivoterpy - parallelized pure Python implementation!