The connectivity sonar: detecting site functionality by structural patterns

ABSTRACT

Web sites today serve many different functions, such as corporate sites, search engines, e-stores, and so forth. As sites are created for different purposes, their structure and connectivity characteristics vary. However, this research argues that sites of similar role exhibit similar structural patterns, as the functionality of a site naturally induces a typical hyperlinked structure and typical connectivity patterns to and from the rest of the Web. Thus, the functionality of Web sites is reflected in a set of structural and connectivity-based features that form a typical signature. In this paper, we automatically categorize sites into eight distinct functional classes, and highlight several search-engine related applications that could make immediate use of such technology. We purposely limit our categorization algorithms by tapping connectivity and structural data alone, making no use of any content analysis whatsoever. When applying two classification algorithms to a set of 202 sites of the eight defined functional categories, the algorithms correctly classified between 54.5% and 59% of the sites. On some categories, the precision of the classification exceeded 85%. An additional result of this work indicates that the structural signature can be used to detect spam rings and mirror sites, by clustering sites with almost identical signatures.

REFERENCES

• 1: Lada A. Adamic , Bernardo A. Huberman, The Web's hidden order, Communications of the ACM, v.44 n.9, p.55-60, Sept. 2001 [doi>10.1145/383694.383707]
• 2: E. Amitay. Using common hypertext links to identify the best phrasal description of target web documents. In Proc of the SIGIR'98 Post-Conference Workshop on Hypertext Information Retrieval for the Web, Melbourne, Australia, 1998.
• 3: Ziv Bar-Yossef , Sridhar Rajagopalan, Template detection via data mining and its applications, Proceedings of the 11th international conference on World Wide Web, May 07-11, 2002, Honolulu, Hawaii, USA [doi>10.1145/511446.511522]
• 4: A.-L. Barabasi and R. Albert. Emergence of scaling in random networks. Science, 286:509--512, October 1999.
• 5: Mark Bernstein, Patterns of hypertext, 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.21-29, June 20-24, 1998, Pittsburgh, Pennsylvania, United States [doi>10.1145/276627.276630]
• 6: Krishna Bharat , Andrei Broder , Monika Henzinger , Puneet Kumar , Suresh Venkatasubramanian, The connectivity server: fast access to linkage information on the Web, Proceedings of the seventh international conference on World Wide Web 7, p.469-477, April 1998, Brisbane, Australia
• 7: B. Bollobás. Random Graphs. Academic Press, 1985.
• 8: Rodrigo A. Botafogo , Ehud Rivlin , Ben Shneiderman, Structural analysis of hypertexts: identifying hierarchies and useful metrics, ACM Transactions on Information Systems (TOIS), v.10 n.2, p.142-180, April 1992 [doi>10.1145/146802.146826]
• 9: Sergey Brin , Lawrence Page, The anatomy of a large-scale hypertextual Web search engine, Proceedings of the seventh international conference on World Wide Web 7, p.107-117, April 1998, Brisbane, Australia
• 10: Andrei Broder, A taxonomy of web search, ACM SIGIR Forum, v.36 n.2, Fall 2002 [doi>10.1145/792550.792552]
• 11: Andrei Broder , Ravi Kumar , Farzin Maghoul , Prabhakar Raghavan , Sridhar Rajagopalan , Raymie Stata , Andrew Tomkins , Janet Wiener, Graph structure in the Web, Proceedings of the 9th international World Wide Web conference on Computer networks : the international journal of computer and telecommunications netowrking, p.309-320, June 2000, Amsterdam, The Netherlands
• 12: Soumen Chakrabarti , Byron Dom , Piotr Indyk, Enhanced hypertext categorization using hyperlinks, Proceedings of the 1998 ACM SIGMOD international conference on Management of data, p.307-318, June 01-04, 1998, Seattle, Washington, United States
• 13: Soumen Chakrabarti , Mukul M. Joshi , Kunal Punera , David M. Pennock, The structure of broad topics on the web, Proceedings of the 11th international conference on World Wide Web, May 07-11, 2002, Honolulu, Hawaii, USA [doi>10.1145/511446.511480]
• 14: B. D. Davison. Recognizing nepotistic links on the web. Technical Report WS-00-01, Artificial Intelligence for Web Search, 2000.
• 15: Brian D. Davison, Topical locality in the Web, Proceedings of the 23rd annual international ACM SIGIR conference on Research and development in information retrieval, p.272-279, July 24-28, 2000, Athens, Greece [doi>10.1145/345508.345597]
• 16: Jeffrey Dean , Monika R. Henzinger, Finding related pages in the World Wide Web, Proceeding of the eighth international conference on World Wide Web, p.1467-1479, May 1999, Toronto, Canada
• 17: Stephen Dill , Ravi Kumar , Kevin S. Mccurley , Sridhar Rajagopalan , D. Sivakumar , Andrew Tomkins, Self-similarity in the web, ACM Transactions on Internet Technology (TOIT), v.2 n.3, p.205-223, August 2002 [doi>10.1145/572326.572328]
• 18: Cynthia Dwork , Ravi Kumar , Moni Naor , D. Sivakumar, Rank aggregation methods for the Web, Proceedings of the 10th international conference on World Wide Web, p.613-622, May 01-05, 2001, Hong Kong, Hong Kong [doi>10.1145/371920.372165]
• 19: Dennis Fetterly , Mark Manasse , Marc Najork , Janet Wiener, A large-scale study of the evolution of web pages, Proceedings of the 12th international conference on World Wide Web, May 20-24, 2003, Budapest, Hungary [doi>10.1145/775152.775246]
• 20: 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]
• 21: J. Fürnkranz. Using links for classifying web-pages. Technical Report TR-OEFAI-98-29, Austrian Research Institute for Artificial Intelligence, 1998.
• 22: D. M. Germán , D. D. Cowan, Towards a Unified Catalog of Hypermedia Design Patterns, Proceedings of the 33rd Hawaii International Conference on System Sciences-Volume 6, p.6067, January 04-07, 2000
• 23: 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]
• 24: Monika Henzinger , Bay-Wei Chang , Brian Milch , Sergey Brin, Query-free news search, Proceedings of the 12th international conference on World Wide Web, May 20-24, 2003, Budapest, Hungary [doi>10.1145/775152.775154]
• 25: Monika R. Henzinger , Rajeev Motwani , Craig Silverstein, Challenges in web search engines, ACM SIGIR Forum, v.36 n.2, Fall 2002 [doi>10.1145/792550.792553]
• 26: M. Kessler. Bibliographic coupling between scientific papers. American Documentation, 14:10--25, 1963.
• 27: 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]
• 28: J. M. Kleinberg, R. Kumar, P. Raghavan, S. Rajagopalan, and A. S. Tomkins. The web as a graph: Measurements, models and methods. Proceedings of the Fifth International Computing and Combinatorics Conference, pages 1--17, 1999.
• 29: R. Kumar , P. Raghavan , S. Rajagopalan , D. Sivakumar , A. Tomkins , E. Upfal, Stochastic models for the Web graph, Proceedings of the 41st Annual Symposium on Foundations of Computer Science, p.57, November 12-14, 2000
• 30: Ravi Kumar , Prabhakar Raghavan , Sridhar Rajagopalan , Andrew Tomkins, Trawling the Web for emerging cyber-communities, Proceeding of the eighth international conference on World Wide Web, p.1481-1493, May 1999, Toronto, Canada
• 31: O. A. McBryan. Genvl and wwww: Tools for taming the web. In Proc First International World Wide Web Conference, Geneva, Switzerland, pages 79--90, May 1994.
• 32: Dharmendra S. Modha , W. Scott Spangler, Clustering hypertext with applications to web searching, Proceedings of the eleventh ACM on Hypertext and hypermedia, p.143-152, May 30-June 03, 2000, San Antonio, Texas, United States [doi>10.1145/336296.336351]
• 33: Gopal Pandurangan , Prabhakar Raghavan , Eli Upfal, Using PageRank to Characterize Web Structure, Proceedings of the 8th Annual International Conference on Computing and Combinatorics, p.330-339, August 15-17, 2002
• 34: Peter Pirolli , James Pitkow , Ramana Rao, Silk from a sow's ear: extracting usable structures from the Web, Proceedings of the SIGCHI conference on Human factors in computing systems: common ground, p.118-125, April 13-18, 1996, Vancouver, British Columbia, Canada [doi>10.1145/238386.238450]
• 35: James Pitkow , Peter Pirolli, Life, death, and lawfulness on the electronic frontier, Proceedings of the SIGCHI conference on Human factors in computing systems, p.383-390, March 22-27, 1997, Atlanta, Georgia, United States [doi>10.1145/258549.258805]
• 36: Krishna Bharat , Bay-Wei Chang , Monika Rauch Henzinger , Matthias Ruhl, Who Links to Whom: Mining Linkage between Web Sites, Proceedings of the 2001 IEEE International Conference on Data Mining, p.51-58, November 29-December 02, 2001
• 37: RuleQuest Research. Data Mining Tools See5 and C5.0. http://www.rulequest.com/see5-info.html.
• 38: H. Small. Co-citation in the scientific literature: A new measure of the relationship between two documents. J. American Soc. Info. Sci., 24:265--269, 1973.
• 39: Ron Weiss , Bienvenido Vélez , Mark A. Sheldon, HyPursuit: a hierarchical network search engine that exploits content-link hypertext clustering, Proceedings of the the seventh ACM conference on Hypertext, p.180-193, March 16-20, 1996, Bethesda, Maryland, United States [doi>10.1145/234828.234846]

INDEX TERMS

Primary Classification:
  H. Information Systems
  H.3 INFORMATION STORAGE AND RETRIEVAL
      H.3.1 Content Analysis and Indexing
          Subjects: Indexing methods

Additional Classification:
  H. Information Systems
  H.3 INFORMATION STORAGE AND RETRIEVAL
      H.3.3 Information Search and Retrieval
          Subjects: Clustering; Information filtering; Selection process

General Terms:
Algorithms, Experimentation, Measurement

Keywords:
link analysis, web IR, web graphs