Abstract
We propose a technique for identifying latent Web communities based solely on the hyperlink structure of the WWW, via random walks. Although the topology of the Directed Web Graph encodes important information about the content of individual Web pages, it also reveals useful meta-level information about user communities. Random walk models are capable of propagating local link information throughout the Web Graph, which can be used to reveal hidden global relationships between different regions of the graph. Variations of these random walk models are shown to be effective at identifying latent Web communities and revealing link topology. To efficiently extract these communities from the stationary distribution defined by a random walk, we exploit a computationally efficient form of directed spectral clustering. The performance of our approach is evaluated in real Web applications, where the method is shown to effectively identify latent Web communities based on link topology only.
Chapter PDF
Similar content being viewed by others
Keywords
These keywords were added by machine and not by the authors. This process is experimental and the keywords may be updated as the learning algorithm improves.
References
Chakrabarti, S., Gibson, D., Kumar, R., Raghavan, P., Rajagopalan, S., Tomkins, A.: Spectral filtering for resource discovery. In: ACM SIGIR workshop on Hypertext Information Retrieval on the Web (1998)
Chung, F.: Spectral Graph Theory. American Mathematical Society (1997)
Ding, C., He, X., Husbands, P., Zha, H., Simon, H.: PageRank, HITS and a unified framework for link analysis. Technical report, LBNL (2002)
Flake, G., Lawrence, S., Giles, C.L.: Efficient identification of web communities. In: ACM SIGKDD (2000)
Flake, G., Lawrence, S., Giles, C.L., Coetzee, F.: Self-organization and identification of web communities. IEEE Computer, Los Alamitos (2002)
Gibson, D., Kleinberg, J., Raghavan, P.: Inferring web communities from link topology. In: UK Conference on Hypertext (1998)
Henzinger, M.: Hyperlink analysis for the web. IEEE Internet Computing (2001)
Ino, H., Kudo, M., Nakamura, A.: Partitioning of web graphs by community topology. In: WWW (2005)
Kessler, M.: Bibliographic coupling between scientific papers. In: American Documentation (1963)
Kleinberg, J.: Authoritative sources in a hyperlinked environment. JACM (1999)
Lempel, R., Moran, S.: The stochastic approach for link-structure analysis (salsa) and the tkc effect. In: WWW, pp. 387–401 (2000)
Page, L., Brin, S., Motwani, R., Winograd, T.: The PageRank citation ranking: Bringing order to the web. Technical report, Stanford Digital Library Technologies Project (1998)
Perona, P., Freeman, W.: A factorization approach to grouping. In: Burkhardt, H.-J., Neumann, B. (eds.) ECCV 1998. LNCS, vol. 1406, pp. 655–670. Springer, Heidelberg (1998)
Shi, J., Malik, J.: Normalized cuts and image segmentation. In: IEEE PAMI (2000)
Small, H.: Co-citation in the scientific literature: A new measure of the relationship between two documents. JASIS (1973)
Zhou, D., Huang, J., Scholkopf, B.: Learning from labeled and unlabeled data on a directed graph. In: ICML (2005)
Author information
Authors and Affiliations
Editor information
Editors and Affiliations
Rights and permissions
Copyright information
© 2006 Springer-Verlag Berlin Heidelberg
About this paper
Cite this paper
Huang, J., Zhu, T., Schuurmans, D. (2006). Web Communities Identification from Random Walks. In: Fürnkranz, J., Scheffer, T., Spiliopoulou, M. (eds) Knowledge Discovery in Databases: PKDD 2006. PKDD 2006. Lecture Notes in Computer Science(), vol 4213. Springer, Berlin, Heidelberg. https://doi.org/10.1007/11871637_21
Download citation
DOI: https://doi.org/10.1007/11871637_21
Publisher Name: Springer, Berlin, Heidelberg
Print ISBN: 978-3-540-45374-1
Online ISBN: 978-3-540-46048-0
eBook Packages: Computer ScienceComputer Science (R0)