Scale-free trees: the skeletons of complex networks

Abstract

We investigate the properties of the spanning trees of various real-world and model networks. The spanning tree representing the communication kernel of the original network is determined by maximizing total weight of edges, whose weights are given by the edge betweenness centralities. We find that a scale-free tree and shortcuts organize a complex network. The spanning tree shows robust betweenness centrality distribution that was observed in scale-free tree models. It turns out that the shortcut distribution characterizes the properties of original network, such as the clustering coefficient and the classification of networks by the betweenness centrality distribution.

References in corpus (17)

• Emergence of scaling in random networks
• Statistical mechanics of complex networks
• Community structure in social and biological networks
• Lethality and centrality in protein networks
• Assortative mixing in networks
• The diameter of the world wide web
• The large-scale organization of metabolic networks
• Evolution of networks
• Who is the best connected scientist? A study of scientific coauthorship networks
• Mean-field theory for scale-free random networks
• Evolution of the social network of scientific collaborations
• Universal Behavior of Load Distribution in Scale-free Networks
• Growing Scale-Free Networks with Tunable Clustering
• Fluctuation-driven dynamics of the Internet topology
• Shortest paths and load scaling in scale-free trees
• Comment on: 'Universal Behavior of Load Distribution in Scale-free Networks'
• Reply to "Comment on 'Universal Behavior of Load Distribution in Scale-Free Networks'"

Cited by in corpus (33)

• Skeleton and fractal scaling in complex networks
• Transport in weighted networks: Partition into superhighways and roads
• Statistical properties of visibility graph of energy dissipation rates in three-dimensional fully developed turbulence
• Fractality in complex networks: critical and supercritical skeletons
• The Backbone of a City
• Betweenness Centrality of Fractal and Non-Fractal Scale-Free Model Networks and Tests on Real Networks
• Removing spurious interactions in complex networks
• Optimal Path and Minimal Spanning Trees in Random Weighted Networks
• Robustness of the avalanche dynamics in data packet transport on scale-free networks
• Googling Social Interactions: Web Search Engine Based Social Network Construction
• Spectral dimensions of hierarchical scale-free networks with shortcuts
• Extracting the information backbone in online system
• Complete trails of co-authorship network evolution
• Networking - A Statistical Physics Perspective
• Network Quotients: Structural Skeletons of Complex Systems
• Complex systems approach to natural language
• Counting spanning trees in self-similar networks by evaluating determinants
• Fluctuation-driven capacity distribution in complex networks
• Centralized Modularity of N-Linked Glycosylation Pathways in Mammalian Cells
• Fractal and multifractal analysis of complex networks: Estonian network of payments
• What exactly are the properties of scale-free and other networks?
• Scale-Free Networks Emerging from Weighted Random Graphs
• Shortest path discovery of complex networks
• Structure of percolating clusters in random clustered networks
• Phase diagram of epidemic spreading - unimodal vs. bimodal probability distributions
• Topological estimation of the latent geometry of a complex network
• Scale-free random branching tree in supercritical phase
• Spanning Trees of Recursive Scale-Free Graphs
• Inhomogeneous substructures hidden in random networks
• Scale-free tree network with an ultra-large diameter
• Maximum Leaf Spanning Trees of Growing Sierpinski Networks Models
• Large Deviation Properties of Minimum Spanning Trees for Random Graphs
• Diffusion Processes Homogenization for Scale-Free Metric Networks