Evolution of networks

Nina Lehmann

Abstract

Real-world networks are often capable of changing the network's structure according to environmental changes. In this talk I want to explore how a network of intelligent vertices with a local view on a network can reduced the diameter of their network to a given value by re-wiring their edges. Of course, this task is not very interesting if there is a central coordinator that gives advice how to reduce the diameter best. But what kind of re-wiring rules have to be given to the vertices such that they can reduce the diameter of their network in a decentralized fashion and how long will it take until the reduced diameter is obtained? As a further constraint we require that no vertex will rewire any edge that is not of personal use to it, i.e., the vertices are egoistic.

We could show that there are two rules that will reduce the diameter of a tree to a given value, obeying the above given constraints, where one rule has an expected exponential