Advanced search
1 file | 2.34 MB Add to list

IncGraph : incremental graphlet counting for topology optimisation

Robrecht Cannoodt (UGent) , Joeri Ruyssinck (UGent) , Jana Ramon (UGent) , Katleen De Preter (UGent) and Yvan Saeys (UGent)
(2018) PLOS ONE. 13(4).
Author
Organization
Abstract
Motivation : Graphlets are small network patterns that can be counted in order to characterise the structure of a network (topology). As part of a topology optimisation process, one could use graphlet counts to iteratively modify a network and keep track of the graphlet counts, in order to achieve certain topological properties. Up until now, however, graphlets were not suited as a metric for performing topology optimisation; when millions of minor changes are made to the network structure it becomes computationally intractable to recalculate all the graphlet counts for each of the edge modifications. Results : IncGraph is a method for calculating the differences in graphlet counts with respect to the network in its previous state, which is much more efficient than calculating the graphlet occurrences from scratch at every edge modification made. In comparison to static counting approaches, our findings show IncGraph reduces the execution time by several orders of magnitude. The usefulness of this approach was demonstrated by developing a graphlet-based metric to optimise gene regulatory networks. IncGraph is able to quickly quantify the topological impact of small changes to a network, which opens novel research opportunities to study changes in topologies in evolving or online networks, or develop graphlet-based criteria for topology optimisation. Availability : IncGraph is freely available as an open-source R package on CRAN (incgraph). The development version is also available on GitHub (rcannood/incgraph).
Keywords
GENE NETWORK INFERENCE, COMPLEX NETWORKS, BIOLOGY, ORGANIZATION, EXPRESSION, INDEX

Downloads

  • 7175.pdf
    • full text
    • |
    • open access
    • |
    • PDF
    • |
    • 2.34 MB

Citation

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

MLA
Cannoodt, Robrecht et al. “IncGraph : Incremental Graphlet Counting for Topology Optimisation.” PLOS ONE 13.4 (2018): n. pag. Print.
APA
Cannoodt, R., Ruyssinck, J., Ramon, J., De Preter, K., & Saeys, Y. (2018). IncGraph : incremental graphlet counting for topology optimisation. PLOS ONE, 13(4).
Chicago author-date
Cannoodt, Robrecht, Joeri Ruyssinck, Jana Ramon, Katleen De Preter, and Yvan Saeys. 2018. “IncGraph : Incremental Graphlet Counting for Topology Optimisation.” Plos One 13 (4).
Chicago author-date (all authors)
Cannoodt, Robrecht, Joeri Ruyssinck, Jana Ramon, Katleen De Preter, and Yvan Saeys. 2018. “IncGraph : Incremental Graphlet Counting for Topology Optimisation.” Plos One 13 (4).
Vancouver
1.
Cannoodt R, Ruyssinck J, Ramon J, De Preter K, Saeys Y. IncGraph : incremental graphlet counting for topology optimisation. PLOS ONE. 2018;13(4).
IEEE
[1]
R. Cannoodt, J. Ruyssinck, J. Ramon, K. De Preter, and Y. Saeys, “IncGraph : incremental graphlet counting for topology optimisation,” PLOS ONE, vol. 13, no. 4, 2018.
@article{8560110,
  abstract     = {Motivation : Graphlets are small network patterns that can be counted in order to characterise the structure of a network (topology). As part of a topology optimisation process, one could use graphlet counts to iteratively modify a network and keep track of the graphlet counts, in order to achieve certain topological properties. Up until now, however, graphlets were not suited as a metric for performing topology optimisation; when millions of minor changes are made to the network structure it becomes computationally intractable to recalculate all the graphlet counts for each of the edge modifications. 
Results : IncGraph is a method for calculating the differences in graphlet counts with respect to the network in its previous state, which is much more efficient than calculating the graphlet occurrences from scratch at every edge modification made. In comparison to static counting approaches, our findings show IncGraph reduces the execution time by several orders of magnitude. The usefulness of this approach was demonstrated by developing a graphlet-based metric to optimise gene regulatory networks. IncGraph is able to quickly quantify the topological impact of small changes to a network, which opens novel research opportunities to study changes in topologies in evolving or online networks, or develop graphlet-based criteria for topology optimisation. 
Availability : IncGraph is freely available as an open-source R package on CRAN (incgraph). The development version is also available on GitHub (rcannood/incgraph).},
  articleno    = {e0195997},
  author       = {Cannoodt, Robrecht and Ruyssinck, Joeri and Ramon, Jana and De Preter, Katleen and Saeys, Yvan},
  issn         = {1932-6203},
  journal      = {PLOS ONE},
  keywords     = {GENE NETWORK INFERENCE,COMPLEX NETWORKS,BIOLOGY,ORGANIZATION,EXPRESSION,INDEX},
  language     = {eng},
  number       = {4},
  pages        = {11},
  title        = {IncGraph : incremental graphlet counting for topology optimisation},
  url          = {http://dx.doi.org/10.1371/journal.pone.0195997},
  volume       = {13},
  year         = {2018},
}

Altmetric
View in Altmetric
Web of Science
Times cited: