Empirical extraction of mechanisms underlying real world network generation

The generation mechanisms of real world networks have been described using multiple models. The mathematical features of these models are usually extrapolated from statistical properties of a snapshot of these networks. We here propose an alternative method based on direct measurement of a sequence of consecutive snapshots to uncover the dynamics underlying real world generation. We assume that the probability of adding a node or an edge depends only on local features surrounding the newly added node/edge, and directly measure the contribution of these features to the node/edge addition probability. These measurements are performed using newly defined N-node local structures. Each N-node local structure represents the configuration of edges surrounding a newly added edge. The N-node local structure measurements reproduce for some networks the now classical addition of edges between high degree node mechanisms. It also provides quantitative estimates of more complex mechanisms driving other networks' evolution, such as the effect of common first and second neighbors. This new methodology reveals the relative importance of different generation mechanisms. We show, for example, that the main mechanism driving hyperlink addition between two websites is the existence of a third website linking to both the source and the target of the new hyperlink. (C) 2010 Elsevier B.V. All rights reserved.