Popularity versus Similarity in Growing Networks

Abstract

Popularity is attractive -- this is the formula underlying preferential attachment, a popular 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 that nodes have follows power laws observed in many real networks. Preferential attachment has been directly validated for some real networks, including the Internet. Preferential attachment can also 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 where new connections, instead of preferring popular nodes, optimize certain trade-offs between popularity and similarity. The framework admits a geometric interpretation, in which popularity preference emerges from local optimization. As opposed to preferential attachment, the optimization framework accurately describes large-scale evolution of technological (Internet), social (web of trust), and biological (E.coli metabolic) networks, predicting the probability of new links in them with a remarkable precision. The developed framework can thus be used for predicting new links in evolving networks, and provides a different perspective on preferential attachment as an emergent phenomenon.

References in corpus (26)

• Emergence of scaling in random networks
• Hierarchical organization of modularity in metabolic networks
• Hierarchical structure and the prediction of missing links in networks
• How Popular is Your Paper? An Empirical Study of the Citation Distribution
• Dynamical and correlation properties of the Internet
• Structure of Growing Networks: Exact Solution of the Barabasi--Albert's Model
• Connectivity of Growing Random Networks
• Hyperbolic Geometry of Complex Networks
• Identity and Search in Social Networks
• Bose-Einstein condensation in complex networks
• Measuring preferential attachment for evolving networks
• Growing networks with local rules: preferential attachment, clustering hierarchy and degree correlations
• Sustaining the Internet with Hyperbolic Mapping
• Class of correlated random networks with hidden variables
• Highly clustered scale-free networks
• Pattern Detection in Complex Networks: Correlation Profile of the Internet
• Graph Evolution: Densification and Shrinking Diameters
• Generic scale of the "scale-free" growing networks
• The Simultaneous Evolution of Author and Paper Networks
• Greedy Forwarding in Dynamic Scale-Free Networks Embedded in Hyperbolic Metric Spaces
• Scale-free network growth by ranking
• Tuning clustering in random networks with arbitrary degree distributions
• Topology and correlations in structured scale-free networks
• Preferential attachment in growing spatial networks
• Optimization in Networks
• WWW and Internet models from 1955 till our days and the ``popularity is attractive'' principle

Cited by in corpus (195)

