Pomiary grafu WWW

• Autorzy: Sydow M.
• Języki publikacji: PL

Abstrakty

PL

Publikacja niniejsza opisuje wybór wyników dokonanych przez autora pomiarów pewnych globalnych własności grafu www, takich jak: rozkłady stopni wejściowych i wyjściowych, PageRank oraz wzajemnych związków między tymi rozkładami. Graf taki otrzymuje się traktując każdy dokument HTML jako wierzchołek grafu, a każdy hiperlink jako jego krawędź skierowaną. Wyniki podobnych pomiarów były już publikowane w literaturze naukowej w ciągu ostatnich kilku lat, jednak referat niniejszy pokazuje, że rozkłady wydają się mieć nieco inne parametry niż zwykle jest to cytowane. Ponadto pokazane są ciekawe wyniki dotyczące silnego związku stopnia wejściowego z wyjściowym, które nie były do tej pory publikowane. Eksperymenty przeprowadzone przez autora są jednymi z pierwszych tego typu w Polsce, a wielkości mierzonych próbek są jednymi z najwyższych w skali światowej. Opisywane własności grafu WWW mają, poza walorem poznawczym, wymiar praktyczny związany z projektowaniem inteligentnych systemów wyszukiwania informacji w WWW, w szczególności tzw. „crawlerów” i repozytoriów dokumentów HTML.

Słowa kluczowe

PL

graf WWW; rozkład stopni wejściowych; rozkład stopni wyjściowych; badania eksperymentalne

• Wydawca: Wydawnictwo Uniwersytetu Przyrodniczo-Humanistycznego w Siedlcach
• Czasopismo: Studia Informatica : systems and information technology
• Rocznik: 2004
• Tom: Vol. 1(3)
• Strony: 51--58
• Opis fizyczny: Bibliogr. 9 poz., wykr.

Twórcy

autor

Sydow M.

• Polsko-Japońska Wyższa Szkoła Technik Komputerowych

Bibliografia

• [1] L. Adamic: Zipf, Power-Laws, and Pareto a ranking tutorial.
• [2] T.Haveliwala: Efficient Computation of PageRank, Stanford University Report, 1999.
• [3] J.M.KIeinberg, R. Kumar, P.Raghavan, S.Rajagopalan, A.Tomkins: The Web As a graph: measurements, models and methods. Proceedings of 5 th Annual International Computing and Combinatorics Conference, 1999.
• [4] M.A.Kłopotek, M.Sydow: Uncorrelating PageRank and In-Degree in a Synthetic Web Model, zaakceptowane do druku w: Lecture Notes of Computer Science, Springer Verlag, Proceedings of ISCIS 2003, Antalya, Turcja, 2003.
• [5] R.Kumar, P.Raghavan, S.Rajagopalan, D.Sivakumar, A.Tomkins, E.Upfal: Stochastic Models for the Web. Proceedings of the 41st Annual Symposium on the Foundations of Computer Science, 2000.
• [6] R.Kumar, P.Raghavan, S.Rajagopalan, A.Tomkins: Trawling the Web for emerging cyber-communities, 8th International WWW Conference, 1999.
• [7] L.Page, S.Brin, , R.Motwani, T.Winograd: the PageRank Citation Ranking. Bringing order to the Web, Technical Report, Computer Science Department, Stanford University, 1998.
• [8] G.Pandurangan, P.Raghavan, E.Upfal: Using PageRank to Characterize Web Structure. Computer Science Department, Brown University, Providence, USA, 2002.
• [9] K.H.Randall, R.Stata, R.G.Wickremesinghe, J.L.Wiener: The Link Database. Fast Access to Graphs of the Web, 2000.