Simon model

Motivation

Aiming to account for the wide range of empirical distributions following a power-law, Herbert SimonSimon, H. A., 1955, Biometrika 42, 425.] proposed a class of stochastic models that results in a power-law distribution function. It models the dynamics of a systemof elements with associated counters (e.g., words and their frequenciesin texts, or nodes in a network and their connectivity $k$). In this model thedynamics of the system is based on constant growth via additionof new elements (new instances of words) as well as incrementingthe counters (new occurrences of a word) at a rate proportionalto their current values.

Description

To model this type of network growth as described above, Bornholdt and EbelBornholdt, S. and H. Ebel, Phys. Rev. E 64 (2001) 035104(R). ] considered anetwork with $n$ nodes, and each node with connectivities $k\_i$, $i\; =\; 1\; ldots\; n$. These nodesform classes $[k]$ of $f(k)$ nodes with identical connectivity $k$.Repeat the following steps:

(i) With probability $alpha$ add a new nodeand attach a link to it from an arbitrarily chosen node.

(ii) With probability $1-alpha$ add one link from an arbitrary node to a node$j$ of class $[k]$ chosen with probability$P\_\{new\; link\; to\; class\; [k]\; \}\; propto\; k\; f(k)$.

For this stochastic process, Simon found a stationary solutionexhibiting power-law scaling,$P(k)\; propto\; k^\{-\; gamma\}$, with exponent$gamma\; =\; 1\; +\; frac\{1\}\{1-\; alpha\}.$

Properties

(i) Barabási-Albert (BA) model can be mapped to the subclass $alpha=\; 1/2$ of Simon's model,when using the simpler probability for a node beingconnected to another node $i$ with connectivity $k\_i$$P\_\{new\; link\; to\; i\}\; propto\; k\_i$ (same as the preferential attachment at BA Model). In other words, the Simon model describes a general class of stochastic processes that can result in a scale-free network, appropriate to capture Pareto and Zipf's laws.

(ii) The only free parameter of the model $alpha$ reflects the relativegrowth of number of nodes versus the number of links.In general $alpha$ has small values; therefore, the scaling exponents can be predicted to be $gammaapprox\; 2$. For instance, Bornholdt and EbelBornholdt, S. and H. Ebel, Phys. Rev. E 64 (2001) 035104(R). ] studied the linking dynamics of World Wide Web, and predicted the scaling exponent as $gamma\; approx\; 2.1$, which was consistent with observation.

(iii) The interest in the scale-free model comes from its ability to describe the topology of complex networks. The Simon model does not have an underlying network structure, as it was designed to describe events whose frequency follows a power-law. Thus network measures going beyond the degree distribution suchas the average path length, [http://austria.phys.nd.edu/netwiki/index.php/Graph_Spectra spectral properties] , and clustering coefficient, cannot be obtained from this mapping.

The Simon model is related to generalized scale-free models with growth and preferential attachment properties. For more reference, see Barabási, A.-L., and R. Albert, Statistical mechanics of complex networks, Reviews of Modern Physics, Vol 74, page 47-97, 2002.] Amaral, L. A. N., A. Scala, M. Barthelemy, and H. E. Stanley, 2000, Proc. Natl. Acad. Sci. U.S.A. 97, 11149.] .

References