Звіт до компʼютерного проєкту на тему «PageRank algorithm» Команда 19
Проєкт є реалізацією алгоритму оцінки важливості веб-сторінок, базуюючись на кількості посилань на кожну сторінку. Чим їх більше, тим важливіша сторінка. Для зображення мережі використовується орієнтований граф, де вершини — це сторінки, а ребра — це звʼязки між ними. Тому для виконання роботи було використано знання з теорії графів.
У коді використано принципи ООП:
-
class Node — опрацювання кожної сторінки у вигляді вершини. Методи: a) init(self, name: str): ініціалізує вершину з іменем, прирівнює початковий рейтинг сторінки до 1 та створює порожні списки для «parents» та «children». «Parents» («батьки») —«in-neighbors» вершини, тобто вершини, з яких виходять ребра інцидентні вершині «Node». «Children» («діти») —«out-neighbors» вершини, тобто вершини, які інцидентні ребрам, що виходять з вершини «Node». b) get_name(self) -> str: повертає назву вершини. c) get_pagerank(self) -> float: повертає поточний PageRank сторінки (вершини). d) get_children(self) -> list: повертає список «children» вершин. e) get_parents(self) -> list: повертає список «parents» вершин. f) set_pagerank(self, pagerank: float): задає PageRank сторінки (вершини). g) add_child(self, child): додає «children» вершину до поточної. h) add_parent(self, parent): додає «parents» вершину до поточної. i) update_pagerank(self, damp: float, num: int): оновлює PageRank вершини, базуючись на її суміжних вершинах та коефіцієнті демпфування.
-
class Graph —управління структурою графа. a) init(self, file_name: str): ініціалізує граф, зчитуючи його з файлу за допомогою методу read_graph. Програма працює з графами заданими у форматі: node->node node->node node->node b) get_children(self, node: str) -> list: повертає список «children» вершин для заданої вершини. c) get_parents(self, node: str) -> list: повертає список «parents» вершин для заданої вершини. d) create_unique_node(self, name: str) -> Node: створює унікальну вершину за заданою назвою або повертає вершину, якщо така назва вже існує. e) add_edge(self, node1: str, node2: str): додає ребро між двома вершинами. f) read_graph(self, file_name: str) -> dict: зчитує орієнтований граф з файлу та повертає словник з усіма суміжними вершинами. g) normalize_pageranks(self): нормалізує значення PageRank для всіх вершин у графі. h) get_pageranks(self) -> list: заокруглює значення PageRank для всіх вершин та повертає їх списком.
-
Функція pagerank_iter(graph, damp) Функція виконує одну ітерацію алгоритму, проходячись по всіх вершинах графа і оновлюючи їх значення (update_pagerank) та нормалізуючи їх (normalize_pageranks). Graph — це заданий граф, damp — це коефіцієнт демпфування (0.15 — класичний випадок для PageRank).
-
main: Створюється обʼєкт класу Graph при зчитанні з файлу. Алгоритм повторюється задану кількість ітерацій (у цьому випадку 100). Виводиться PageRank для кожної вершини.
Робота виконувалась повністю у команді без поділу на окремі процеси, оскільки PageRank - це цілісний алгоритм.