Scale-free network growth by ranking
arXiv:cond-mat/0602081 · doi:10.1103/PhysRevLett.96.218701
Abstract
Network growth is currently explained through mechanisms that rely on node prestige measures, such as degree or fitness. In many real networks those who create and connect nodes do not know the prestige values of existing nodes, but only their ranking by prestige. We propose a criterion of network growth that explicitly relies on the ranking of the nodes according to any prestige measure, be it topological or not. The resulting network has a scale-free degree distribution when the probability to link a target node is any power law function of its rank, even when one has only partial information of node ranks. Our criterion may explain the frequency and robustness of scale-free degree distributions in real networks, as illustrated by the special case of the Web graph.
4 pages, 2 figures. We extended the model to account for ranking by arbitrarily distributed fitness. Final version to appear on Physical Review Letters
References in corpus (14)
- Emergence of scaling in random networks
- Statistical mechanics of complex networks
- The structure and function of complex networks
- Error and attack tolerance of complex networks
- Epidemic spreading in scale-free networks
- Evolution of networks
- Structure of Growing Networks: Exact Solution of the Barabasi--Albert's Model
- Universal Behavior of Load Distribution in Scale-free Networks
- Search in Power-Law Networks
- Connectivity of Growing Random Networks
- Class of correlated random networks with hidden variables
- Truncation of power law behavior in "scale-free" network models due to information filtering
- The egalitarian effect of search engines
- Statistics of Lead Changes in Popularity-Driven Systems
Cited by in corpus (44)
- Activity driven modeling of time varying networks
- Popularity versus Similarity in Growing Networks
- Finding Scientific Gems with Google
- Weighted network modules
- Characterizing and modeling the dynamics of online popularity
- Ranking in evolving complex networks
- Structural and Dynamical Patterns on Online Social Networks: the Spanish May 15th Movement as a case study
- How algorithmic popularity bias hinders or promotes quality
- The egalitarian effect of search engines
- A Simple Generative Model of Collective Online Behaviour
- Promise and Pitfalls of Extending Google's PageRank Algorithm to Citation Networks
- Pair approximation for the q-voter model with independence on complex networks
- Tail universalities in rank distributions as an algebraic problem: the beta-like function
- Political audience diversity and news reliability in algorithmic ranking
- Evolution of the digital society reveals balance between viral and mass media influence
- Effect of node deleting on network structure
- Preferential attachment mechanism of complex network growth: "rich-gets-richer" or "fit-gets-richer"?
- An analysis of the graph processing landscape
- Growing Scale-free Networks by a Mediation-Driven Attachment Rule
- Degree Distribution, Rank-size Distribution, and Leadership Persistence in Mediation-Driven Attachment Networks
- Competition between global and local online social networks
- The long-term impact of ranking algorithms in growing networks
- Use of Astronomical Literature - A Report on Usage Patterns
- Digital Ecology: Coexistence and Domination among Interacting Networks
- Remembering what we like: Toward an agent-based model of Web traffic
- Diffusion on hierarchical systems of weakly-coupled networks
- Massive Multi-Agent Data-Driven Simulations of the GitHub Ecosystem
- Attention Inequality in Social Media
- Preferential attachment with partial information
- Heterogeneity shapes groups growth in social online communities
- Large deviations for the degree structure in preferential attachment schemes
- Likelihood-based approach to discriminate mixtures of network models that vary in time
- Agents, Bookmarks and Clicks: A topical model of Web traffic
- Reconciling the Quality vs Popularity Dichotomy in Online Cultural Markets
- Rank-based model for weighted network with hierarchical organization and disassortative mixing
- Automatic Discovery of Families of Network Generative Processes
- Rank-dependent deactivation in network evolution
- Measuring Equality and Hierarchical Mobility on Abstract Complex Networks
- VeilGraph: Streaming Graph Approximations
- Geometric protean graphs
- Priority Attachment: a Comprehensive Mechanism for Generating Networks
- Rank-based attachment leads to power law graphs
- Hot-Get-Richer Network Growth Model
- Network Evolution by Relevance and Importance Preferential Attachment