Przejdź do treści

Pagerank

Algorytm PageRank

Poniższa prosta implementacja bazuje na wzorze z Wikipedii. Funkcja pagerank wykonuje jeden krok iteracji.

In [1]:
DAMPING_FACTOR = 0.85

class Page:
    def __init__(self, links_to):
        self.rank = 1
        self.old_rank = 1
        self.links_to = links_to

def pagerank(pages_dict):
    for page in pages_dict.values():
        page.old_rank = page.rank
        page.rank = (1 - DAMPING_FACTOR) / len(pages_dict)
        
    for page in pages_dict.values():
        for linked_page in [pages_dict[x] for x in page.links_to]:
            linked_page.rank += DAMPING_FACTOR * page.old_rank / len(page.links_to)

def print_ranks(pages_dict):
    for page in pages_dict:
        print(f'{page}: {pages_dict[page].rank}')

Poniżej dane jak dla przykładu nr 1 z Wikipedii.

In [2]:
pages = {
    'a': Page(['b', 'd']),
    'b': Page(['a']),
    'c': Page(['a', 'b']),
    'd': Page(['c'])
}

Co na grafie wyglądałoby następująco:

Graf stron

Po ok. 50 iteracjach dla ww. przykładu i współczynnika tłumienia 0.85 algorytm osiąga zbieżność - dla prostoty pominięto tutaj automatyczne wykrywanie zbieżności.

In [3]:
print('Stan początkowy:')
print_ranks(pages)
print()

for i in range(50):
    pagerank(pages)
    if (i % 10 == 9):
        print(f'Iteracja: {i}')
        print_ranks(pages)
        print()
Stan początkowy:
a: 1
b: 1
c: 1
d: 1

Iteracja: 9
a: 0.5623505353694931
b: 0.4322265791660144
c: 0.30132085774026984
d: 0.2947252407463905

Iteracja: 19
a: 0.3916088772144747
b: 0.300838981044389
c: 0.21669762713552462
d: 0.20713310785915465

Iteracja: 29
a: 0.3576758940722046
b: 0.2753391284358139
c: 0.19974025093782935
d: 0.19013700533852065

Iteracja: 39
a: 0.3509906847352029
b: 0.27032448040044704
c: 0.1963977759047993
d: 0.18679396270922516

Iteracja: 49
a: 0.349674468643652
b: 0.26933730738408623
c: 0.1957396697721065
d: 0.1861358481912935

Konwersja do grafu RDF

In [4]:
def page_iri(page_name):
    return f'<http://{page_name}.com>'

LINK_IRI = '<http://example.com/links_to>'

def page_dict_to_ntriples_file(page_dict, filename):
    with open(filename, 'w') as f:
        for page_name in page_dict:
            for linked_page in page_dict[page_name].links_to:
                print(page_iri(page_name), LINK_IRI, page_iri(linked_page), '.', file=f)
In [5]:
page_dict_to_ntriples_file(pages, 'pages.nt')

Uruchomienie PageRank w CGE

Wystarczy odpowiednio spreparowane zapytanie w (rozszerzonym) SPARQL:

prefix cray: <http://cray.com/>

select ?vertices ?pagerank where {
    construct {
        ?sub ?pred ?obj .
    } where {
        ?sub ?pred ?obj
    }
    invoke cray:graphAlgorithm.pagerank(0.0005, 0.85)
    producing ?vertices ?pagerank
}
order by desc(?pagerank)

Warto zwrócić uwagę na to, jak w klauzuli invoke przekazano do algorytmu parametry liczbowe.

Przykładowy wynik z CGE w formacie TSV:

?vertices   ?pagerank
<http://a.com>  "1"^^<http://www.w3.org/2001/XMLSchema#double>
<http://b.com>  "0.7704550561822686"^^<http://www.w3.org/2001/XMLSchema#double>
<http://c.com>  "0.559802417230212"^^<http://www.w3.org/2001/XMLSchema#double>
<http://d.com>  "0.532450808488539"^^<http://www.w3.org/2001/XMLSchema#double>

Są to identyczne wartości, jak wyliczone wcześniej, ale znormalizowane tak, aby strona z najwyższym wynikiem miała wartość 1.

Odtworzenie powyższych wyników

Do odtworzenie poniższych wyników wymagane jest wyczyszczenie katalogu zawierającego dane wejściowe do CGE oraz skopiowanie tam nowego pliku z danymi.

Przed czyszczeniem katalogu trzeba zamknąć proces CGE, a po skopiowaniu nowych danych należy uruchomić bazę ponownie.

Czyszczenie oraz skopiowanie pliku można zrobić następującymi komendami:

cd ~
rm cge/db/*
cp notebooki/pages.nt cge/db/dataset.nt

Ostatnia aktualizacja: May 18, 2021
Ta strona używa plików cookies.
Polityka Prywatności    AKCEPTUJĘ