Wyniki wyszukiwania - BazTech

1

An efficient Monte Carlo approach to compute PageRank for large graphs on a single PC

Sonobe T.

Foundations of Computing and Decision Sciences

|

2016

|

Vol. 41, No. 1

29--43

EN

This paper describes a novel Monte Carlo based random walk to compute PageRanks of nodes in a large graph on a single PC. The target graphs of this paper are ones whose size is larger than the physical memory. In such an environment, memory management is a difficult task for simulating the random walk among the nodes. We propose a novel method that partitions the graph into subgraphs in order to make them fit into the physical memory, and conducts the random walk for each subgraph. By evaluating the walks lazily, we can conduct the walks only in a subgraph and approximate the random walk by rotating the subgraphs. In computational experiments, the proposed method exhibits good performance for existing large graphs with several passes of the graph data.

2

Accelerating PageRank computations

Wierzchoń S. T., Kłopotek M. A., Ciesielski K., Czerski D., Dramiński M.

Control and Cybernetics

|

2011

|

Vol. 40, no 2

259-274

EN

Different methods for computing PageRank vectors are analysed. Particularly, we note the opposite behavior of the power method and the Monte Carlo method. Further, a method of reducing the number of iterations of the power method is suggested.

3

“CRAWL.PL” Measuring Statistical and Structural Properties of the Polish Web : Technical Report

Castillo C., Starosta B., Sydow M.

Studia Informatica : systems and information technology

|

2007

|

Vol. 1(8)

43--73

EN

This document summarizes the results of an experiment made in the Polish-Japanese Institute of Information Technology, Warsaw, Poland during autumn 2005 and winter 2006. The goal of the project was to collect and analyze large portion of Polish Web documents in order to characterize the structure and other properties of the „.pl” domain. Up to the knowledge of the authors, it was the first publicly reported research experiment of this kind over the Polish Web. The following sections include information about downloaded Web pages, Web sites, and their characteristics. We also present various statistics concerning hosts and domains, as well as the link structure. Among the results of the experiment are the first data sets representing graphs of the Polish Web which will be publicly available for other researchers.

4

Random Surfer with Back Step

Sydow M.

Fundamenta Informaticae

|

2005

|

Vol. 68, nr 4

379--398

EN

The World Wide Web with its billions of hyperlinked documents is a huge and important resource of information. There is a necessity of filtering this information. Link analysis of the Web graph turned out to be a powerful tool for automatically identifying authoritative documents. One of the best examples is the PageRank algorithm used in Google [1] to rank search results. In this paper we extend the model underlying the PageRank algorithm by incorporating "back button'' usage modeling in order to make the model less simplistic. We explain the existence and uniqueness of the ranking induced by the extended model. We also develop and implement an efficient approximation method for computing the novel ranking and present succesful experimental results made on 80- and 50- million page samples of the real Web.

5

Synthetic Web

Kłopotek M.

Prace Instytutu Podstaw Informatyki Polskiej Akademii Nauk

|

2003

|

Nr 954

1-14

EN

We got used to the idea that Web is a collection of interlinked documents containing knowledge from almost all areas of human activity. Recent research points however that the very structure of WWW links may by its own be a rich source of diverse knowledge. Understanding of rules for Web structure and growth may have immense impact in diverse research areas, starting with theory of structure and dynamics of massive graphs, utilitarian search for effective search algorithms on WWW, to the psychological research on formation of social communities and detection of such communities on the Internet. Currently the mainstream research concentrates apparently on construction of simple models helping to explain various basic statistical phenomena observed on the Web. This paper briefly explains major models of the Web and recalls basic contradictions between properties of synthetic Web and the real Web. It also offers a way to resolve one such contradiction concerning the high correlation between PageRank and in-degrees in synthetic Web models, while such a correlation is not present in real Web.

PL

Przyzwyczailiśmy się do traktowania sieci WWW jako zbioru dokumentów zawierających wiedzę prawie ze wszystkich dziedzin naszego życia . Ostatnie badania zdają się wskazywać, że równie głębokim źródłem wiedzy może być sama struktura sieci WWW. Zrozumienie struktury i ewolucji sieci dokumentów na WWW może mieć kolosalne znaczenie dla wielu dziedzin-począwszy od badań naqd strukturą i dynamiką wielkich grafów poprzez utilitarne badania nad efektywnością programów przeczesujących sieć WWW aż po psychologiczne badania nad powstawaniem grup społecznych czy też wykrywaniem takich grup. W chwili obecnej główny nurt badań nad strukturą i rozwojem WWW skupia się na konstruowaniu prostych modeli pozwalających wyjaśnić podstawowe statystyczne własności sieci WWW. W niniejszym artykule przedstawiono ważniejsze koncepcje modelu sieci WWW i wskazano na sprzeczności między miarami rzeczywistej sieci WWW a jej syntetycznymi modelami. Zaproponowano sposób obejścia jednej z takich sprzeczności, jaką jest wysoka korelacja między PageRankiem a stopniem wejściowym stron WWW w sieciach syntetycznych, oraz brakiem takiej korelacji w rzeczywistej sieci WWW.