A combinatorial approach to graphlet counting
Abstract Motivation: Small-induced subgraphs called graphlets are emerging as a possible tool for exploration of global and local structure of networks and for analysis of roles of individual nodes. One of the obstacles to their wider use is the computational complexity of algorithms for their disco...
Published in: | Bioinformatics |
---|---|
Main Authors: | , |
Format: | Article in Journal/Newspaper |
Language: | English |
Published: |
Oxford University Press (OUP)
2014
|
Subjects: | |
Online Access: | http://dx.doi.org/10.1093/bioinformatics/btt717 https://academic.oup.com/bioinformatics/article-pdf/30/4/559/48917199/bioinformatics_30_4_559.pdf |
id |
croxfordunivpr:10.1093/bioinformatics/btt717 |
---|---|
record_format |
openpolar |
spelling |
croxfordunivpr:10.1093/bioinformatics/btt717 2024-06-23T07:55:58+00:00 A combinatorial approach to graphlet counting Hočevar, Tomaž Demšar, Janez 2014 http://dx.doi.org/10.1093/bioinformatics/btt717 https://academic.oup.com/bioinformatics/article-pdf/30/4/559/48917199/bioinformatics_30_4_559.pdf en eng Oxford University Press (OUP) Bioinformatics volume 30, issue 4, page 559-565 ISSN 1367-4811 1367-4803 journal-article 2014 croxfordunivpr https://doi.org/10.1093/bioinformatics/btt717 2024-06-11T04:18:25Z Abstract Motivation: Small-induced subgraphs called graphlets are emerging as a possible tool for exploration of global and local structure of networks and for analysis of roles of individual nodes. One of the obstacles to their wider use is the computational complexity of algorithms for their discovery and counting. Results: We propose a new combinatorial method for counting graphlets and orbit signatures of network nodes. The algorithm builds a system of equations that connect counts of orbits from graphlets with up to five nodes, which allows to compute all orbit counts by enumerating just a single one. This reduces its practical time complexity in sparse graphs by an order of magnitude as compared with the existing pure enumeration-based algorithms. Availability and implementation: Source code is available freely at http://www.biolab.si/supp/orca/orca.html. Contact: tomaz.hocevar@fri.uni-lj.si Supplementary information: Supplementary data are available at Bioinformatics online. Article in Journal/Newspaper Orca Oxford University Press Bioinformatics 30 4 559 565 |
institution |
Open Polar |
collection |
Oxford University Press |
op_collection_id |
croxfordunivpr |
language |
English |
description |
Abstract Motivation: Small-induced subgraphs called graphlets are emerging as a possible tool for exploration of global and local structure of networks and for analysis of roles of individual nodes. One of the obstacles to their wider use is the computational complexity of algorithms for their discovery and counting. Results: We propose a new combinatorial method for counting graphlets and orbit signatures of network nodes. The algorithm builds a system of equations that connect counts of orbits from graphlets with up to five nodes, which allows to compute all orbit counts by enumerating just a single one. This reduces its practical time complexity in sparse graphs by an order of magnitude as compared with the existing pure enumeration-based algorithms. Availability and implementation: Source code is available freely at http://www.biolab.si/supp/orca/orca.html. Contact: tomaz.hocevar@fri.uni-lj.si Supplementary information: Supplementary data are available at Bioinformatics online. |
format |
Article in Journal/Newspaper |
author |
Hočevar, Tomaž Demšar, Janez |
spellingShingle |
Hočevar, Tomaž Demšar, Janez A combinatorial approach to graphlet counting |
author_facet |
Hočevar, Tomaž Demšar, Janez |
author_sort |
Hočevar, Tomaž |
title |
A combinatorial approach to graphlet counting |
title_short |
A combinatorial approach to graphlet counting |
title_full |
A combinatorial approach to graphlet counting |
title_fullStr |
A combinatorial approach to graphlet counting |
title_full_unstemmed |
A combinatorial approach to graphlet counting |
title_sort |
combinatorial approach to graphlet counting |
publisher |
Oxford University Press (OUP) |
publishDate |
2014 |
url |
http://dx.doi.org/10.1093/bioinformatics/btt717 https://academic.oup.com/bioinformatics/article-pdf/30/4/559/48917199/bioinformatics_30_4_559.pdf |
genre |
Orca |
genre_facet |
Orca |
op_source |
Bioinformatics volume 30, issue 4, page 559-565 ISSN 1367-4811 1367-4803 |
op_doi |
https://doi.org/10.1093/bioinformatics/btt717 |
container_title |
Bioinformatics |
container_volume |
30 |
container_issue |
4 |
container_start_page |
559 |
op_container_end_page |
565 |
_version_ |
1802648793002278912 |