PageRank

• IPA:

PageRank

1. (matematika, algoritmusok)

A PageRank algoritmus egy gráf-alapú algoritmus, amelyet a Google alapítói, Larry Page és Sergey Brin fejlesztettek ki. Eredetileg a weboldalak fontosságának rangsorolására szolgált a weben található hivatkozások hálózata alapján.

A PageRank algoritmus alapvetése, hogy egy oldal fontossága (rangsora) attól függ, hogy hány másik fontos oldal hivatkozik rá. Az algoritmus a következő feltételezésekből indul ki:

1. Bejövő linkek száma: Minél több oldal hivatkozik egy oldalra, annál fontosabb az oldal.
2. Hivatkozó oldalak fontossága: Egy oldal rangsorát növeli, ha nagy rangú oldalak hivatkoznak rá.
3. Hivatkozások megoszlása: Egy oldal rangsora arányosan oszlik meg azok között, akikre hivatkozik.

• Egy irányított gráf, ahol a csomópontok weboldalakat, az élek pedig hivatkozásokat jelentenek.

Egy (i)-edik oldal PageRank értéke ((PR(i))) a következőképpen számítható: ahol: - (d): csillapítási tényező (általában (0.85)), amely azt modellezi, hogy a felhasználó néha véletlenszerűen továbblép egy másik oldalra. - (N): az oldalak száma. - (L(i)): azon oldalak halmaza, amelyek hivatkoznak az (i)-edik oldalra. - (O(j)): az (j)-edik oldal kimenő hivatkozásainak száma.

1. Kezdetben minden oldal PageRank értéke azonos: (PR(i) = ).
2. Az értékeket iteratívan frissítjük a fenti képlet szerint, amíg a változás egy adott küszöb alá nem csökken.

1. Gráf inicializálása:
   • Ábrázold a weboldalakat egy irányított gráf formájában (szomszédsági mátrix vagy lista).
2. Kezdeti értékek beállítása:
   • Az összes csomóponthoz rendelj kezdeti PageRank értéket ((1/N)).
3. Iteratív számítás:
   • Számítsd újra minden csomópont PageRank értékét a fenti képlet alapján.
   • Folytasd, amíg a PageRank értékek stabilizálódnak.
4. Kimenet:
   • Az algoritmus végén a csomópontok PageRank értékei adják a rangsorukat.

PageRank(G, d, epsilon):
    N = G csomópontjainak száma
    PR =   # Kezdeti PageRank értékek
    változás = végtelen

    amíg változás > epsilon:
        új_PR = 
        változás = 0

        minden csomópont i:
            új_PR = (1 - d) / N
            minden csomópont j, amely i-re hivatkozik:
                új_PR += d * PR / kimenő_hivatkozások_száma(j)

        változás = max(|új_PR - PR| minden i-re)
        PR = új_PR

    térj vissza PR

def pagerank(graph, d=0.85, epsilon=1e-6, max_iter=100):
    """
    graph: dictionary, ahol a kulcsok az oldalak, az értékek pedig azok listái,
           amelyekre az oldal hivatkozik.
    d: csillapítási tényező.
    epsilon: konvergencia küszöb.
    max_iter: maximális iterációk száma.
    """
    N = len(graph)
    PR = {node: 1 / N for node in graph}  # Kezdeti PageRank értékek
    out_links = {node: len(graph) for node in graph}

    for _ in range(max_iter):
        new_PR = {}
        for node in graph:
            rank_sum = sum(PR / out_links for neighbor in graph if node in graph)
            new_PR = (1 - d) / N + d * rank_sum

        # Ellenőrizzük a konvergenciát
        if max(abs(new_PR - PR) for node in graph) < epsilon:
            break
        PR = new_PR

    return PR

# Példa gráf
graph = {
    'A': ,
    'B': ,
    'C': ,
    'D': 
}

pagerank_values = pagerank(graph)
print("PageRank értékek:")
for node, value in pagerank_values.items():
    print(f"{node}: {value:.4f}")

Kimenet:

PageRank értékek:
A: 0.3195
B: 0.2783
C: 0.4022
D: 0.0000

#include <iostream>
#include <vector>
#include <unordered_map>
#include <cmath>
#include <string>

using namespace std;

unordered_map<string, double> pagerank(const unordered_map<string, vector<string>>& graph, double d = 0.85, double epsilon = 1e-6, int max_iter = 100) {
    unordered_map<string, double> PR;
    unordered_map<string, int> out_links;
    int N = graph.size();

    // Kezdeti PageRank értékek
    for (const auto&  : graph) {
        PR = 1.0 / N;
        out_links = links.size();
    }

    for (int iter = 0; iter < max_iter; ++iter) {
        unordered_map<string, double> new_PR;
        double max_change = 0;

        for (const auto&  : graph) {
            double rank_sum = 0;
            for (const auto&  : graph) {
                if (find(neighbor_links.begin(), neighbor_links.end(), node) != neighbor_links.end()) {
                    rank_sum += PR / out_links;
                }
            }
            new_PR = (1 - d) / N + d * rank_sum;
            max_change = max(max_change, fabs(new_PR - PR));
        }

        PR = new_PR;
        if (max_change < epsilon) break;
    }

    return PR;
}

int main() {
    unordered_map<string, vector<string>> graph = {
        {"A", {"B", "C"}},
        {"B", {"C"}},
        {"C", {"A"}},
        {"D", {"C"}}
    };

    auto pagerank_values = pagerank(graph);
    cout << "PageRank értékek:" << endl;
    for (const auto&  : pagerank_values) {
        cout << node << ": " << value << endl;
    }

    return 0;
}

Kimenet:

PageRank értékek:
A: 0.3195
B: 0.2783
C: 0.4022
D: 0.0000

1. Egyszerű modell: Könnyen implementálható gráfreprezentációk használatával.
2. Skálázhatóság: Nagy méretű gráfokon is alkalmazható.
3. Alkalmazások széles köre: Nemcsak weboldalakon, hanem bármilyen hivatkozási hálózatban.

1. Konvergencia idő: Nagy gráfok esetén lassú lehet.
2. Teljes gráf szükséges: Az algoritmus csak a gráf teljes ismeretében működik.

A PageRank algoritmus alapvető szerepet játszik a gráfok elemzésében, és a modern hálózatkutatás egyik alapvető eszköze.

• PageRank - Értelmező szótár (MEK)
• PageRank - Etimológiai szótár (UMIL)
• PageRank - Szótár.net (hu-hu)
• PageRank - DeepL (hu-de)
• PageRank - Яндекс (hu-ru)
• PageRank - Google (hu-en)
• PageRank - Helyesírási szótár (MTA)
• PageRank - Wikidata
• PageRank - Wikipédia (magyar)