  We study the evolution of cooperation in the prisoner's dilemma game, whereby
a coevolutionary rule is introduced that molds the random topology of the
interaction network in two ways. First, existing links are deleted whenever a
player adopts a new strategy or its degree exceeds a threshold value, and
second, new links are added randomly after a given number of game iterations.
These coevolutionary processes correspond to the generic formation of new and
deletion of existing links that, especially in human societies, appear
frequently as a consequence of ongoing socialization, change of lifestyle or
death. Due to the counteraction of deletions and additions of links the initial
heterogeneity of the interaction network is qualitatively preserved, and thus
cannot be held responsible for the observed promotion of cooperation. Indeed,
the coevolutionary rule evokes the spontaneous emergence of a powerful
multilevel selection mechanism, which despite of the sustained random topology
of the evolving network, maintains cooperation across the whole span of
defection temptation values.
