Motivation

Aiming to account for the wide range of empirical distributions

Frequency distribution

In statistics, a frequency distribution is an arrangement of the values that one or more variables take in a sample. Each entry in the table contains the frequency or count of the occurrences of values within a particular group or interval, and in this way, the table summarizes the distribution of...

 following a power-law, Herbert Simon proposed a class of stochastic models that results in a power-law distribution function. It models the dynamics of a system
of elements with associated counters (e.g., words and their frequencies
in texts, or nodes in a network and their connectivity ). In this model the
dynamics of the system is based on constant growth via addition
of new elements (new instances of words) as well as incrementing
the counters (new occurrences of a word) at a rate proportional
to their current values.

Description

To model this type of network growth as described above, Bornholdt and Ebel considered a
network with nodes, and each node with connectivities , . These nodes
form classes of nodes with identical connectivity .
Repeat the following steps:

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

(ii) With probability add one link from an arbitrary node to a node
of class chosen with probability
.

For this stochastic process, Simon found a stationary solution
exhibiting power-law scaling,
, with exponent

Properties

(i) Barabási-Albert (BA) model can be mapped to the subclass of Simon's model,
when using the simpler probability for a node being
connected to another node with connectivity
(same as the preferential attachment at BA Model

BA model

The Barabási–Albert model is an algorithm for generating random scale-free networks using a preferential attachment mechanism. Scale-free networks are widely observed in natural and man-made systems, including the Internet, the world wide web, citation networks, and some social...

). In other words, the Simon model describes a general class of stochastic processes that can result in a scale-free network

Scale-free network

A scale-free network is a network whose degree distribution follows a power law, at least asymptotically. That is, the fraction P of nodes in the network having k connections to other nodes goes for large values of k as...

, appropriate to capture Pareto and Zipf's laws.

(ii) The only free parameter of the model reflects the relative
growth of number of nodes versus the number of links.
In general has small values; therefore, the scaling exponents can be predicted to be . For instance, Bornholdt and Ebel studied the linking dynamics of World Wide Web, and predicted the scaling exponent as , 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

Degree distribution

In the study of graphs and networks, the degree of a node in a network is the number of connections it has to other nodes and the degree distribution is the probability distribution of these degrees over the whole network.-Definition:...

 such
as the average path length

Average path length

Average path length is a concept in network topology that is defined as the average number of steps along the shortest paths for all possible pairs of network nodes...

, spectral properties, and clustering coefficient

Clustering coefficient

In graph theory, a clustering coefficient is a measure of degree to which nodes in a graph tend to cluster together. Evidence suggests that in most real-world networks, and in particular social networks, nodes tend to create tightly knit groups characterised by a relatively high density of ties...

, cannot be obtained from this mapping.

The Simon model is related to generalized scale-free model

Generalized scale-free model

There has been a burst of activity in the modeling of scale-free complex networks. The recipe of Barabási and Albert has been followed by several variations and generalizations and the revamping of previous mathematicalworks...

s with growth and preferential attachment properties. For more reference, see .