Biconnectivity of social and web graphs

Network connectivity is a basic notion for big data analysis, with many practical applications. In particular, the analysis of the largest strongly connected component is at the heart of the famous bow-tie structure of the Web. In this paper, we go beyond connected components and characterize the properties of the higher-connectivity components that lie inside real-world networks. We combine and extend recently developed techniques for scaling up to real-world datasets with up to 23.1 billion edges. Our experiments point out a striking difference between structural properties in social and web graphs, and highlight deep properties of social networks which may be helpful in devising theoretical models that can better capture their structure.