Fast counting of medium-sized rooted subgraphs

Authors Pierre-André G. Maugis, Sofia C. Olhede, P. J. Wolfe

Publication date 31 December 2016

Has companion code repository https://github.com/PierreAndreMaugis/motifs-for-network-samples

Graphs and linear algebra (matrices, eigenvalues, etc.) (05C50) Analysis of algorithms and problem complexity (68Q25) Graph theory (including graph drawing) in computer science (68R10) Programming involving graphs or networks (90C35)

Abstract: We prove that counting copies of any graph

F

in another graph

G

can be achieved using basic matrix operations on the adjacency matrix of

G

. Moreover, the resulting algorithm is competitive for medium-sized

F

: our algorithm recovers the best known complexity for rooted 6-clique counting and improves on the best known for 9-cycle counting. Underpinning our proofs is the new result that, for a general class of graph operators, matrix operations are homomorphisms for operations on rooted graphs.

This page was built for publication: Fast counting of medium-sized rooted subgraphs

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q6281444)