Local heuristics and the emergence of spanning subgraphs in complex networks

A O Stauffer, Valmir C. Barbosa

Research output: Contribution to journalArticle

5 Citations (Scopus)

Abstract

We study the use of local heuristics to determine spanning subgraphs for use in the dissemination of information in complex networks. We introduce two different heuristics and analyze their behavior in giving rise to spanning subgraphs that perform well in terms of allowing every node of the network to be reached, of requiring relatively few messages and small node bandwidth for information dissemination, and also of stretching paths with respect to the underlying network only modestly. We contribute a detailed mathematical analysis of one of the heuristics and provide extensive simulation results on random graphs for both of them. These results indicate that, within certain limits, spanning subgraphs are indeed expected to emerge that perform well in respect to all requirements. We also discuss the spanning subgraphs’ inherent resilience to failures and adaptability to topological changes.
Original languageEnglish
Pages (from-to)80-95
JournalTheoretical Computer Science
Volume355
Issue number1
DOIs
Publication statusPublished - 6 Apr 2006

Fingerprint

Information dissemination
Spanning Subgraph
Complex networks
Complex Networks
Stretching
Heuristics
Bandwidth
Information Dissemination
Resilience
Vertex of a graph
Adaptability
Mathematical Analysis
Random Graphs
Path
Requirements
Simulation

Cite this

Local heuristics and the emergence of spanning subgraphs in complex networks. / Stauffer, A O; Barbosa, Valmir C.

In: Theoretical Computer Science, Vol. 355, No. 1, 06.04.2006, p. 80-95.

Research output: Contribution to journalArticle

@article{6c113b62d8974f26ba8c2dca394eed36,
title = "Local heuristics and the emergence of spanning subgraphs in complex networks",
abstract = "We study the use of local heuristics to determine spanning subgraphs for use in the dissemination of information in complex networks. We introduce two different heuristics and analyze their behavior in giving rise to spanning subgraphs that perform well in terms of allowing every node of the network to be reached, of requiring relatively few messages and small node bandwidth for information dissemination, and also of stretching paths with respect to the underlying network only modestly. We contribute a detailed mathematical analysis of one of the heuristics and provide extensive simulation results on random graphs for both of them. These results indicate that, within certain limits, spanning subgraphs are indeed expected to emerge that perform well in respect to all requirements. We also discuss the spanning subgraphs’ inherent resilience to failures and adaptability to topological changes.",
author = "Stauffer, {A O} and Barbosa, {Valmir C.}",
year = "2006",
month = "4",
day = "6",
doi = "10.1016/j.tcs.2005.12.007",
language = "English",
volume = "355",
pages = "80--95",
journal = "Theoretical Computer Science",
issn = "0304-3975",
publisher = "Elsevier",
number = "1",

}

TY - JOUR

T1 - Local heuristics and the emergence of spanning subgraphs in complex networks

AU - Stauffer, A O

AU - Barbosa, Valmir C.

PY - 2006/4/6

Y1 - 2006/4/6

N2 - We study the use of local heuristics to determine spanning subgraphs for use in the dissemination of information in complex networks. We introduce two different heuristics and analyze their behavior in giving rise to spanning subgraphs that perform well in terms of allowing every node of the network to be reached, of requiring relatively few messages and small node bandwidth for information dissemination, and also of stretching paths with respect to the underlying network only modestly. We contribute a detailed mathematical analysis of one of the heuristics and provide extensive simulation results on random graphs for both of them. These results indicate that, within certain limits, spanning subgraphs are indeed expected to emerge that perform well in respect to all requirements. We also discuss the spanning subgraphs’ inherent resilience to failures and adaptability to topological changes.

AB - We study the use of local heuristics to determine spanning subgraphs for use in the dissemination of information in complex networks. We introduce two different heuristics and analyze their behavior in giving rise to spanning subgraphs that perform well in terms of allowing every node of the network to be reached, of requiring relatively few messages and small node bandwidth for information dissemination, and also of stretching paths with respect to the underlying network only modestly. We contribute a detailed mathematical analysis of one of the heuristics and provide extensive simulation results on random graphs for both of them. These results indicate that, within certain limits, spanning subgraphs are indeed expected to emerge that perform well in respect to all requirements. We also discuss the spanning subgraphs’ inherent resilience to failures and adaptability to topological changes.

UR - http://dx.doi.org/10.1016/j.tcs.2005.12.007

UR - http://arxiv.org/abs/cs/0411090v1

U2 - 10.1016/j.tcs.2005.12.007

DO - 10.1016/j.tcs.2005.12.007

M3 - Article

VL - 355

SP - 80

EP - 95

JO - Theoretical Computer Science

JF - Theoretical Computer Science

SN - 0304-3975

IS - 1

ER -