Cargando…
How modular structure can simplify tasks on networks: parameterizing graph optimization by fast local community detection
By considering the task of finding the shortest walk through a Network, we find an algorithm for which the run time is not as O(2(n)), with n being the number of nodes, but instead scales with the number of nodes in a coarsened network. This coarsened network has a number of nodes related to the num...
Autores principales: | , |
---|---|
Formato: | Online Artículo Texto |
Lenguaje: | English |
Publicado: |
The Royal Society Publishing
2014
|
Materias: | |
Acceso en línea: | https://www.ncbi.nlm.nih.gov/pmc/articles/PMC4156142/ https://www.ncbi.nlm.nih.gov/pubmed/25294962 http://dx.doi.org/10.1098/rspa.2014.0224 |
_version_ | 1782333677745733632 |
---|---|
author | Bui-Xuan, Binh-Minh Jones, Nick S. |
author_facet | Bui-Xuan, Binh-Minh Jones, Nick S. |
author_sort | Bui-Xuan, Binh-Minh |
collection | PubMed |
description | By considering the task of finding the shortest walk through a Network, we find an algorithm for which the run time is not as O(2(n)), with n being the number of nodes, but instead scales with the number of nodes in a coarsened network. This coarsened network has a number of nodes related to the number of dense regions in the original graph. Since we exploit a form of local community detection as a preprocessing, this work gives support to the project of developing heuristic algorithms for detecting dense regions in networks: preprocessing of this kind can accelerate optimization tasks on networks. Our work also suggests a class of empirical conjectures for how structural features of efficient networked systems might scale with system size. |
format | Online Article Text |
id | pubmed-4156142 |
institution | National Center for Biotechnology Information |
language | English |
publishDate | 2014 |
publisher | The Royal Society Publishing |
record_format | MEDLINE/PubMed |
spelling | pubmed-41561422014-10-08 How modular structure can simplify tasks on networks: parameterizing graph optimization by fast local community detection Bui-Xuan, Binh-Minh Jones, Nick S. Proc Math Phys Eng Sci Research Articles By considering the task of finding the shortest walk through a Network, we find an algorithm for which the run time is not as O(2(n)), with n being the number of nodes, but instead scales with the number of nodes in a coarsened network. This coarsened network has a number of nodes related to the number of dense regions in the original graph. Since we exploit a form of local community detection as a preprocessing, this work gives support to the project of developing heuristic algorithms for detecting dense regions in networks: preprocessing of this kind can accelerate optimization tasks on networks. Our work also suggests a class of empirical conjectures for how structural features of efficient networked systems might scale with system size. The Royal Society Publishing 2014-10-08 /pmc/articles/PMC4156142/ /pubmed/25294962 http://dx.doi.org/10.1098/rspa.2014.0224 Text en http://creativecommons.org/licenses/by/4.0/ © 2014 The Authors. Published by the Royal Society under the terms of the Creative Commons Attribution License http://creativecommons.org/licenses/by/4.0/, which permits unrestricted use, provided the original author and source are credited. |
spellingShingle | Research Articles Bui-Xuan, Binh-Minh Jones, Nick S. How modular structure can simplify tasks on networks: parameterizing graph optimization by fast local community detection |
title | How modular structure can simplify tasks on networks: parameterizing graph optimization by fast local community detection |
title_full | How modular structure can simplify tasks on networks: parameterizing graph optimization by fast local community detection |
title_fullStr | How modular structure can simplify tasks on networks: parameterizing graph optimization by fast local community detection |
title_full_unstemmed | How modular structure can simplify tasks on networks: parameterizing graph optimization by fast local community detection |
title_short | How modular structure can simplify tasks on networks: parameterizing graph optimization by fast local community detection |
title_sort | how modular structure can simplify tasks on networks: parameterizing graph optimization by fast local community detection |
topic | Research Articles |
url | https://www.ncbi.nlm.nih.gov/pmc/articles/PMC4156142/ https://www.ncbi.nlm.nih.gov/pubmed/25294962 http://dx.doi.org/10.1098/rspa.2014.0224 |
work_keys_str_mv | AT buixuanbinhminh howmodularstructurecansimplifytasksonnetworksparameterizinggraphoptimizationbyfastlocalcommunitydetection AT jonesnicks howmodularstructurecansimplifytasksonnetworksparameterizinggraphoptimizationbyfastlocalcommunitydetection |