pivoterpy 1.0.0

Parallelized pure Python implementation of the Pivoter clique counting algorithm.

pivoterpy

Parallelized pure Python implementation of the Pivoter clique counting algorithm.

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

The greatest victory is that which requires no battle - Sun Tzu, The Art of War

quick start

# pip install pivoterpy

from pivoterpy import Pivoter

G = Pivoter.from_adj_matrix(array)

G.count()

G.clique_counts

benchmarks

• CPU: AMD Ryzen 5 3600, RAM: 32GB DDR4-3200MHz CL16
• Tested on complete graphs with n nodes.
• All times shown are the average of 10 runs (in seconds).
• Setup refers to initialization time (nbhds, degen. ordering, etc)

---

n	setup	no mp	4 procs	8 procs
300	0.02
600	0.09	0:04
900	0.22	0:13	0:04
1200	0.36		0:11	0:11
1500	0.69			0:22

Documentation

usage

Requires a N x N adjacency 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 $(u,v)$ with $u,v\in\mathbb{Z}$ and $0\le u < v < n$.

G = Pivoter.from_edge_list(array, n)

Values available after construction.

G.neighborhoods         # list of sets
G.degrees               # list of ints
G.by_degrees            # list of sets
G.degeneracy            # int
G.node_by_degen_order   # list of ints
G.degen_order_by_node   # list of ints
G.degen_order_nbhds     # list of sets

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) # default is False, finds vertex counts

Results available after completion:

G.max_k         # max clique size
G.global_ec     # G.ec (euler characteristic)
G.global_counts # G.clique_counts

if vertex is True:

G.vertex_ec   # G.curvatures
G.vertex_counts # G.vertex_clique_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!