Extraction and classification of dense implicit communities in the Web graph

ABSTRACT

The World Wide Web (WWW) is rapidly becoming important for society as a medium for sharing data, information, and services, and there is a growing interest in tools for understanding collective behavior and emerging phenomena in the WWW. In this article we focus on the problem of searching and classifying communities in the Web. Loosely speaking a community is a group of pages related to a common interest. More formally, communities have been associated in the computer science literature with the existence of a locally dense subgraph of the Web graph (where Web pages are nodes and hyperlinks are arcs of the Web graph). The core of our contribution is a new scalable algorithm for finding relatively dense subgraphs in massive graphs. We apply our algorithm on Web graphs built on three publicly available large crawls of the Web (with raw sizes up to 120M nodes and 1G arcs). The effectiveness of our algorithm in finding dense subgraphs is demonstrated experimentally by embedding artificial communities in the Web graph and counting how many of these are blindly found. Effectiveness increases with the size and density of the communities: it is close to 100% for communities of thirty nodes or more (even at low density). It is still about 80% even for communities of twenty nodes with density over 50% of the arcs present. At the lower extremes the algorithm catches 35% of dense communities made of ten nodes. We also develop some sufficient conditions for the detection of a community under some local graph models and not-too-restrictive hypotheses. We complete our Community Watch system by clustering the communities found in the Web graph into homogeneous groups by topic and labeling each group by representative keywords.

REFERENCES

