Graph Evolution: Densification and Shrinking Diameters

Abstract

How do real graphs evolve over time? What are ``normal'' growth patterns in social, technological, and information networks? Many studies have discovered patterns in static graphs, identifying properties in a single snapshot of a large network, or in a very small number of snapshots; these include heavy tails for in- and out-degree distributions, communities, small-world phenomena, and others. However, given the lack of information about network evolution over long periods, it has been hard to convert these findings into statements about trends over time. Here we study a wide range of real graphs, and we observe some surprising phenomena. First, most of these graphs densify over time, with the number of edges growing super-linearly in the number of nodes. Second, the average distance between nodes often shrinks over time, in contrast to the conventional wisdom that such distance parameters should increase slowly as a function of the number of nodes (like O(log n) or O(log(log n)). Existing graph generation models do not exhibit these types of behavior, even at a qualitative level. We provide a new graph generator, based on a ``forest fire'' spreading process, that has a simple, intuitive justification, requires very few parameters (like the ``flammability'' of nodes), and produces graphs exhibiting the full range of properties observed both in prior work and in the present study. We also notice that the ``forest fire'' model exhibits a sharp transition between sparse graphs and graphs that are densifying. Graphs with decreasing distance between the nodes are generated around this transition point.

References in corpus (8)

• Emergence of scaling in random networks
• The structure and function of complex networks
• Power laws, Pareto distributions and Zipf's law
• Identity and Search in Social Networks
• Organization of Growing Random Networks
• Growing networks with local rules: preferential attachment, clustering hierarchy and degree correlations
• Log-Networks
• Citation Statistics From More Than a Century of Physical Review

Cited by in corpus (75)

• Graph Embedding Techniques, Applications, and Performance: A Survey
• Overlapping Community Detection in Networks: the State of the Art and Comparative Study
• Popularity versus Similarity in Growing Networks
• Identifying influential spreaders in complex networks based on gravity formula
• Structure-based control of complex networks with nonlinear dynamics
• Ranking the spreading influence in complex networks
• Dynamic stochastic blockmodels for time-evolving social networks
• Learning and innovative elements of strategy adoption rules expand cooperative network topologies
• Identifying optimal targets of network attack by belief propagation
• Identify influential spreaders in complex networks, the role of neighborhood
• How women organize social networks different from men
• Self-similar scaling of density in complex real-world networks
• Optimal Deployment of Resources for Maximizing Impact in Spreading Processes
• Inducing Effect on the Percolation Transition in Complex Networks
• Maximizing Influence in Social Networks: A Two-Stage Stochastic Programming Approach That Exploits Submodularity
• MODEL: Motif-based Deep Feature Learning for Link Prediction
• Fast Algorithms for the Maximum Clique Problem on Massive Graphs with Applications to Overlapping Community Detection
• Looplessness in networks is linked to trophic coherence
• Accurate ranking of influential spreaders in networks based on dynamically asymmetric link-impact
• A critical look at power law modelling of the Internet
• Statistical Mechanics of the Minimum Dominating Set Problem
• Systematic evaluation of a new combinatorial curvature for complex networks
• Best Friends Forever (BFF): Finding Lasting Dense Subgraphs
• Identifying Communities and Key Vertices by Reconstructing Networks from Samples
• Extracting and Analyzing Hidden Graphs from Relational Databases
• Characteristic exponents of complex networks
• A Regularized Graph Layout Framework for Dynamic Network Visualization
• A generative graph model for electrical infrastructure networks
• Dimensionality of social networks using motifs and eigenvalues
• Structure controllability of complex network based on preferential matching
• Behavioral and Network Origins of Wealth Inequality: Insights from a Virtual World
• Positively Correlated Samples Save Pooled Testing Costs
• Network representation learning systematic review: ancestors and current development state
• Group detection in complex networks: An algorithm and comparison of the state of the art
• Predicting link directions via a recursive subgraph-based ranking
• The Metabolism and Growth of Web Forums
• Reentrant phase transitions in threshold driven contagion on multiplex networks
• Learning multifractal structure in large networks
• Random Spatial Network Models with Core-Periphery Structure
• Evolution Features and Behavior Characters of Friendship Networks on Campus Life
• Characteristics of Real Futures Trading Networks
• A Dynamic Process Interpretation of the Sparse ERGM Reference Model
• Forest Fire Clustering for Single-cell Sequencing with Iterative Label Propagation and Parallelized Monte Carlo Simulation
• Extreme robustness of scaling in sample space reducing processes explains Zipf's law in diffusion on directed networks
• The Directed Dominating Set Problem: Generalized Leaf Removal and Belief Propagation
• Dynamic range maximization in excitable networks
• Diversity of structural controllability of complex networks with given degree sequence
• Graph Similarity Description: How Are These Graphs Similar?
• Systems Applications of Social Networks
• Quantifying the consistency of scientific databases
• A Measurement Framework for Directed Networks
• Stay Awhile and Listen: User Interactions in a Crowdsourced Platform Offering Emotional Support
• Seeds Buffering for Information Spreading Processes
• Minimum Long-Loop Feedback Vertex Set and Network Dismantling
• Convex skeletons of complex networks
• Two types of densification scaling in the evolution of temporal networks
• Multiple Kernel Representation Learning on Networks
• Release Connection Fingerprints in Social Networks Using Personalized Differential Privacy
• Influencing Busy People in a Social Network
• OCSM : Finding Overlapping Cohesive Subgraphs with Minimum Degree
• A Simple and Generic Paradigm for Creating Complex Networks Using the Strategy of Vertex Selecting-and-Pairing
• War pact model of shrinking networks
• DeSCo: Towards Generalizable and Scalable Deep Subgraph Counting
• Vulnerability and Resilience of Social Engagement: Equilibrium Theory
• Computational Models for Commercial Advertisements in Social Networks
• Estimating Formation Mechanisms and Degree Distributions in Mixed Attachment Networks
• Core-periphery Detection Based on Masked Bayesian Non-negative Matrix Factorization
• Analyses of a Virtual World
• Outlier Edge Detection Using Random Graph Generation Models and Applications
• Malleability of complex networks
• Collaboration and followership: a stochastic model for activities in social networks
• Transfer Learning for Node Regression Applied to Spreading Prediction
• Competition Between Homophily and Information Entropy Maximization in Social Networks
• LUEM : Local User Engagement Maximization in Networks
• Sublinear Update Time Randomized Algorithms for Dynamic Graph Regression