Assessment of ranking algorithms in complex networks

• Autorzy: Wołoszyn P.

Warianty tytułu

PL

Algorytmy rankingu w sieciach złożonych

• Języki publikacji: EN

Abstrakty

EN

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.

Słowa kluczowe

EN

link analysis; web search; HITS algorithm; Kleinberg’s HITS algorithm; Page rank algorithm; SALSA algorithm; hubs; authorities

PL

analiza linków; przeszukiwanie sieci Web; HITS; PageRank; SALSA; autorytet; koncentratory

• Wydawca: Institute of Computer and Information Systems, Faculty of Cybernetics, Military University of Technology
• Czasopismo: Computer Science and Mathematical Modelling
• Rocznik: 2017
• Tom: No. 5
• Strony: 41--51
• Opis fizyczny: bibliogr. 12 poz., rys., tab.

Twórcy

autor

Wołoszyn P.

• Military University of Technology, Faculty of Cybernetics Institute of Computer and Information Systems Kaliskiego Str. 2, 00-908 Warsaw, Poland

Bibliografia

• 1. Markov Z., Larose D., Eksploracja zasobów internetowych, Wydawnictwo Naukowe PWN, Warszawa 2009.
• 2. Fronczak A., Fronczak P., Świat sieci złożonych. Od fizyki do internetu, Wydawnictwo Naukowe PWN, Warszawa 2009.
• 3. Lay D.C., Linear Algebra and Its Applications, Addison-Wesley, 2000.
• 4. Kleinberg Jon M., “Authoritative sources in a hyperlinked environment”, Journal of the ACM (JACM), 46.5: 604–632 (1999).
• 5. Farahat A., LoFaro T., Miller J.C., Rae G., and Ward L., “Authority Rankings from HITS, PageRank, and SALSA: Existence, Uniqueness, and Effect of Initialization”, SIAM J. Sci. Comput., 27(4), 1181–1201 (2006).
• 6. Borodin A., Roberts G.O., Rosenthal J.S., Tsaparas P., Link Analysis Ranking Algorithms Theory And Experiments, The Pennsylvania State University, 2005.
• 7. Page L., Brin S., Motwani R., Winograd T., The PageRank Citation Ranking: Bringing Order to the Web. Technical Report, Computer Science Department, Stanford University, 1998.
• 8. Brin S., Page L., The anatomy of a large-scale hypertextual Web search engine, Computer Networks and ISDN Systems, 1998.
• 9. Langville A.N., Meyer C.D., “Deeper Inside PageRank”, Internet Mathematics, February 2004.
• 10. Kamvar S., Haveliwala T., Golub G., Adaptive Methods for the Computation of PageRank. Technical Report, Computer Science Department, Stanford University, 2003.
• 11. Kamver S., Haveliwala T., Manning C., Golub G., Exploiting the block structure of the web for computing PageRank. Tech. Rep. SCCM03-02, Stanford University, http://www-sccm.stanford.edu/nfpublicationstech.html, 2003.
• 12. Berry W.M. and Browne M., Understanding Search Engines: Mathematical Modeling and Text Retrieval, SIAM, Philadelphia, 2nd edition, 2005.