Evolving network

One concern with the BA model is that the degree distributions of each nodes experience strong positive feedback whereby the earliest nodes with high degree distributions continue to dominate the network indefinitely. However, this can be alleviated by introducing a fitness for each node, which modifies the probability of new links being created with that node or even of links to that node being removed.[4]

In order to preserve the preferential attachment from the BA model, this fitness is then multiplied by the preferential attachment based on degree distribution to give the true probability that a link is created which connects to node i.

${\displaystyle \Pi (k_{i})={\frac {\eta _{i}k_{i}}{\displaystyle \sum _{j}\eta _{j}k_{j}}},}$

Where ${\displaystyle \eta }$ is the fitness, which may also depend on time. A decay of fitness with respect to time may occur and can be formalized by

${\displaystyle \Pi (k_{i})\propto k_{i}(t-t_{i})^{-\nu },}$

where ${\displaystyle \gamma }$ increases with ${\displaystyle \nu .}$

Further complications arise because nodes may be removed from the network with some probability. Additionally, existing links may be destroyed and new links between existing nodes may be created. The probability of these actions occurring may depend on time and may also be related to the node's fitness. Probabilities can be assigned to these events by studying the characteristics of the network in question in order to grow a model network with identical properties. This growth would take place with one of the following actions occurring at each time step:

Prob p: add an internal link.

Prob q: delete a link.

Prob r: delete a node.

Prob 1-p-q-r: add a node.

In networked systems where competitive decision making takes place, game theory is often used to model system dynamics, and convergence towards equilibria can be considered as a driver of topological evolution. For example, Kasthurirathna and Piraveenan [5] have shown that when individuals in a system display varying levels of rationality, improving the overall system rationality might be an evolutionary reason for the emergence of scale-free networks. They demonstrated this by applying evolutionary pressure on an initially random network which simulates a range of classic games, so that the network converges towards Nash equilibria while being allowed to re-wire. The networks become increasingly scale-free during this process.

The most common way to view evolving networks is by considering them as successive static networks. This could be conceptualized as the individual still images which compose a motion picture. Many simple parameters exist to describe a static network (number of nodes, edges, path length, connected components), or to describe specific nodes in the graph such as the number of links or the clustering coefficient. These properties can then individually be studied as a time series using signal processing notions.[6] For example, we can track the number of links established to a server per minute by looking at the successive snapshots of the network and counting these links in each snapshot.

Unfortunately, the analogy of snapshots to a motion picture also reveals the main difficulty with this approach: the time steps employed are very rarely suggested by the network and are instead arbitrary. Using extremely small time steps between each snapshot preserves resolution, but may actually obscure wider trends which only become visible over longer timescales. Conversely, using larger timescales loses the temporal order of events within each snapshot. Therefore, it may be difficult to find the appropriate timescale for dividing the evolution of a network into static snapshots.

It may be important to look at properties which cannot be directly observed by treating evolving networks as a sequence of snapshots, such as the duration of contacts between nodes[7] Other similar properties can be defined and then it is possible to instead track these properties through the evolution of a network and visualize them directly.

Another issue with using successive snapshots is that only slight changes in network topology can have large effects on the outcome of algorithms designed to find communities. Therefore, it is necessary to use a non classical definition of communities which permits following the evolution of the community through a set of rules such as birth, death, merge, split, growth, and contraction.[8][9]