• The Matthew effect in empirical data
• Evaluating Link Prediction Methods
• Origins of power-law degree distribution in the heterogeneity of human activity in social networks
• Network Geometry
• Ranking in evolving complex networks
• Generalized network structures: The configuration model and the canonical ensemble of simplicial complexes
• Machine learning meets network science: dimensionality reduction for fast and efficient embedding of networks in the hyperbolic space
• Quantifying randomness in real networks
• Emergent Hyperbolic Network Geometry
• Network Mapping by Replaying Hyperbolic Growth
• Network geometry with flavor: from complexity to quantum geometry
• Modeling human dynamics of face-to-face interaction networks
• Hidden geometric correlations in real multiplex networks
• Visibility of minorities in social networks
• Progresses and Challenges in Link Prediction
• Multiscale unfolding of real networks by geometric renormalization
• Network Cosmology
• Interdisciplinary and physics challenges of Network Theory
• Emergent Complex Network Geometry
• Correlation dimension of complex networks
• Emergence of Soft Communities from Geometric Preferential Attachment
• A nonuniform popularity-similarity optimization (nPSO) model to efficiently generate realistic complex networks with communities
• Geomstats: A Python Package for Riemannian Geometry in Machine Learning
• The hidden geometry of weighted complex networks
• Geometric renormalization unravels self-similarity of the multiscale human connectome
• Network Geometry Inference using Common Neighbors
• True scale-free networks hidden by finite size effects
• An Experimental Investigation of Hyperbolic Routing with a Smart Forwarding Plane in NDN
• Navigable Networks as Nash Equilibria of Navigation Games
• Division of labor, skill complementarity, and heterophily in socioeconomic networks
• Diversity of information pathways drives scaling and sparsity in real-world networks
• Growing complex network of citations of scientific papers -- measurements and modeling
• Deciphering the global organization of clustering in real complex networks
• Complex Quantum Network Geometries: Evolution and Phase Transitions
• Geometric correlations mitigate the extreme vulnerability of multiplex networks against targeted attacks
• Measuring robustness of community structure in complex networks
• Scale-free networks with exponent one
• Metric clusters in evolutionary games on scale-free networks
• Hyperbolic Graph Generator
• Diffusion geometry unravels the emergence of functional clusters in collective phenomena
• Accelerating Recommendation System Training by Leveraging Popular Choices
• Characterizing the analogy between hyperbolic embedding and community structure of complex networks
• Network Geometry and Complexity
• Fractional Dynamics of Network Growth Constrained by aging Node Interactions
• Complex network view of evolving manifolds
• Co-evolutionary dynamics in social networks: A case study of Twitter
• Link prediction with hyperbolic geometry
• Modeling Structure and Resilience of the Dark Network
• Effective epidemic containment strategy in hypergraphs
• GLEE: Geometric Laplacian Eigenmap Embedding
• A vertex similarity index for better personalized recommendation
• ACE-HGNN: Adaptive Curvature Exploration Hyperbolic Graph Neural Network
• Entropy distribution and condensation in random networks with a given degree distribution
• Soft communities in similarity space
• Evolution of the digital society reveals balance between viral and mass media influence
• Reconstructing networks
• Latent geometry of bipartite networks
• Geohyperbolic Routing and Addressing Schemes
• Evolution of the Internet k-dense structure
• Structure controllability of complex network based on preferential matching
• A coevolving model based on preferential triadic closure for social media networks
• The inherent community structure of hyperbolic networks
• Embedding Graphs in Lorentzian Spacetime
• Brand effect versus competitiveness in hypernetworks
• Preferential attachment mechanism of complex network growth: "rich-gets-richer" or "fit-gets-richer"?
• Statistical validation of high-dimensional models of growing networks
• Diffusion geometry of multiplex and interdependent systems
• Ex-ante measure of patent quality reveals intrinsic fitness for citation-network growth
• Competition between global and local online social networks
• Finding shortest and nearly shortest path nodes in large substantially incomplete networks
• Hyperbolic Geometric Graph Representation Learning for Hierarchy-imbalance Node Classification
• Analysis of English free association network reveals mechanisms of efficient solution of Remote Association Tests
• Scaling theory of fractal complex networks
• From sparse to dense and from assortative to disassortative in online social networks
• Geometric explanation of the rich-club phenomenon in complex networks
• Emergence of geometric Turing patterns in complex networks
• Duality between equilibrium and growing networks
• New Phenomena in Large-Scale Internet Traffic
• Similarity forces and recurrent components in human face-to-face interaction networks
• Percolation and the effective structure of complex networks
• A geometry-induced topological phase transition in random graphs
• Temporal and structural heterogeneities emerging in adaptive temporal networks
• Link Prediction via Graph Attention Network
• Random hyperbolic graphs in $d+1$ dimensions
• Model-independent methods for embedding directed networks into Euclidean and hyperbolic spaces
• Collective navigation of complex networks: Participatory greedy routing
• Learning epidemic threshold in complex networks by Convolutional Neural Network
• Digital Ecology: Coexistence and Domination among Interacting Networks
• Link persistence and conditional distances in multiplex networks
• Spatial effects in real networks: measures, null models, and applications
• Assortative and disassortative mixing investigated using the spectra of graphs
• Hyperbolic Graph Attention Network
• k-core structure of real multiplex networks
• Minimum curvilinear automata with similarity attachment for network embedding and link prediction in the hyperbolic space
• Local-ring network automata and the impact of hyperbolic geometry in complex network link-prediction
• Scale-invariant geometric random graphs
• Identification and modeling of discoverers in online social systems
• Growing hyperbolic networks beyond two dimensions: the generalised popularity-similarity optimisation model
• Dynamic Hidden-Variable Network Models
• Network Renormalization
• Optimisation of the coalescent hyperbolic embedding of complex networks
• Pareto optimality in multilayer network growth
• Highly Dispersed Networks Generated by Enhanced Redirection
• Latent geometry and dynamics of proximity networks
• Finite-size scaling of geometric renormalization flows in complex networks
• Complex networks as an emerging property of hierarchical preferential attachment
• Highly Dispersed Networks
• Impact of noise and damage on collective dynamics of scale-free neuronal networks
• Stylized facts in social networks: Community-based static modeling
• Maximally modular structure of growing hyperbolic networks
• Analytical estimation of the correlation dimension of integer lattices
• Zoo Guide to Network Embedding
• Cosmological networks
• Growing homophilic networks are natural navigable small worlds
• Complex systems: features, similarity and connectivity
• Hamiltonian Dynamics of Preferential Attachment
• Detecting network communities beyond assortativity-related attributes
• Fundamental dynamics of popularity-similarity trajectories in real networks
• A Latent Parameter Node-Centric Model for Spatial Networks
• Sampling networks by nodal attributes
• Explaining the emergence of complex networks through log-normal fitness in a Euclidean node similarity space
• Duality between preferential attachment and static random networks on hyperbolic spaces
• How does homophily shape the topology of a dynamic network?
• Influence Activation Model: A New Perspective in Social Influence Analysis and Social Network Evolution
• How Complex Contagions Spread Quickly in the Preferential Attachment Model and Other Time-Evolving Networks
• Hyperbolic Variational Graph Neural Network for Modeling Dynamic Graphs
• The Fitness-Corrected Block Model, or how to create maximum-entropy data-driven spatial social networks
• Effects of homophily and heterophily on preferred-degree networks: mean-field analysis and overwhelming transition
• Topological estimation of the latent geometry of a complex network
• Geometric evolution of complex networks
• Greedy routing optimisation in hyperbolic networks
• A novel method of generating tunable underlying network topologies for social simulation
• Model-free hidden geometry of complex networks
• Hyperbolic Mapping of Human Proximity Networks
• Rich-clubness test: how to determine whether a complex network has or doesn't have a rich-club?
• Navigability of Random Geometric Graphs in the Universe and Other Spacetimes
• Real-Time Visualization in Non-Isotropic Geometries
• Hyperbolic triangulations and discrete random graphs
• Strength of minority ties: the role of homophily and group composition in a weighted social network
• Automatic Discovery of Families of Network Generative Processes
• Social Centralization and Semantic Collapse: Hyperbolic Embeddings of Networks and Text
• Large-Margin Classification in Hyperbolic Space
• Geometric detection of hierarchical backbones in real networks
• Disagreement and fragmentation in growing groups
• The co-evolution of brand effect and competitiveness in evolving networks
• Social Connection Induces Cultural Contraction: Evidence from Hyperbolic Embeddings of Social and Semantic Networks
• Angular separability of data clusters or network communities in geometrical space and its relevance to hyperbolic embedding
• Improving link prediction accuracy of network embedding algorithms via rich node attribute information
• When Labels Fall Short: Property Graph Simulation via Blending of Network Structure and Vertex Attributes
• DeepHGCN: Toward Deeper Hyperbolic Graph Convolutional Networks
• Community detection in hypergraphs through hyperedge percolation
• Trust based attachment
• Stability of similarity measurements for bipartite networks
• Complex Networks in the Framework of Nonassociative Geometry
• Far-reaching consequences of trait preferences for animal social network structure and function
• Latent Geometry Inspired Graph Dissimilarities Enhance Affinity Propagation Community Detection in Complex Networks
• Dynamics of hot random hyperbolic graphs
• Topology and Geometry of the Third-Party Domains Ecosystem: Measurement and Applications
• Temporal rich club phenomenon and its formation mechanisms
• Geometric representations of brain networks can predict the surgery outcome in temporal lobe epilepsy
• Simple indicators for Lorentzian causets
• On the duration of face-to-face contacts
• Systematic comparison of graph embedding methods in practical tasks
• Homophilic Clustering by Locally Asymmetric Geometry
• Large algebraic connectivity fluctuations in spatial network ensembles imply a predictive advantage from node location information
• Nearest-neighbour directed random hyperbolic graphs
• Dynamics of cold random hyperbolic graphs with link persistence
• Modelling Multi-Trait Scale-free Networks by Optimization
• Reconstructing propagation networks with temporal similarity metrics
• Navigating Higher Dimensional Spaces using Hyperbolic Geometry
• Impact of local information in growing networks
• Observement as Universal Measurement
• High Performance Algorithms for Quantum Gravity and Cosmology
• HEAT: Hyperbolic Embedding of Attributed Networks
• Generating Tree Structures for Hyperbolic Tessellations
• Curvature of an Arbitrary Surface for Discrete Gravity and for $d=2$ Pure Simplicial Complexes
• Evolution of Social Networks: A Microfounded Model
• Microscopic Evolution of Social Networks by Triad Position Profile
• Dynamic Distances in Hyperbolic Graphs
• Hidden multiscale organization and robustness of real multiplex networks
• Non-Euclidean Self-Organizing Maps
• A Theory of Hyperbolic Prototype Learning
• Uncovering Patterns of Participant-Invariant Influence in Networks
• Improving Data Forwarding in Mobile Social Networks with Infrastructure Support: A Space-Crossing Community Approach
• Streaming Social Event Detection and Evolution Discovery in Heterogeneous Information Networks
• Hyperbolic Multiplex Network Embedding with Maps of Random Walk
• $({\omega }_1,{\omega }_2)$-temporal random hyperbolic graphs
• Hyperbolic embedding of multilayer networks
• Multiplexity amplifies geometry in networks
• The Hidden Geometry of Attention Diffusion
• Latent geometry emerging from network-driven processes
• Node similarity distribution of complex networks and its application in link prediction
• Robustness and size-dependence of circadian rhythms in multiscale suprachiasmatic-nucleus networks
• A game model for the multimodality phenomena of coauthorship networks
• Temporal similarity metrics for latent network reconstruction: The role of time-lag decay