• 1: James Abello , Mauricio G. C. Resende , Sandra Sudarsky, Massive Quasi-Clique Detection, Proceedings of the 5th Latin American Symposium on Theoretical Informatics, p.598-612, April 03-06, 2002
• 2: Einat Amitay , David Carmel , Adam Darlow , Ronny Lempel , Aya Soffer, The connectivity sonar: detecting site functionality by structural patterns, Proceedings of the fourteenth ACM conference on Hypertext and hypermedia, August 26-30, 2003, Nottingham, UK [doi>10.1145/900051.900060]
• 3: Krishna Bharat , Andrei Broder , Jeffrey Dean , Monika R. Henzinger, A comparison of techniques to find mirrored hosts on the WWW, Journal of the American Society for Information Science, v.51 n.12, p.1114-1122, Oct. 2000 [doi>10.1002/1097-4571(2000)9999:9999<::AID-ASI1025>3.0.CO;2-0]
• 4: Monica Bianchini , Marco Gori , Franco Scarselli, Inside PageRank, ACM Transactions on Internet Technology (TOIT), v.5 n.1, p.92-128, February 2005 [doi>10.1145/1052934.1052938]
• 5: Paolo Boldi , Bruno Codenotti , Massimo Santini , Sebastiano Vigna, UbiCrawler: a scalable fully distributed web crawler, Software—Practice & Experience, v.34 n.8, p.711-726, 10 July 2004 [doi>10.1002/spe.587]
• 6: P. Boldi , S. Vigna, The webgraph framework I: compression techniques, Proceedings of the 13th international conference on World Wide Web, May 17-20, 2004, New York, NY, USA [doi>10.1145/988672.988752]
• 7: 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
• 8: Andrei Z. Broder , Moses Charikar , Alan M. Frieze , Michael Mitzenmacher, Min-wise independent permutations, Journal of Computer and System Sciences, v.60 n.3, p.630-659, June 2000 [doi>10.1006/jcss.1999.1690]
• 9: Andrei Z. Broder , Steven C. Glassman , Mark S. Manasse , Geoffrey Zweig, Syntactic clustering of the Web, Selected papers from the sixth international conference on World Wide Web, p.1157-1166, September 1997, Santa Clara, California, United States
• 10: Capocci, A., Servedio, V. D. P., Caldarelli, G., and Colaiori, F. 2004. Communities detection in large networks. In Proceedings of the Algorithms and Models for the Web graph (WAW'04): Third International Workshop. 181--188.
• 11: Soumen Chakrabarti , Byron E. Dom , S. Ravi Kumar , Prabhakar Raghavan , Sridhar Rajagopalan , Andrew Tomkins , David Gibson , Jon Kleinberg, Mining the Web's Link Structure, Computer, v.32 n.8, p.60-67, August 1999 [doi>10.1109/2.781636]
• 12: Cho, J. and Garcia-Molina, H. 2000. WebBase and the Stanford interlib project. In Proceedings of the Kyoto International Conference on Digital Libraries: Research and Practice.
• 13: Thomas M. Cover , Joy A. Thomas, Elements of information theory, Wiley-Interscience, New York, NY, 1991
• 14: Yon Dourisboure , Filippo Geraci , Marco Pellegrini, Extraction and classification of dense communities in the web, Proceedings of the 16th international conference on World Wide Web, May 08-12, 2007, Banff, Alberta, Canada [doi>10.1145/1242572.1242635]
• 15: Rui Fang , Alexander Mikroyannidis , Babis Theodoulidis, A Voting Method for the Classification of Web Pages, Proceedings of the 2006 IEEE/WIC/ACM international conference on Web Intelligence and Intelligent Agent Technology, p.610-613, December 18-22, 2006 [doi>10.1109/WI-IATW.2006.23]
• 16: Uriel Feige, Relations between average case complexity and approximation complexity, Proceedings of the thiry-fourth annual ACM symposium on Theory of computing, May 19-21, 2002, Montreal, Quebec, Canada [doi>10.1145/509907.509985]
• 17: Uriel Feige , Michael Langberg, Approximation algorithms for maximization problems arising in graph partitioning, Journal of Algorithms, v.41 n.2, p.174-211, November 2001 [doi>10.1006/jagm.2001.1183]
• 18: Feige, U., Peleg, D., and Kortsarz, G. 2001. The dense k-subgraph problem. Algorithmica 29, 3, 410--421.
• 19: Gary William Flake , Steve Lawrence , C. Lee Giles, Efficient identification of Web communities, Proceedings of the sixth ACM SIGKDD international conference on Knowledge discovery and data mining, p.150-160, August 20-23, 2000, Boston, Massachusetts, United States [doi>10.1145/347090.347121]
• 20: Gary William Flake , Steve Lawrence , C. Lee Giles , Frans M. Coetzee, Self-Organization and Identification of Web Communities, Computer, v.35 n.3, p.66-71, March 2002 [doi>10.1109/2.989932]
• 21: Geraci, F., Pellegrini, M., Maggini, M., and Sebastiani, F. 2007. Cluster generation and labeling for web snippets:a fast, accurate hierarchical solution. Internet Math. 3, 4, 413--443.
• 22: David Gibson , Jon Kleinberg , Prabhakar Raghavan, Inferring Web communities from link topology, Proceedings of the ninth ACM conference on Hypertext and hypermedia : links, objects, time and space---structure in hypermedia systems: links, objects, time and space---structure in hypermedia systems, p.225-234, June 20-24, 1998, Pittsburgh, Pennsylvania, United States [doi>10.1145/276627.276652]
• 23: David Gibson , Ravi Kumar , Andrew Tomkins, Discovering large dense subgraphs in massive graphs, Proceedings of the 31st international conference on Very large data bases, August 30-September 02, 2005, Trondheim, Norway
• 24: Girvan, M. and Newman, M. E. J. 2002. Community structure in social and biological networks. Proceedings of the National Academic Science, 7821--7826.
• 25: Eric J. Glover , Kostas Tsioutsiouliklis , Steve Lawrence , David M. Pennock , Gary W. Flake, Using web structure for classifying and describing web pages, Proceedings of the 11th international conference on World Wide Web, May 07-11, 2002, Honolulu, Hawaii, USA [doi>10.1145/511446.511520]
• 26: A. Gulli , A. Signorini, The indexable web is more than 11.5 billion pages, Special interest tracks and posters of the 14th international conference on World Wide Web, May 10-14, 2005, Chiba, Japan [doi>10.1145/1062745.1062789]
• 27: Gyöngyi, Z. and Garcia-Molina, H. 2005. Web spam taxonomy. In Proceedings of the 1st International Workshop on Adversarial Information Retrieval on the Web.
• 28: Hastad, J. 1999. Clique is hard to approximate within n^1−ε. Acta Mathematica 182, 105--142.
• 29: Haveliwala, T. H., Gionis, A., and Indyk, P. 2000. Scalable techniques for clustering the web. In Proceedings of the WebDB Workshop. 129--134.
• 30: Henzinger, M. 2002. Algorithmic challenges in Web search engines. Internet Math. 1, 1, 115--126.
• 31: Noriko Imafuji , Masaru Kitsuregawa, Finding a Web Community by Maximum Flow Algorithm with HITS Score Based Capacity, Proceedings of the Eighth International Conference on Database Systems for Advanced Applications, p.101, March 26-28, 2003
• 32: Hidehiko Ino , Mineichi Kudo , Atsuyoshi Nakamura, Partitioning of Web graphs by community topology, Proceedings of the 14th international conference on World Wide Web, May 10-14, 2005, Chiba, Japan [doi>10.1145/1060745.1060841]
• 33: Henry Kautz , Bart Selman , Mehul Shah, Referral Web: combining social networks and collaborative filtering, Communications of the ACM, v.40 n.3, p.63-65, March 1997 [doi>10.1145/245108.245123]
• 34: Ravi Kumar , Prabhakar Raghavan , Sridhar Rajagopalan , Andrew Tomkins, Extracting Large-Scale Knowledge Bases from the Web, Proceedings of the 25th International Conference on Very Large Data Bases, p.639-650, September 07-10, 1999
• 35: Ravi Kumar , Prabhakar Raghavan , Sridhar Rajagopalan , Andrew Tomkins, Trawling the Web for emerging cyber-communities, Computer Networks: The International Journal of Computer and Telecommunications Networking, v.31 n.11-16, p.1481-1493, May 17, 1999
• 36: Kumar, R., Raghavan, P., Rajagopalan, S., and Tomkins, A. 2005. Method and system for trawling the world-wide Web to identify implicitly-defined communities of Web pages. US patent 6886129.
• 37: Ravi Kumar , Prabhakar Raghavan , Sridhar Rajagopalan , Andrew Tomkins, Extracting Large-Scale Knowledge Bases from the Web, Proceedings of the 25th International Conference on Very Large Data Bases, p.639-650, September 07-10, 1999
• 38: R. Lempel , S. Moran, The stochastic approach for link-structure analysis (SALSA) and the TKC effect, Computer Networks: The International Journal of Computer and Telecommunications Networking, v.33 n.1-6, p.387-401, June 2000
• 39: Christoph Lindemann , Lars Littig, Classifying web sites, Proceedings of the 16th international conference on World Wide Web, May 08-12, 2007, Banff, Alberta, Canada [doi>10.1145/1242572.1242736]
• 40: Newman, M. 2003. The structure and function of complex networks. SIAM Rev. 45, 2, 167--256.
• 41: P. Krishna Reddy , Masaru Kitsuregawa, An Approach to Relate the Web Communities through Bipartite Graphs, Proceedings of the Second International Conference on Web Information Systems Engineering (WISE'01) Volume 1, p.301, December 03-06, 2001
• 42: Stamou, S., Ntoulas, A., Krikos, V., Kokosis, P., and Christodoulakis, D. 2006. Classifying web data in directory structures. In Frontiers of WWW Research and Development—APWeb, 8th Asia-Pacific Web Conference. Lecture Notes in Computer Science, vol. 3841. Springer, 238--249.
• 43: Baoning Wu , Brian D. Davison, Identifying link farm spam pages, Special interest tracks and posters of the 14th international conference on World Wide Web, May 10-14, 2005, Chiba, Japan [doi>10.1145/1062745.1062762]

INDEX TERMS

Primary Classification:
  F. Theory of Computation
  F.2 ANALYSIS OF ALGORITHMS AND PROBLEM COMPLEXITY
      F.2.2 Nonnumerical Algorithms and Problems
          Subjects: Computations on discrete structures

Additional Classification:
  H. Information Systems
  H.2 DATABASE MANAGEMENT
      H.2.8 Database applications
          Subjects: Data mining
  H.3 INFORMATION STORAGE AND RETRIEVAL
      H.3.3 Information Search and Retrieval
          Subjects: Clustering

General Terms:
Algorithms, Experimentation, Theory

Keywords:
Web graph, communities, detection of dense subgraph