Structural Properties of Networks Grown via an Achlioptas Process

Abstract

After the Achlioptas process (AP), which yields the so-called explosive percolation, was introduced, the number of papers on percolation phenomena has been literally exploding. Most of the existing studies, however, have focused only on the nature of phase transitions, not paying proper attention to the structural properties of the resulting networks, which compose the main theme of the present paper. We compare the resulting network structure of the AP with random networks and find, through observations of the distributions of the shortest-path length and the betweenness centrality in the giant cluster, that the AP makes the network less clustered and more fragile. Such structural characteristics are more directly seen by using snapshots of the network structures and are explained by the fact that the AP suppresses the formation of large clusters more strongly than the random process does. These structural differences between the two processes are shown to be less noticeable in growing networks than in static ones.

arXiv comment12 pages, 4 figures, submitted for the journal publication

References in corpus (22)

• 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
• Evolution of networks
• Network robustness and fragility: Percolation on random graphs
• Critical phenomena in complex networks
• Attack vulnerability of complex networks
• Breakdown of the Internet under intentional attack
• Connectivity of Growing Random Networks
• Are randomly grown graphs really random?
• "Explosive Percolation" Transition is Actually Continuous
• Explosive Percolation is Continuous, but with Unusual Finite Size Behavior
• Percolation Transitions in Scale-Free Networks under Achlioptas Process
• Clustering in complex networks. I. General formalism
• Anomalous percolating properties of growing networks
• Avoiding a Spanning Cluster in Percolation Models
• Bicomponents and the robustness of networks to failure
• Suppression effect on explosive percolations
• Statistical Self-Similar Properties of Complex Networks
• Properties of a random attachment growing network
• Percolation properties of growing networks under an Achlioptas process