Popularity versus similarity in growing networks

By Fragkiskos Papadopoulos, Marián Boguñá, Dmitri V. Krioukov. Nature, 2011

625 citations recorded by the source corpus.

The principle that ‘popularity is attractive’ underlies preferential attachment, which is a common explanation for the emergence of scaling in growing networks. If new connections are made preferentially to more popular nodes, then the resulting distribution of the number of connections possessed by nodes follows power laws, as observed in many real networks. Preferential attachment has been directly validated for some real networks (including the Internet), and can be a consequence of different underlying processes based on node fitness, ranking, optimization, random walks or duplication. Here we show that popularity is just one dimension of attractiveness; another dimension is similarity. We develop a framework in which new connections optimize certain trade-offs between popularity and similarity, instead of simply preferring popular nodes. The framework has a geometric interpretation in which popularity preference emerges from local optimization. As opposed to preferential attachment, our optimization framework accurately describes the large-scale evolution of technological (the Internet), social (trust relationships between people) and biological (Escherichia coli metabolic) networks, predicting the probability of new links with high precision. The framework that we have developed can thus be used for predicting new links in evolving networks, and provides a different perspective on preferential attachment as an emergent phenomenon.

Subfields: Ecology, Evolution, Behavior and Systematics, Sociology and Political Science, Statistical and Nonlinear Physics

View Paper: https://www.semanticscholar.org/paper/439bc87197a15214c207a17b3b09568c900b9470

How researchers see this paper

The researchers whose trusted networks rank it highest, strongest advocate first. Every researcher gets a different order.

In Ecology, Evolution, Behavior and Systematics

In Sociology and Political Science

In Statistical and Nonlinear Physics

Citations in the corpus

The Geometry of Culture: Analyzing the Meanings of Class through Word Embeddings (2018, background): “Social networks, power grids and the internet, with “nodes” of highly unequal degree distribution or number of connections, are often embedded in hyperbolic spaces having constant, negative curvature (Krioukov et al. 2010; Papadopoulos et al. 2012; Cvetkovski and Crovella 2009; Alanis-Lobato, Mier, ”
The science of science: from the perspective of complex systems (2017, background): “Alternatively, the property of rich triangles in citation networks can bemodeled using a geometric graph [113] that is similar to the popularity–similaritymodel [114].”
Growing Homophilic Networks Are Natural Navigable Small Worlds (2015, positive): “[17], which is a growing model in a hyperbolic space, adequately describes evolution of many scale-free real networks.”
From link-prediction in brain connectomes and protein interactomes to the local-community-paradigm in complex networks (2013, background): “This paradigm, named preferential attachment (PA) 4 , together with the underlying idea of popularity 6 is just one facet of node attractiveness in growing networks, another important aspect being similarity 6 .”
Navigable networks as Nash equilibria of navigation games (2014, methodology): “The model in [78] has been validated against long histories of growth of several real networks, predicting their growth dynamics with a remarkable precision.”
Mixed Dimension Embeddings with Application to Memory-Efficient Recommendation Systems (2019, background): “In networks science, this phenomena is referred to as popularity [14, 39], a terminology we adopt here.”
Hyperbolic Graph Neural Networks (2019, background): “lex networks. Typical properties such as heterogeneous degree distributions and strong clustering can often be explained by assuming an underlying hierarchy which is well captured in hyperbolic space [28, 35]. These insights led, for instance, to hyperbolic geometric graph models, which allow for th”
Suicide Ideation Detection via Social and Temporal User Representations using Hyperbolic Learning (2021, background): “a better representation of the underlying scale-free nature of social networks (Krioukov et al., 2010; Papadopoulos et al., 2012).”