A particularly helpful search of a network such as the Internet or a citation network not only finds nodes that satisfy some criteria but also ranks those nodes for importance to create what amounts to a “reading list”. In the recent past, there has been a large interest across a number of research communities in the analysis of complex networks. The selected set of pages from the World Wide Web can be modeled as a directed graph, where nodes are designated as individual pages, and the links as a connection between them. As the number of webpages to be ranked is in the billions, the computation is time-consuming and can take several days or more. Algorithms like PageRank, HITS, SALSA and their modifications has a challenge to deal with the size of the processed data. The need for accelerated algorithms is clear. This article presents the characteristics of three best known ranking algorithms and the assumptions for new algorithm development with first test runs.
PL
W ostatnich latach zaobserwować można duże zainteresowanie środowisk naukowych obszarem sieci złożonych. Zbiór stron z sieci World Wide Web można zamodelować jako graf skierowany, gdzie węzły są wyznaczone jako poszczególne strony, a linki jako połączenie pomiędzy nimi. Liczba stron internetowych, które biorą udział w rankingu, podana jest w miliardach, zatem obliczenia są czasochłonne, uzależnione od użytych algorytmów oraz oczekiwanego stopnia dokładności. Algorytmy takie jak PageRank, HITS, SALSA i ich modyfikacje mają do czynienia z problemem ilości przetwarzanych danych. Dlatego potrzebne są nowe narzędzia, wydajne obliczeniowo w szczególności w oparciu o analizy sieci dla wspólnego rankingu wszystkich węzłów. W prezentowanym artykule przedstawiam charakterystykę trzech najbardziej znanych algorytmów rankingu oraz propozycję założeń do opracowania nowego algorytmu wraz z pierwszymi testami na zestawie realnych danych.
Nowadays it is more and more common to treat the Internet as one of the first sources of information. Given key words, different types of web search engines generate a list of websites ranked by priority (theoretically corresponding to the query). The page position on the list depends on many factors. The method presented herein is a version of a PageRank algorithm introduced by Google to designate one of them. The PageRank algorithm ranks a webpage, depending on the number and quality of links leading to it and thus determines its position on the list. In its simplest version, the method can operate using just the basic operations on matrices. This paper presents also the more advanced version based on probabilistic approach.
In this paper the challenges in building good search engines are discussed. Many of the search engines use well-known information retrieval algorithms and techniques. They use Web crawlers to maintain their index databases amortizing the cost of crawling and indexing over the millions of queries received by them. Web crawlers are programs that exploit the graph structure of the Web to move from page to page. Paper analyses the PageRank algorithm one of these Web crawlers. The results of the impact of the PageRank parameter value on the effectiveness of determining the so-called PageRank vector are considered in the paper. Investigations are illustrated by means of the results of a some simulation experiments to analyze the PageRank algorithm efficiency for different density graph (representing analyzed part of www) coefficient values.
JavaScript jest wyłączony w Twojej przeglądarce internetowej. Włącz go, a następnie odśwież stronę, aby móc w pełni z niej korzystać.