What's inside a bow-tie: Analyzing the core of the web and of social networks

The explosive growth of the Web and of social networks motivates the need for analyzing the macroscopic structure of their underlying graphs. Since the pioneering study by Broder et al. that revealed the bow-tie structure of the Web, many subsequent studies observed a similar structure in large-scale Web and social graphs, all reporting the existence of a giant strongly connected component that is considered as the core of the graph. Although the characterization of the structure of a graph with respect to its pairwise connectivity has been known for over 15 years, no study further analyzed the structure inside the largest strongly connected component of Web and social graphs. In this paper, we investigate the pairwise 2-connectivity among the vertices inside the core of Web and social graphs. Our experiments reveal an inner bow-tie structure, with respect to the pairwise 2-connectivity, that is formed around a giant 2-connected components. Furthermore, our fundings report a surprisingly consistent structure across Web graphs and across social graphs, despite the diff erence in their sizes and characteristics.