pivoterpy 0.1.3

Pure Python implementation of Pivoter clique counting algorithm.

pivoterpy

Pure Python implementation of Pivoter clique counting algorithm.

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

quick start

# pip install pivoterpy

from pivoterpy import Pivoter

G = Pivoter.from_adj_matrix(array)

G.count()

G.clique_counts

timings

• Tested on complete graphs with $k$ nodes.
• CPU: AMD Ryzen 5 3600, RAM: 2x16GB DDR4-3200 CL16

Results

$k$	100	200	300	400	500	600	700	800	900	1000
time	0:00	0:02	0:15	1:01	0:29	1:02	1:53	2:06	3:17	4:51
procs					4	4	4	8	8	8

Documentation

usage

For edge lists, all entries must be $(u,v)$ with $u,v\in\mathbb{Z}$ and $0\le u < v < n$.

# (n x n) adjacency matrix. Entry > 0 indicates an edge.
G = Pivoter.from_adj_matrix(adj_matrix)

# (m x 2) edge list (and number of nodes)
G = Pivoter.from_edge_list(edge_list, n)

# 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

• Non multi-proc (default) is generally better for small dense graphs.
• Multi-proc is better for large graphs.

G.count(procs=4) # default is procs=0
G.count(get_curv=True) # vertex clique counts

# available results
G.ec
G.clique_counts

# with get_curv=True
G.vertex_clique_counts
G.curvatures

Extras

the academic 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 - pure Python implementation with parallelization!

todo

features

• make docs
• per edge clique counts
• get on PyPI
• max-clique size parameter

settings

• calculate ec, save clique counts?
• calculate curvs, save vertex clique counts?
• save edge clique counts?