Border trees of complex networks

Abstract

The comprehensive characterization of the structure of complex networks is essential to understand the dynamical processes which guide their evolution. The discovery of the scale-free distribution and the small world property of real networks were fundamental to stimulate more realistic models and to understand some dynamical processes such as network growth. However, properties related to the network borders (nodes with degree equal to one), one of its most fragile parts, remain little investigated and understood. The border nodes may be involved in the evolution of structures such as geographical networks. Here we analyze complex networks by looking for border trees, which are defined as the subgraphs without cycles connected to the remainder of the network (containing cycles) and terminating into border nodes. In addition to describing an algorithm for identification of such tree subgraphs, we also consider a series of their measurements, including their number of vertices, number of leaves, and depth. We investigate the properties of border trees for several theoretical models as well as real-world networks.

5 pages, 1 figure, 2 tables. A working manuscript, comments and suggestions welcomed

References in corpus (9)

• Emergence of scaling in random networks
• The structure and function of complex networks
• The diameter of the world wide web
• Who is the best connected scientist? A study of scientific coauthorship networks
• New Model of Internet Topology Using k-shell Decomposition
• MEDUSA - New Model of Internet Topology Using k-shell Decomposition
• k-core organization of complex networks
• Classes of complex networks defined by role-to-role connectivity profiles
• Strong correlations between text quality and complex networks features

Cited by in corpus (7)

• Analyzing and Modeling Real-World Phenomena with Complex Networks: A Survey of Applications
• Random walks on complex trees
• Explicit determination of mean first-passage time for random walks on deterministic uniform recursive trees
• Anomalous behavior of trapping on a fractal scale-free network
• Influences of degree inhomogeneity on average path length and random walks in disassortative scale-free networks
• Random walks in small-world exponential treelike networks
• Evaluating links through spectral decomposition