Giulio Iacobelli (Universidade Federal do Rio de Janeiro, Brazil)
Growing Networks with Random Walks
Network growth and evolution is a fundamental theme that has puzzled scientists for the past decades. A number of models have been proposed to capture important properties of real networks, the most famous being the model of Barabási-Albert (BA) which embodies the principle of preferential attachment. A recognized drawback of most proposed network growth models is the assumption of global information about the network. For example, the BA model requires the knowledge of the degree of every node in the network to randomly choose where a new node will be connected.
In this work we propose and study a network growth model that is purely local. The model is based on a continuously moving random walk that after s steps connects a new node to its current location. Through extensive simulations and theoretical arguments, we analyze the behavior of the model finding a fundamental dependency on the parity of s, where networks with either exponential or heavy-tailed degree distribution can emerge. As s increases, parity dependency diminishes and the model recovers the degree distribution of BA preferential attachment model. The proposed purely local model indicates that networks can grow to exhibit interesting properties even in the absence of any global information.
Joint work with Bernardo Amorim, Daniel Figueiredo, and Giovanni Neglia.