Computation of Graphlet Orbits for Nodes and Edges in Sparse Graphs
Graphlet analysis is a useful tool for describing local network topology around individual nodes or edges. A node or an edge can be described by a vector containing the counts of different kinds of graphlets (small induced subgraphs) in which it appears, or the "roles" (orbits) it has with...
| Main Authors: | , |
|---|---|
| Format: | Article |
| Language: | English |
| Published: |
Foundation for Open Access Statistics
2016-07-01
|
| Series: | Journal of Statistical Software |
| Subjects: | |
| Online Access: | https://www.jstatsoft.org/index.php/jss/article/view/2781 |
| _version_ | 1811213548093702144 |
|---|---|
| author | Tomaž Hočevar Janez Demšar |
| author_facet | Tomaž Hočevar Janez Demšar |
| author_sort | Tomaž Hočevar |
| collection | DOAJ |
| description | Graphlet analysis is a useful tool for describing local network topology around individual nodes or edges. A node or an edge can be described by a vector containing the counts of different kinds of graphlets (small induced subgraphs) in which it appears, or the "roles" (orbits) it has within these graphlets. We implemented an R package with functions for fast computation of such counts on sparse graphs. Instead of enumerating all induced graphlets, our algorithm is based on the derived relations between the counts, which decreases the time complexity by an order of magnitude in comparison with past approaches. |
| first_indexed | 2024-04-12T05:47:34Z |
| format | Article |
| id | doaj.art-38d3b41f37084593b3a0aa95ecda0d3e |
| institution | Directory Open Access Journal |
| issn | 1548-7660 |
| language | English |
| last_indexed | 2024-04-12T05:47:34Z |
| publishDate | 2016-07-01 |
| publisher | Foundation for Open Access Statistics |
| record_format | Article |
| series | Journal of Statistical Software |
| spelling | doaj.art-38d3b41f37084593b3a0aa95ecda0d3e2022-12-22T03:45:23ZengFoundation for Open Access StatisticsJournal of Statistical Software1548-76602016-07-0171112410.18637/jss.v071.i101022Computation of Graphlet Orbits for Nodes and Edges in Sparse GraphsTomaž HočevarJanez DemšarGraphlet analysis is a useful tool for describing local network topology around individual nodes or edges. A node or an edge can be described by a vector containing the counts of different kinds of graphlets (small induced subgraphs) in which it appears, or the "roles" (orbits) it has within these graphlets. We implemented an R package with functions for fast computation of such counts on sparse graphs. Instead of enumerating all induced graphlets, our algorithm is based on the derived relations between the counts, which decreases the time complexity by an order of magnitude in comparison with past approaches.https://www.jstatsoft.org/index.php/jss/article/view/2781network analysisgraphletsdata miningbioinformatics |
| spellingShingle | Tomaž Hočevar Janez Demšar Computation of Graphlet Orbits for Nodes and Edges in Sparse Graphs Journal of Statistical Software network analysis graphlets data mining bioinformatics |
| title | Computation of Graphlet Orbits for Nodes and Edges in Sparse Graphs |
| title_full | Computation of Graphlet Orbits for Nodes and Edges in Sparse Graphs |
| title_fullStr | Computation of Graphlet Orbits for Nodes and Edges in Sparse Graphs |
| title_full_unstemmed | Computation of Graphlet Orbits for Nodes and Edges in Sparse Graphs |
| title_short | Computation of Graphlet Orbits for Nodes and Edges in Sparse Graphs |
| title_sort | computation of graphlet orbits for nodes and edges in sparse graphs |
| topic | network analysis graphlets data mining bioinformatics |
| url | https://www.jstatsoft.org/index.php/jss/article/view/2781 |
| work_keys_str_mv | AT tomazhocevar computationofgraphletorbitsfornodesandedgesinsparsegraphs AT janezdemsar computationofgraphletorbitsfornodesandedgesinsparsegraphs |