A methodology for the evaluation of web graph models and a test case
Pages 2202 - 2209
Abstract
Valid models of the WWW are important for creating WWW-like representations, upon which new algorithms and applications for searching, indexing, compression etc. can be tested, but also for predicting the evolution of the web and the emergence of important new phenomena. In this study we introduce a validation process for web-graph models and use it to analyze the behavior of the Exponential Growth Copying Model, which has been explicitly designed to model the WWW. We study the effect of individual parameters on its effectiveness, suggest appropriate parameter values for the creation of web-like graphs and indicate inherent deficiencies of the model.
References
[1]
Adler, M., and M. Mitzenmacher. 2001. Towards compressing web graphs. Proceedings of the IEEE Data Compression Conference, 203--212.
[2]
Barabasi, A., and R. Albert. 1999. Emergence of scaling in random networks. Science 286, 509--512.
[3]
Brin, S. and Page L. 1998. The anatomy of a large-scale hypertextual web search engine. Proceedings of the 7th WWW Conference.
[4]
Broder, A., R. Kumar, F. Maghoul, P. Raghavan, S. Rajagopalan, R. Stata, A. Tomkins, and J. Wiener. 2000. Graph structure in the web: Experiments and models. Proceedings of the 9th WWW Conference, 309--320.
[5]
Bu, T. and D. Towsley. 2002. On distinguishing between Internet power-law topology generators. Proceedings of the 25th Conference on Computer Communications (INFOCOM 2002).
[6]
Faloutsos, M., P. Faloutsos and C. Faloutsos 1999. On power-law relationships of the Intenet topology. Proceedings of the Annual Conference of the ACM Special Interest Group on Data Communication (ACM SIGCOMM '99).
[7]
Kleinberg, J. 1998. Authoritative sources in a hyperlinked environment. Proceedings of the 9th Annual ACM-SIAM Symposium on Discrete Algorithms, 668--677.
[8]
Kleinberg, J., R. Kumar, P. Raghavan, S. Rajagopalan, and A. Tomkins. 1999. The web as a graph: Measurements, models and methods. Proceedings of the International Conference on Combinatorics and Computing, 1--18.
[9]
Kogias, A., M. Nikolaidou, and D. Anagnostopoulos. 2005. Modelling and simulation of the web graph: evaluating an exponential growth copying model. International Journal of Web Engineering and Technology Vol. 2 No 1, 29--49.
[10]
Kumar, R., P. Raghavan, S. Rajagopalan, and A. Tomkins. 1999a. Trawling the web for emerging cyber-communities. Proceedings of the 8th WWW Conference, 403--416.
[11]
Kumar, R., P. Raghavan, S. Rajagopalan and A. Tomkins. 1999. Extracting large-scale knowledge bases from the web. Proceedings 25th VLDB Conference, 639--650.
[12]
Kumar, R., P. Raghavan, S. Rajagopalan, D. Sivakumar, A. Tomkins, and E. Upfal. 2000. Stochastic models for the web graph. Proceedings of the 41st Annual Symposium on Foundations of Computer Science.
[13]
Laura, L., S. Leonardi, G. Caldarelli, and P. De Los Rios. 2002. A multi-layer model for the web graph. Proceedings of the 2nd International Workshop on Web Dynamics.
[14]
Matsumoto, M. and T. Nishimura. 1998. Mercenne Twister: a 623-dimensionally equidistributed uniform pseudo-random number generator. ACM Transactions on Modeling and Computer Simulation 8(1), pp. 3--30.
[15]
Tangmunarunkit, H., R. Govindan, S. Jamin, S. Shenker, and W. Willinger. 2002. Network topology generators: degree-based vs structural. Proceedings of the Annual Conference of the ACM Special Interest Group on Data Communication (SIGCOMM '02).
- A methodology for the evaluation of web graph models and a test case
Recommendations
Stochastic models for the Web graph
FOCS '00: Proceedings of the 41st Annual Symposium on Foundations of Computer ScienceThe Web may be viewed as a directed graph each of whose vertices is a static HTML Web page, and each of whose edges corresponds to a hyperlink from one Web page to another. We propose and analyze random graph models inspired by a series of empirical ...
A Graph based Methodology for Web Structure Mining - with a Case Study on the Webs of UK Universities
WIMS '14: Proceedings of the 4th International Conference on Web Intelligence, Mining and Semantics (WIMS14)Web structure mining is to extract knowledge from the hyperlink structure data of world wide webs for improving web design for clear content presentation and easy navigation. This paper presents a graph-based methodology for web structure mining. The ...
China web graph measurements and evolution
APWeb'05: Proceedings of the 7th Asia-Pacific web conference on Web Technologies Research and DevelopmentWith the huge number of Web pages on the World Wide Web, there are many characteristics that should be analyzed in the Web mining fields. As a subset of the global Web graph, China Web graph shows many different properties compared with the global Web ...
Comments
Information & Contributors
Information
Published In
December 2006
2429 pages
ISBN:1424405017
- Editors:
- L. Felipe Perrone,
- Barry G. Lawson,
- Jason Liu,
- Frederick P. Wieland,
- General Chair:
- David Nicol,
- Program Chair:
- Richard Fujimoto
Sponsors
- IIE: Institute of Industrial Engineers
- ASA: American Statistical Association
- IEICE ESS: Institute of Electronics, Information and Communication Engineers, Engineering Sciences Society
- IEEE-CS\DATC: The IEEE Computer Society
- SIGSIM: ACM Special Interest Group on Simulation and Modeling
- NIST: National Institute of Standards and Technology
- (SCS): The Society for Modeling and Simulation International
- INFORMS-CS: Institute for Operations Research and the Management Sciences-College on Simulation
Publisher
Winter Simulation Conference
Publication History
Published: 03 December 2006
Check for updates
Qualifiers
- Article
Conference
WSC06
Sponsor:
- IIE
- ASA
- IEICE ESS
- IEEE-CS\DATC
- SIGSIM
- NIST
- (SCS)
- INFORMS-CS
Acceptance Rates
WSC '06 Paper Acceptance Rate 177 of 252 submissions, 70%;
Overall Acceptance Rate 3,413 of 5,075 submissions, 67%
Contributors
Other Metrics
Bibliometrics & Citations
Bibliometrics
Article Metrics
- 0Total Citations
- 160Total Downloads
- Downloads (Last 12 months)0
- Downloads (Last 6 weeks)0
Reflects downloads up to 07 Mar 2025
Other Metrics
Citations
View Options
Login options
Check if you have access through your login credentials or your institution to get full access on this article.
Sign in