Log-Networks

Abstract

We introduce a growing network model in which a new node attaches to a randomly-selected node, as well as to all ancestors of the target node. This mechanism produces a sparse, ultra-small network where the average node degree grows logarithmically with network size while the network diameter equals 2. We determine basic geometrical network properties, such as the size dependence of the number of links and the in- and out-degree distributions. We also compare our predictions with real networks where the node degree also grows slowly with time -- the Internet and the citation network of all Physical Review papers.

7 pages, 6 figures, 2-column revtex4 format. Version 2: minor changes in response to referee comments and to another proofreading; final version for PRE

References in corpus (10)

• Emergence of scaling in random networks
• Statistical mechanics of complex networks
• The structure and function of complex networks
• Who is the best connected scientist? A study of scientific coauthorship networks
• Organization of Growing Random Networks
• Self-organization of collaboration networks
• Finiteness and Fluctuations in Growing Networks
• Statistics of Lead Changes in Popularity-Driven Systems
• Life, Death and Preferential Attachment
• Accelerated growth in outgoing links in evolving networks: deterministic vs. stochastic picture

Cited by in corpus (62)

• Hyperbolic Geometry of Complex Networks
• The Matthew effect in empirical data
• Graph Evolution: Densification and Shrinking Diameters
• Triadic closure as a basic generating mechanism of communities in complex networks
• Modeling complex systems with adaptive networks
• Duplication-divergence model of protein interaction network
• The Memory of Science: Inflation, Myopia, and the Knowledge Network
• Structural Transitions in Dense Networks
• Local Leaders in Random Networks
• Growing complex network of citations of scientific papers -- measurements and modeling
• Logarithmic growth dynamics in software networks
• The power of choice in network growth
• Random Graph Modeling: A survey of the concepts
• Densification and Structural Transitions in Networks that Grow by Node Copying
• Prosperity is associated with instability in dynamical networks
• Structure and Interpretation of Computer Programs
• The Time Dimension of Science: Connecting the Past to the Future
• Network growth models and genetic regulatory networks
• Modeling the average shortest path length in growth of word-adjacency networks
• Power-law citation distributions are not scale-free
• Discrete-time quantum walk algorithm for ranking nodes on a network
• Preferential attachment mechanism of complex network growth: "rich-gets-richer" or "fit-gets-richer"?
• The distribution of shortest path lengths in a class of node duplication network models
• Multiplex congruence network of natural numbers
• The disruption index is biased by citation inflation
• Assortativity and leadership emergence from anti-preferential attachment in heterogeneous networks
• The disruption index suffers from citation inflation and is confounded by shifts in scholarly citation practice
• The transition towards immortality: non-linear autocatalytic growth of citations to scientific papers
• Coupled dynamics of node and link states in complex networks: A model for language competition
• Identifying time dependence in network growth
• A general model of hierarchical fractal scale-free networks
• Preferential survival in models of complex ad hoc networks
• Growing network with j-redirection
• Analytical results for the distribution of shortest path lengths in directed random networks that grow by node duplication
• Emergent Network Modularity
• Partition of Networks into Basins of Attraction
• Highly Dispersed Networks Generated by Enhanced Redirection
• The Accelerating Growth of Online Tagging Systems
• The structure of networks that evolve under a combination of growth, via node addition and random attachment, and contraction, via random node deletion
• Complex networks as an emerging property of hierarchical preferential attachment
• Descendant distributions for the impact of mutant contagion on networks
• Emergence of Robust and Efficient Networks in a Family of Attachment Models
• Highly Dispersed Networks
• Epistemic Phase Transitions in Mathematical Proofs
• Random Recursive Hypergraphs
• Exactly Solvable Random Graph Ensemble with Extensively Many Short Cycles
• Random Ancestor Trees
• Analytical results for the in-degree and out-degree distributions of directed random networks that grow by node duplication
• Discrete-Time Open Quantum Walks for Vertex Ranking in Graphs
• Non-equilibrium phase transitions in competitive markets caused by network effects
• The Magic of Networks Grown by Redirection
• Asymmetric access to information impacts the power-law exponent in networks
• Software graphs and programmer awareness
• Activity ageing in growing networks
• Clique Densification in Networks
• Dynamic Scaling, Data-collapse and Self-Similarity in Mediation-Driven Attachment Networks
• Distinct Degrees and Their Distribution in Complex Networks
• An Agent-based Model of Citation Behavior
• Growing Networks with Super-Joiners
• Emergence of network communities driven by local rules
• Manageable to unmanageable transition in a fractal model of project networks
• Scale-Invariant Strength Assortativity of Streaming Butterflies