Maximal planar networks with large clustering coefficient and power-law degree distribution

Abstract

In this article, we propose a simple rule that generates scale-free networks with very large clustering coefficient and very small average distance. These networks are called {\bf Random Apollonian Networks}(RAN) as they can be considered as a variation of Apollonian networks. We obtain the analytic results of power-law exponent $\gamma =3$ and clustering coefficient $C=46/3-36\text{ln}3/2\approx 0.74$, which agree very well with the simulation results. We prove that the increasing tendency of average distance of RAN is a little slower than the logarithm of the number of nodes in RAN. Since most real-life networks are both scale-free and small-world networks, RAN may perform well in mimicking the reality. The RAN possess hierarchical structure as $C(k)\sim k^{-1}$ that in accord with the observations of many real-life networks. In addition, we prove that RAN are maximal planar networks, which are of particular practicability for layout of printed circuits and so on. The percolation and epidemic spreading process are also studies and the comparison between RAN and Barabási-Albert(BA) as well as Newman-Watts(NW) networks are shown. We find that, when the network order $N$(the total number of nodes) is relatively small(as $N\sim 10^4$), the performance of RAN under intentional attack is not sensitive to $N$, while that of BA networks is much affected by $N$. And the diseases spread slower in RAN than BA networks during the outbreaks, indicating that the large clustering coefficient may slower the spreading velocity especially in the outbreaks.

13 pages, 10 figures

References in corpus (75)

• 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
• The diameter of the world wide web
• The large-scale organization of metabolic networks
• Evolution of networks
• Classes of behavior of small-world networks
• Who is the best connected scientist? A study of scientific coauthorship networks
• Network robustness and fragility: Percolation on random graphs
• Resilience of the Internet to random breakdowns
• Mean-field theory for scale-free random networks
• Hierarchical Organization in Complex Networks
• Cascade-based attacks on complex networks
• Epidemic dynamics and endemic states in complex networks
• How Popular is Your Paper? An Empirical Study of the Citation Distribution
• Dynamical and correlation properties of the Internet
• Breakdown of the Internet under intentional attack
• Renormalization group analysis of the small-world network model
• The Web of Human Sexual Contacts
• Structure of Growing Networks: Exact Solution of the Barabasi--Albert's Model
• Topology of evolving networks: local events and universality
• Scaling and percolation in the small-world network model
• Connectivity of Growing Random Networks
• Organization of Growing Random Networks
• Bose-Einstein condensation in complex networks
• Cascade control and defense in complex networks
• Velocity and hierarchical spread of epidemic outbreaks in scale-free networks
• Epidemic dynamics in finite size scale-free networks
• Small-world properties of the Indian Railway network
• Epidemic spreading in correlated complex networks
• Absence of epidemic threshold in scale-free networks with connectivity correlations
• Pseudofractal Scale-free Web
• Is the Boston subway a small-world network ?
• Highly clustered scale-free networks
• Generic scale of the "scale-free" growing networks
• Robust Patterns in Food Web Structure
• Sandpile on Scale-Free Networks
• Scaling Behaviour of Developing and Decaying Networks
• Instability of scale-free networks under node-breaking avalanches
• Vertex overload breakdown in evolving networks
• Percolation in Directed Scale-Free Networks
• Epidemic spread in weighted scale-free networks
• Edge overload breakdown in evolving networks
• Effect of the accelerating growth of communications networks on their structure
• Diffusion, localization and dispersion relations on ``small-world'' lattices
• Autocatalytic Sets and the Growth of Complexity in an Evolutionary Model
• Critical load and congestion instabilities in scale-free networks
• Exact solution of site and bond percolation on small-world networks
• The Fractal Properties of Internet
• Correlated random networks
• Self-similar disk packings as model spatial scale-free networks
• Hierarchy Measures in Complex Networks
• World-Wide Web scaling exponent from Simon's 1955 model
• Structural transitions in scale-free networks
• Spreading and shortest paths in systems with sparse long-range connections
• Dynamics of directed graphs: the world-wide Web
• Potts model on complex networks
• Small-World Networks: Links with long-tailed distributions
• Sandpile avalanche dynamics on scale-free networks
• Statistical mechanics of topological phase transitions in networks
• Geographical Coarsegraining of Complex Networks
• Perturbation: the Catastrophe Causer in Scale-Free Networks
• First-order transition in small-world networks
• Scale free networks from a Hamiltonian dynamics
• Comment on "Breakdown of the Internet under Intentional Attack"
• Scaling in directed dynamical small-world networks with random responses
• Small-world phenomena and the statistics of linear polymer networks
• Network of Econophysicists: a weighted network to investigate the development of Econophysics
• A comprehensive weighted evolving network model
• Temporal fractal structures: Origin of power-laws in the world-wide Web
• Renormalization group for evolving networks
• Growing dynamics of Internet providers
• Dynamical Scaling Behavior of Percolation Clusters in Scale-free Networks

Cited by in corpus (95)

