Robustness of Social Networks: Comparative Results Based on Distance\n Distributions

Given a social network, which of its nodes have a stronger impact in\ndetermining its structure? More formally: which node-removal order has the\ngreatest impact on the network structure? We approach this well-known problem\nfor the first time in a setting that combines both web graphs and social\nnetworks, using datasets that are orders of magnitude larger than those\nappearing in the previous literature, thanks to some recently developed\nalgorithms and software tools that make it possible to approximate accurately\nthe number of reachable pairs and the distribution of distances in a graph. Our\nexperiments highlight deep differences in the structure of social networks and\nweb graphs, show significant limitations of previous experimental results, and\nat the same time reveal clustering by label propagation as a new and very\neffective way of locating nodes that are important from a structural viewpoint.\n