Structural properties of Complex networks

The k-core decomposition was recently applied to a number of real-world networks (the Internet, the WWW, cellular networks, etc and was turned out to be an important tool for visualization of complex networks and interpretation of cooperative processes in them. Rich k-core architectures of real networks were revealed. The k-core is the largest subgraph where vertices have at least k interconnections. We find the structure of k-cores, their sizes, and their birth points --- the bootstrap percolation thresholds. I will show a derivation of exact equations describing the k-core organization of a randomly damaged uncorrelated network with an arbitrary degree distribution. This allows us to obtain the sizes and other structural characteristics of k-cores in a variety of damaged and undamaged random networks and find the nature of the k-core percolation in complex networks. These general results will be applied to the classical random graphs and to scale-free networks, in particular, to empirical router-level Internet maps. We find that not only the giant connected components in infinite networks with slowly decreasing degree distributions are resilient against random damage, as was known, but their entire k-core architectures are robust.