Advanced search
2 files | 1.86 MB Add to list

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

Ine Melckenbeeck, P. Audenaert (UGent) , Didier Colle (UGent) and Mario Pickavet (UGent)
(2018) BIOINFORMATICS. 34(8). p.1372-1380
Author
Organization
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. 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.
Keywords
SCALE-FREE, NETWORK

Downloads

  • (...).pdf
    • full text
    • |
    • UGent only
    • |
    • PDF
    • |
    • 787.42 KB
  • 7097 i.pdf
    • full text
    • |
    • open access
    • |
    • PDF
    • |
    • 1.08 MB

Citation

Please use this url to cite or link to this publication:

MLA
Melckenbeeck, Ine et al. “Efficiently Counting All Orbits of Graphlets of Any Order in a Graph Using Autogenerated Equations.” BIOINFORMATICS 34.8 (2018): 1372–1380. Print.
APA
Melckenbeeck, I., Audenaert, P., Colle, D., & Pickavet, M. (2018). Efficiently counting all orbits of graphlets of any order in a graph using autogenerated equations. BIOINFORMATICS, 34(8), 1372–1380.
Chicago author-date
Melckenbeeck, Ine, Pieter Audenaert, Didier Colle, and Mario Pickavet. 2018. “Efficiently Counting All Orbits of Graphlets of Any Order in a Graph Using Autogenerated Equations.” Bioinformatics 34 (8): 1372–1380.
Chicago author-date (all authors)
Melckenbeeck, Ine, Pieter Audenaert, Didier Colle, and Mario Pickavet. 2018. “Efficiently Counting All Orbits of Graphlets of Any Order in a Graph Using Autogenerated Equations.” Bioinformatics 34 (8): 1372–1380.
Vancouver
1.
Melckenbeeck I, Audenaert P, Colle D, Pickavet M. Efficiently counting all orbits of graphlets of any order in a graph using autogenerated equations. BIOINFORMATICS. Oxford: Oxford Univ Press; 2018;34(8):1372–80.
IEEE
[1]
I. Melckenbeeck, P. Audenaert, D. Colle, and M. Pickavet, “Efficiently counting all orbits of graphlets of any order in a graph using autogenerated equations,” BIOINFORMATICS, vol. 34, no. 8, pp. 1372–1380, 2018.
@article{8560784,
  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. 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.}},
  author       = {{Melckenbeeck, Ine and Audenaert, P. and Colle, Didier and Pickavet, Mario}},
  issn         = {{1367-4803}},
  journal      = {{BIOINFORMATICS}},
  keywords     = {{SCALE-FREE,NETWORK}},
  language     = {{eng}},
  number       = {{8}},
  pages        = {{1372--1380}},
  publisher    = {{Oxford Univ Press}},
  title        = {{Efficiently counting all orbits of graphlets of any order in a graph using autogenerated equations}},
  url          = {{http://dx.doi.org/10.1093/bioinformatics/btx758}},
  volume       = {{34}},
  year         = {{2018}},
}

Altmetric
View in Altmetric
Web of Science
Times cited: