< Terug naar vorige pagina


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

Tijdschriftbijdrage - Tijdschriftartikel

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. Hocevar and Demsar 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.
Tijdschrift: Computer Applications in the Biosciences
ISSN: 0266-7061
Issue: 8
Volume: 34
Pagina's: 1372 - 1380
Jaar van publicatie:2018