An Algorithm to Automatically Generate the Combinatorial Orbit Counting Equations.
Graphlets are small subgraphs, usually containing up to five vertices, that can be found in a larger graph. Identification of the graphlets that a vertex in an explored graph touches can provide useful information about the local structure of the graph around that vertex. Actually finding all graphl...
Saved in:
| Main Authors: | , , , , |
|---|---|
| Format: | Article |
| Language: | English |
| Published: |
Public Library of Science (PLoS)
2016-01-01
|
| Series: | PLoS ONE |
| Online Access: | https://doi.org/10.1371/journal.pone.0147078 |
| Tags: |
Add Tag
No Tags, Be the first to tag this record!
|
| _version_ | 1849726919710343168 |
|---|---|
| author | Ine Melckenbeeck Pieter Audenaert Tom Michoel Didier Colle Mario Pickavet |
| author_facet | Ine Melckenbeeck Pieter Audenaert Tom Michoel Didier Colle Mario Pickavet |
| author_sort | Ine Melckenbeeck |
| collection | DOAJ |
| description | Graphlets are small subgraphs, usually containing up to five vertices, that can be found in a larger graph. Identification of the graphlets that a vertex in an explored graph touches can provide useful information about the local structure of the graph around that vertex. Actually finding all graphlets in a large graph can be time-consuming, however. As the graphlets grow in size, more different graphlets emerge and the time needed to find each graphlet also scales up. If it is not needed to find each instance of each graphlet, but knowing the number of graphlets touching each node of the graph suffices, the problem is less hard. Previous research shows a way to simplify counting the graphlets: instead of looking for the graphlets needed, smaller graphlets are searched, as well as the number of common neighbors of vertices. Solving a system of equations then gives the number of times a vertex is part of each graphlet of the desired size. However, until now, equations only exist to count graphlets with 4 or 5 nodes. In this paper, two new techniques are presented. The first allows to generate the equations needed in an automatic way. This eliminates the tedious work needed to do so manually each time an extra node is added to the graphlets. The technique is independent on the number of nodes in the graphlets and can thus be used to count larger graphlets than previously possible. The second technique gives all graphlets a unique ordering which is easily extended to name graphlets of any size. Both techniques were used to generate equations to count graphlets with 4, 5 and 6 vertices, which extends all previous results. Code can be found at https://github.com/IneMelckenbeeck/equation-generator and https://github.com/IneMelckenbeeck/graphlet-naming. |
| format | Article |
| id | doaj-art-b787af52445e42a2a045ecd402f5c800 |
| institution | DOAJ |
| issn | 1932-6203 |
| language | English |
| publishDate | 2016-01-01 |
| publisher | Public Library of Science (PLoS) |
| record_format | Article |
| series | PLoS ONE |
| spelling | doaj-art-b787af52445e42a2a045ecd402f5c8002025-08-20T03:10:02ZengPublic Library of Science (PLoS)PLoS ONE1932-62032016-01-01111e014707810.1371/journal.pone.0147078An Algorithm to Automatically Generate the Combinatorial Orbit Counting Equations.Ine MelckenbeeckPieter AudenaertTom MichoelDidier ColleMario PickavetGraphlets are small subgraphs, usually containing up to five vertices, that can be found in a larger graph. Identification of the graphlets that a vertex in an explored graph touches can provide useful information about the local structure of the graph around that vertex. Actually finding all graphlets in a large graph can be time-consuming, however. As the graphlets grow in size, more different graphlets emerge and the time needed to find each graphlet also scales up. If it is not needed to find each instance of each graphlet, but knowing the number of graphlets touching each node of the graph suffices, the problem is less hard. Previous research shows a way to simplify counting the graphlets: instead of looking for the graphlets needed, smaller graphlets are searched, as well as the number of common neighbors of vertices. Solving a system of equations then gives the number of times a vertex is part of each graphlet of the desired size. However, until now, equations only exist to count graphlets with 4 or 5 nodes. In this paper, two new techniques are presented. The first allows to generate the equations needed in an automatic way. This eliminates the tedious work needed to do so manually each time an extra node is added to the graphlets. The technique is independent on the number of nodes in the graphlets and can thus be used to count larger graphlets than previously possible. The second technique gives all graphlets a unique ordering which is easily extended to name graphlets of any size. Both techniques were used to generate equations to count graphlets with 4, 5 and 6 vertices, which extends all previous results. Code can be found at https://github.com/IneMelckenbeeck/equation-generator and https://github.com/IneMelckenbeeck/graphlet-naming.https://doi.org/10.1371/journal.pone.0147078 |
| spellingShingle | Ine Melckenbeeck Pieter Audenaert Tom Michoel Didier Colle Mario Pickavet An Algorithm to Automatically Generate the Combinatorial Orbit Counting Equations. PLoS ONE |
| title | An Algorithm to Automatically Generate the Combinatorial Orbit Counting Equations. |
| title_full | An Algorithm to Automatically Generate the Combinatorial Orbit Counting Equations. |
| title_fullStr | An Algorithm to Automatically Generate the Combinatorial Orbit Counting Equations. |
| title_full_unstemmed | An Algorithm to Automatically Generate the Combinatorial Orbit Counting Equations. |
| title_short | An Algorithm to Automatically Generate the Combinatorial Orbit Counting Equations. |
| title_sort | algorithm to automatically generate the combinatorial orbit counting equations |
| url | https://doi.org/10.1371/journal.pone.0147078 |
| work_keys_str_mv | AT inemelckenbeeck analgorithmtoautomaticallygeneratethecombinatorialorbitcountingequations AT pieteraudenaert analgorithmtoautomaticallygeneratethecombinatorialorbitcountingequations AT tommichoel analgorithmtoautomaticallygeneratethecombinatorialorbitcountingequations AT didiercolle analgorithmtoautomaticallygeneratethecombinatorialorbitcountingequations AT mariopickavet analgorithmtoautomaticallygeneratethecombinatorialorbitcountingequations AT inemelckenbeeck algorithmtoautomaticallygeneratethecombinatorialorbitcountingequations AT pieteraudenaert algorithmtoautomaticallygeneratethecombinatorialorbitcountingequations AT tommichoel algorithmtoautomaticallygeneratethecombinatorialorbitcountingequations AT didiercolle algorithmtoautomaticallygeneratethecombinatorialorbitcountingequations AT mariopickavet algorithmtoautomaticallygeneratethecombinatorialorbitcountingequations |