The very small world of the well-connected

ABSTRACT

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.

REFERENCES

• 1: Lada A. Adamic, The Small World Web, Proceedings of the Third European Conference on Research and Advanced Technology for Digital Libraries, p.443-452, September 22-24, 1999
• 2: Lada A. Adamic , Natalie Glance, The political blogosphere and the 2004 U.S. election: divided they blog, Proceedings of the 3rd international workshop on Link discovery, p.36-43, August 21-25, 2005, Chicago, Illinois [doi>10.1145/1134271.1134277]
• 3: Micah Adler , Michael Mitzenmacher, Towards Compressing Web Graphs, Proceedings of the Data Compression Conference (DCC '01), p.203, March 27-29, 2001
• 4: Yong-Yeol Ahn , Seungyeop Han , Haewoon Kwak , Sue Moon , Hawoong Jeong, Analysis of topological characteristics of huge online social networking services, Proceedings of the 16th international conference on World Wide Web, May 08-12, 2007, Banff, Alberta, Canada [doi>10.1145/1242572.1242685]
• 5: Sergey Brin , Lawrence Page, The anatomy of a large-scale hypertextual Web search engine, Computer Networks and ISDN Systems, v.30 n.1-7, p.107-117, April 1, 1998
• 6: Andrei Broder , Ravi Kumar , Farzin Maghoul , Prabhakar Raghavan , Sridhar Rajagopalan , Raymie Stata , Andrew Tomkins , Janet Wiener, Graph structure in the Web, Computer Networks: The International Journal of Computer and Telecommunications Networking, v.33 n.1-6, p.309-320, June 2000
• 7: V. Colizza, A. Flammini, M. A. Serrano, and A. Vespignani. Detecting rich-club ordering in complex networks. NATURE PHYSICS, 2:110, 2006.
• 8: S. N. Dorogovtsev, A. V. Goltsev, and J. F. F. Mendes. k-core organization of complex networks. Physical Review Letters, 96:040601, 2006.
• 9: M. Garey and D. Johnson. The rectilinear Steiner problem is NP-complete. SIAM J. Appl. Math., 32(4):826--834, 1977.
• 10: A. C. Gilbert and K. Levchenko. Compressing network graphs. In LinkKDD, 2004.
• 11: E. N. Gilbert and H. O. Pollak. Steiner minimal trees. SIAM J. Appl. Math., 16(1):1--29, 1968.
• 12: Tad Hogg , Lada Adamic, Enhancing reputation mechanisms via online social networks, Proceedings of the 5th ACM conference on Electronic commerce, May 17-20, 2004, New York, NY, USA [doi>10.1145/988772.988811]
• 13: Jon M. Kleinberg, Authoritative sources in a hyperlinked environment, Journal of the ACM (JACM), v.46 n.5, p.604-632, Sept. 1999 [doi>10.1145/324133.324140]
• 14: J. M. Kleinberg, R. Kumar, P. Raghavan, S. Rajagopalan, and A. S. Tomkins. The Web as a graph: Measurements, models and methods. Lecture Notes in Computer Science, 1627:1--17, 1999.
• 15: S. H. Lee, P.-J. Kim, and H. Jeong. Statistical properties of sampled networks. Physical Review E, 73:016102, 2006.
• 16: Jure Leskovec , Susan Dumais , Eric Horvitz, Web projections: learning from contextual subgraphs of the web, Proceedings of the 16th international conference on World Wide Web, May 08-12, 2007, Banff, Alberta, Canada [doi>10.1145/1242572.1242636]
• 17: Jure Leskovec , Christos Faloutsos, Sampling from large graphs, Proceedings of the 12th ACM SIGKDD international conference on Knowledge discovery and data mining, August 20-23, 2006, Philadelphia, PA, USA [doi>10.1145/1150402.1150479]
• 18: Jure Leskovec , Andreas Krause , Carlos Guestrin , Christos Faloutsos , Jeanne VanBriesen , Natalie Glance, Cost-effective outbreak detection in networks, Proceedings of the 13th ACM SIGKDD international conference on Knowledge discovery and data mining, August 12-15, 2007, San Jose, California, USA [doi>10.1145/1281192.1281239]
• 19: P. Li, K. Church, and T. Hastie. A sketch-based sampling algorithm on sparse data. Technical report, Department of Statistics, Stanford University, 2006.
• 20: C. Macdonald and I. Ounis. The TREC Blogs06 collection: Creating and analysing a blog test collection. Tech report (dcs), Dept of Computing Science, University of Glasgow, 2006.
• 21: Alan Mislove , Massimiliano Marcon , Krishna P. Gummadi , Peter Druschel , Bobby Bhattacharjee, Measurement and analysis of online social networks, Proceedings of the 7th ACM SIGCOMM conference on Internet measurement, October 24-26, 2007, San Diego, California, USA [doi>10.1145/1298306.1298311]
• 22: M. Newman. Coauthorship networks and patterns of scientific collaboration, 2004.
• 23: M. E. J. Newman. Assortative mixing in networks. Phys. Rev. Lett., 89(20):208701, Oct 2002.
• 24: M. E. J. Newman. The structure and function of complex networks. SIAM Review, 45(2):167--256, 2003.
• 25: L. Page, S. Brin, R. Motwani, and T. Winograd. The pagerank citation ranking: Bringing order to the web. Technical report, Stanford Digital Library Technologies Project, 1998.
• 26: J. Park and M. Newman. Origin of degree correlations in the Internet and other networks. Physical Review E, 68(2):26112, 2003.
• 27: R. Pastor-Satorras, A. Vazquez, and A. Vespignani. Dynamical and correlation properties of the internet. Physical Review Letters, 87:258701, 2001.
• 28: D. Pennock, G. Flake, S. Lawrence, E. Glover, and C. Giles. Winners don't take all: Characterizing the competition for links on the web. Proceedings of the National Academy of Sciences, 99(8):5207, 2002.
• 29: X. Shi, B. Tseng, and L. Adamic. Looking at the Blogosphere Topology through Different Lenses. In Proceedings of the International Conference on Weblogs and Social Media (ICWSM 2007), volume 1001, page 48109, 2007.
• 30: Torsten Suel , Jun Yuan, Compressing the Graph Structure of the Web, Proceedings of the Data Compression Conference (DCC '01), p.213, March 27-29, 2001
• 31: Andrew Y. Wu , Michael Garland , Jiawei Han, Mining scale-free networks using geodesic clustering, Proceedings of the tenth ACM SIGKDD international conference on Knowledge discovery and data mining, August 22-25, 2004, Seattle, WA, USA [doi>10.1145/1014052.1014146]
• 32: S. Zhou and R. J. Mondragon. The Rich-Club Phenomenon In The Internet Topology. IEEE Commun. Lett., 8:180--182, 2004.

INDEX TERMS

Primary Classification:
  E. Data
  E.1 DATA STRUCTURES

Additional Classification:
  E. Data
  E.4 CODING AND INFORMATION THEORY

  G. Mathematics of Computing
  G.2 DISCRETE MATHEMATICS
      G.2.2 Graph Theory

General Terms:
Algorithms, Measurement, Theory

Keywords:
graph compression, graph synopsis