Efficiently counting all orbits of graphlets of any order in a graph using autogenerated equations

    loading  Checking for direct PDF access through Ovid

Abstract

Motivation

Graphlets are a useful tool to determine a graph's small-scale structure. Finding them is exponentially hard with respect to the number of nodes in each graphlet. Therefore, equations can be used to reduce the size of graphlets that need to be enumerated to calculate the number of each graphlet touching each node. Hočevar and Demšar first introduced such equations, which were derived manually, and an algorithm that uses them, but only graphlets with four or five nodes can be counted this way.

Results

We present a new algorithm for orbit counting, which is applicable to graphlets of any order. This algorithm uses a tree structure to simplify finding orbits, and stabilizers and symmetry-breaking constraints to ensure correctness. This method gives a significant speedup compared to a brute force counting method and can count orbits beyond the capacity of other available tools.

Availability and implementation

An implementation of the algorithm can be found at https://github.com/biointec/jesse.

Related Topics

    loading  Loading Related Articles