Online networks occupy an increasingly larger position in how we
acquire information, how we communicate with one another, and how we
disseminate information. Frequently, small sets of vertices
dominate various graph and statistical properties of these networks
and, because of this, they are relevant for structural
analysis and efficient algorithms and engineering. For
the web overall, and specifically for social linking in blogs and
instant messaging, we provide a principled, rigorous study of the
properties, the construction, and the utilization of subsets of
special vertices in large online networks. We show that graph
synopses defined by the importance of vertices provide small,
relatively accurate portraits, independent of the importance
measure, of the larger underlying graphs and of the important
vertices. Furthermore, they can be computed relatively efficiently.
Copyright. All Rights Reserved.