InterJournal Complex Systems, 1220 Status: Accepted Manuscript Number: [1220] Submission Date: 2004 Constructing Scale-Free Networks by a Matrix Stability Criterium
Author(s): Markus Brede ,John Finnigan

Subject(s): CX.18

Category:

Abstract:

Scale-free (SF) networks have been found to occur in very diverse contexts. Examples are found in artificially created systems such as the WWW, transport flow systems or social networks, and also in many biological regulatory networks -- e.g., metabolic, protein folding and genetic networks. It is this striking universality which makes one look for widely applicable general principles leading to the formation of SF networks. In principle, two processes for the formation of SF networks are known: preferential attachment (and modifications thereof) and optimization with respect to diameter and link number. In this paper we propose a potentially third mechanism: Evolving SF networks as interaction networks of systems which are distinguished by their stability to perturbation away from equilibrium. The model we propose thus for the first time relates SF networks to stability properties of the underlying dynamical system. Consider a model network where links can either be positive or negative. A positive link between node $i$ and node $j$ means that the population associated with $i$ promotes the growth of $j$'s population. Conversely, a negative link means suppression of the growth of $j$ by $i$. The model evolves by two major steps: (i) attachment of new nodes, which each form a positive and a negative in- and out-link to randomly selected nodes from the old network and (ii) acceptance or rejection of the resulting new network configurations according to their stability. Stability is measured by the size of the largest eigenvalue of the adjacency matrix. Networks generated in this way exhibit a SF topology with exponents $\gamma$ in the range between $-2$ and $-3$. We extend the model to weighted directed networks, now randomly drawing link strength in step (i) uniformly from the intervals $[-1,0)$ (for positive links) and $(0,1]$ (for negative links). We report power law behaviour of the link strength distribution of the weighted graphs in the SF regime, favouring weak links.