• Coevolution spreading in complex networks
• Behaviors of susceptible-infected epidemics on scale-free networks with identical infectivity
• Epidemic spreading on heterogeneous networks with identical infectivity
• Small world yields the most effective information spreading
• Identifying Infection Sources and Regions in Large Networks
• Entropy Optimization of Scale-Free Networks Robustness to Random Failures
• Non-equilibrium dynamics of language games on complex networks
• Inverted Berezinskii-Kosterlitz-Thouless Singularity and High-Temperature Algebraic Order in an Ising Model on a Scale-Free Hierarchical-Lattice Small-World Network
• Network geometry with flavor: from complexity to quantum geometry
• Scale-free networks without growth
• Efficient routing on scale-free networks based on local information
• Enhance synchronizability by structural perturbations
• Weighted Growing Simplicial Complexes
• Maximal planar scale-free Sierpinski networks with small-world effect and power-law strength-degree correlation
• Relations between Average Distance, Heterogeneity and Network Synchronizability
• High dimensional random Apollonian networks
• Self-similarity, small-world, scale-free scaling, disassortativity, and robustness in hierarchical lattices
• High Dimensional Apollonian Networks
• A Mutual Selection Model for Weighted Networks
• Evolving Apollonian Networks with Small-world Scale-free topologies
• A general geometric growth model for pseudofractal scale-free web
• Exact analytical solution of average path length for Apollonian networks
• Immunization of Susceptible-Infected Model on Scale-Free networks
• Dynamic Evolution of Complex Networks: A Reinforcement Learning Approach Applying Evolutionary Games to Community Structure
• Random walks on the Apollonian network with a single trap
• Random Sierpinski network with scale-free small-world and modular structure
• Evolving small-world scale-free networks consist of cliques
• Weighted Network of Chinese Nature Science Basic Research
• Optimization of network structure to random failures
• Evolving small-world networks with geographical attachment preference
• A general model for collaboration networks
• Growing Scale-free Small-world Networks with Tunable Assortative Coefficient
• Integer Networks
• Impact of Heterogeneous Human Activities on Epidemic Spreading
• Geographical networks evolving with optimal policy
• Exploring complex networks via topological embedding on surfaces
• Walks on Apollonian networks
• A directed network model for World-Wide Web
• Effect of node deleting on network structure
• Characterizing departure delays of flights in passenger aviation network of United States
• Local-world evolving networks with tunable clustering
• Correlations in random Apollonian network
• Improvement of the robustness on geographical networks by adding shortcuts
• Complex Network Properties of Chinese Natural Science Basic Research
• Empirical study on clique-degree distribution of networks
• Predicting link directions via a recursive subgraph-based ranking
• Deterministic weighted scale-free small-world networks
• A Network Science perspective of Graph Convolutional Networks: A survey
• Universal Scaling Behavior of Clustering Coefficient Induced by Deactivation Mechanism
• Lower bound of assortativity coefficient in scale-free networks
• From regular to growing small-world networks
• Infinitely Robust Order and Local Order-Parameter Tulips in Apollonian Networks with Quenched Disorder
• Mandelbrot Law of Evolving Networks
• Synchronous and Asynchronous Recursive Random Scale-Free Nets
• Interplay between HIV/AIDS Epidemics and Demographic Structures Based on Sexual Contact Networks
• How Transitive Are Real-World Group Interactions? -- Measurement and Reproduction
• Mathematical and Algorithmic Analysis of Network and Biological Data
• Principled Multilayer Network Embedding
• Evolutionary Construction of Geographical Networks with Nearly Optimal Robustness and Efficient Routing Properties
• Geographical networks stochastically constructed by a self-similar tiling according to population
• Scaling of disordered recursive networks
• Time scales of epidemic spread and risk perception on adaptive networks
• Growing Self-organized Design of Efficient and Robust Complex Networks
• Comment on "Maximal planar networks with large clustering coefficient and power-law degree distribution"
• Vertex labeling and routing in expanded Apollonian networks
• On the Longest Paths and the Diameter in Random Apollonian Networks
• Generalized preferential attachment: tunable power-law degree distribution and clustering coefficient
• Entropy of unimodular Lattice Triangulations
• Spatially self-organized resilient networks by a distributed cooperative mechanism
• Simplex triangulation induced scale-free networks
• Deterministic scale-free networks created in a recursive manner
• Unimodular lattice triangulations as small-world and scale-free random graphs
• An approximative calculation of the fractal structure in self-similar tilings
• Epidemic dynamics on complex networks
• A survey on modelling of infectious disease spread and control on social contact networks
• Random Apollonian networks with tailored clustering coefficient
• Degrees and distances in random and evolving Apollonian networks
• The heavy path approach to Galton-Watson trees with an application to Apollonian networks
• Distances in random Apollonian network structures
• Characterizing several properties of high-dimensional random Apollonian networks
• Spectral properties of unimodular lattice triangulations
• Nearest-neighbour directed random hyperbolic graphs
• Assortativity in Generalized Preferential Attachment Models
• Scale-free Loopy Structure is Resistant to Noise in Consensus Dynamics in Complex Networks
• Diffusion on dynamic contact networks with indirect transmission links
• Toughness and Hamiltonicity in Random Apollonian Networks
• Adaptive Fractal-like Network Structure for Efficient Search of Inhomogeneously Distributed Targets at Unknown Positions
• The Number of Spanning Trees in Apollonian Networks
• Simple Derivation of the Lifetime and the Distribution of Faces for a Binary Subdivision Model
• Longest paths in random Apollonian networks and largest $r$-ary subtrees of random $d$-ary recursive trees
• High Degree Vertices, Eigenvalues and Diameter of Random Apollonian Networks
• The Degree Sequence of Random Apollonian Networks
• Recoverable DTN Routing based on a Relay of Cyclic Message-Ferries on a MSQ Network
• The $N$-stars network evolution model
• Randomized Rumor Spreading in Poorly Connected Small-World Networks