Stability in the Self-Organized Evolution of Networks

Madeleine Theile*, Thomas Jansen

*Corresponding author for this work

Research output: Contribution to journalArticlepeer-review

1 Citation (SciVal)

Abstract

The modeling and analysis of large networks of autonomous agents is an important topic with applications in many different disciplines. One way of modeling the development of such networks is by means of an evolutionary process. The autonomous and selfishly acting agents are randomly chosen to become active according to an underlying probability distribution. They may apply some kind of local mutation operator to the network and decide about accepting these changes via some fitness-based selection whereas the fitness models the agent's preferences. This general framework for the self-organized evolution of networks can be instantiated in many different ways. For interesting instances, one would like to know whether stable topologies eventually evolve and how long this process may take. Here, known results for an instantiation based on random spanning trees and a fitness-based selection according to global graph centrality measures are improved. Moreover, a more natural and local fitness-based selection using only the information on nearest neighbors is presented and analyzed with respect to the expected time needed to reach a stable state.

Original languageEnglish
Pages (from-to)147-169
Number of pages23
JournalAlgorithmica
Volume57
Issue number1
Early online date25 Oct 2008
DOIs
Publication statusPublished - May 2010
EventAnnual Conference of Genetic and Evolutionary Computation Conference - London
Duration: 07 Jul 200711 Jul 2007

Keywords

  • TREES
  • Evolutionary algorithms
  • WIENER INDEX
  • Runtime analysis
  • Stability
  • Self-organization

Fingerprint

Dive into the research topics of 'Stability in the Self-Organized Evolution of Networks'. Together they form a unique fingerprint.

Cite this