Emergence of scale-free networks via random walk
Giulio Iacobelli (IM-UFRJ)

Power-law degree distributions commonly arise in real-world networks such as the World Wide Web, social networks, and citation networks. By assigning non-negligible probability to the occurrence of high-degree nodes, these distributions explain the emergence of hubs—highly connected nodes such as popular web pages. To account for this phenomenon, Barabási and Albert introduced a random network growth model based on preferential attachment, where new vertices are more likely to connect to existing vertices with higher degree. However, this mechanism relies on global knowledge of the network, particularly the degrees of all existing nodes, an assumption that may not always be realistic in practical settings. We propose a local alternative: the Tree Builder Random Walk (TBRW) model. In TBRW, the network is dynamically built by a random walk that, at each time step $n$, adds a leaf to its current position with probability $p_n$, then moves to a uniformly chosen neighbor in the (possibly modified) network. Crucially, the walker requires only local information, namely, its immediate neighbors. We show that for $p_n= n^{- \gamma}$, with $\gamma\in (2/3,1]$, the TBRW at its growth times, can be coupled to be identical to the Barabási-Albert model (BA). This coupling also implies that many properties known for the BA model --beyond just the power-law degree distribution-- can be transferred to the TBRW.