Projekt: Googles PageRank Algoritme

Projekt: Googles PageRank Algoritme#

af: Jesper Bækholm Rom Poulsen og Jonas Amtoft. Baseret på David Branders arbejde. Med vejledning fra Jakob Lemvig.

Indledning#

Når du søger på Google, bliver du præsenteret med en række hjemmesider med den mest relevante øverst, når man ser bort fra annoncer. Hvordan ved Googles søgealgoritme, hvordan den skal rangere disse hjemmesider? En måde at se på det er, at en hjemmeside som mange andre linker til, er en relevant hjemmeside. Dette er grundtanken bag PageRank algoritmen, navngivet efter Google-medstifter Larry Page, og netop det som dette projekt omhandler. I Google er håndteringen af internettets enorme informationsmængde et stort samspil mellem flere systemer. Webcrawlerne, som er distribueret over mange maskiner, henter og gemmer siderne i et stort repository. Disse sider gennemgår en proces, hvor vigtige ord og links udvindes og organiseres, hvilket danner grundlag for, at vi kan opbygge en stor netværksstruktur af hjemmesider forbundet via links. Denne sammenkædning, der blandt andet muliggør beregningen af en hjemmesides PageRank, er med til at sikre, at relevante og betydningsfulde sider nemt kan findes (http://infolab.stanford.edu/~backrub/google.html).

I dette projekt skal I undersøge en af de matematiske modeller bag PageRank algoritmen og udvikle forskellige metoder til at beregne PageRank i Python.

Forberedelse#

  • Egenværdiproblemet og diagonalisering, kapitel 11 (Matematik 1a)

  • Diagonaliserbare matricer, afsnit 2.7 (Matematik 1b)

Projektmål#

Hovedmålet med projektet er at lave fire forskellige implementeringer af PageRank algoritmen, der for et givet netværk kan udregne PageRanken.

Note

I skal skrive en sammenhængende rapport uden henvisning til opgavenumrene nedenfor. Det forventes ikke at alle opgaver besvares. I opgave Opgave 22 skal I fx bevise at alle matricer af en vis form er en såkaldt Markov-matrix - hvis I ikke kan komme igennem med det generelle bevis, må I i stedet illustrere udsagnet med nogle eksempler. I skal lade den endelige rapport styre af jeres interesser og ambitioner.

Opgaver markeret med (*) kan undlades i den endelige rapport. Opgaver med (**) er særligt udfordrende og er tiltænkt interesserede.

Grafteoretisk Modellering af Netværk#

Hjemmesider og deres links til andre hjemmesider kan repræsenteres som et netværk \(W\), der kan opfattes som en rettet graf \(W = (V, E)\). Mængden \(V\) består af noder, der hver repræsenterer en hjemmeside, og mængden \(E\) indeholder kanter \((p_i, p_j)\), som repræsenterer et link fra hjemmeside \(p_i\) til hjemmeside \(p_j\). Vi antager, at hjemmesider ikke kan linke til sig selv, og derfor er løkker \((p_i,p_i)\) ikke tilladt. I denne model er hver kant rettet, hvilket betyder, at et link fra \(p_i\) til \(p_j\) ikke implicerer et modsatrettet link. Den indgående grad, \(\deg^-(p_j)\), svarer til antallet af links, der ankommer til node \(p_j\), og den udgående grad, \(\deg^+(p_i)\), repræsenterer antallet af links, der forlader node \(p_i\).

Note

  • Noder kaldes også for knuder, punkter eller hjørner (på engelsk: vertices, nodes eller points)

  • Kanter kaldes også for links (på engelsk: edges, links or lines)

  • En rettet graf hedder på engelsk directed graph eller digraph.

  • En cykel (cyklus) eller kreds hedder på engelsk a cycle.

Opgave 1 (*)#

Givet \(V_1=\{p_1,p_2,p_3,p_4,p_5\}\) og \(E_1=\{(p_1,p_3),(p_1,p_5),(p_2,p_4),(p_2,p_5),(p_3,p_1),(p_4,p_1),(p_4,p_2),(p_4,p_5)\}\), tegn grafen for netværket \(W_1=(V_1,E_1)\) og angiv \(deg^-(p_i)\) for \(i=1,2,...,5\).

Opgave 2 (*)#

Givet \(V_2=\{P1,P2,P3,P4,P5,P6\}\) og \(E_2=\{(P1,P2),(P2,P3),(P3,P1),(P4,P5),(P5,P6),(P6,P4)\}\), tegn grafen for netværket \(W_2=(V_2,E_2)\).

Grafen for netværket \(W_2\) består af to komponenter, som begge er tre-cykler. En komponent i en graf er en delmængde af grafens noder og kanter, hvor der er en vej mellem enhver to noder i delmængden, og der er ingen kanter, der forbinder noder i delmængden med noder udenfor delmængden. En cykel er en vej, der starter og slutter i samme node, og som ikke gentager nogen kanter eller noder imellem bortset fra start- og slutnoden.

Opgave 3#

Diskutér hvordan antallet af komponenter i et netværk påvirker hjemmesidernes synlighed og tilgængelighed for en bruger.

I projektet skal vi bruge dictionaries i Python til at repræsentere netværket \(W\) af hjemmesider. Denne datastruktur gør det muligt at tildele hver side en mængde af de sider, den linker til. Dictionariens nøgler repræsenterer siderne i \(W\), og værdien for en given nøgle \(k\) er mængden af sider, som side \(p_k\) linker til. En dictionary i Python giver os derfor en effektiv måde at tildele hver hjemmeside et sæt af andre hjemmesider, som den peger på. For eksempel kan vi definere en simpel rettet graf som følger:

W = {'P1': {'P2', 'P3'}, 'P2': {'P3'}, 'P3': {'P1'}}

Denne model gør det nemt at tilgå og manipulere data, idet vi hurtigt kan finde ud af, hvilke sider der modtager links fra en bestemt side, hvilket er essentielt for PageRank algoritmen, da link-strukturen danner grundlaget for at bestemme sidernes relative vigtighed.

Opgave 4 (*)#

Skriv netværkene \(W_1\) og \(W_2\) som Python-kode ved at benytte en dictionary. Hvordan angiver man korrekt, at en hjemmeside ikke linker til andre hjemmesider?

Hint

Overvej hvilken datatype værdierne for nøglerne er?

I projektet har vi behov for at teste forskellige implementeringer af PageRank algoritmen på forskellige netværk, og derfor er vi interesserede i at kunne generere vilkårlige netværk med varierende størrelse.

Opgave 5#

Skriv en Python-funktion, der laver en dictionary af n hjemmesider, hvor hver hjemmeside linker til et tilfældigt antal hjemmesider. Dette antal skal ligge mellem kmin og k.

import numpy as np

def make_web(n,k,kmin=0):

    # Input: n og k er ikke-negative heltal
    # Output: web er en dictionary med n nøgler.
    # Værdien af hver nøgle er en liste, der er en delmængde af nøglerne.
    
    assert(k < n), "k skal være mindre end n (da man ikke kan linke til sig selv)"
    assert(kmin <= k), "kmin skal være mindre end eller lig med k"
    keys = # Fjern pass og INDSÆT KODE HER - definér n nøgler fra 0 til n-1 
    web = dict()
    
    for j in keys:
        numlinks = # INDSÆT KODE HER - generér et tilfældigt tal mellem kmin og k
        web[j] = set() # INDSÆT KODE HER - Vælg et antal links (numlinks) fra de andre sider, undgå at vælge den nuværende side (j) og sørg for, at der ikke er duplikatlinks

Hint

Brug np.random.choice() til at vælge tilfældige elementer fra et array.

Opgave 6 (*)#

Skriv en Python-funktion, der laver en grafisk repræsentation af et netværk, hvor links vises med pile.

import networkx as nx
import matplotlib.pyplot as plt

def visualize_graph(web):
    
    # Input: netværk som dictionary
    # Output: Netværk visualiseret som graf

    # INDSÆT KODE HER

    plt.show()

Hint

Benyt networkx og matplotlib.pyplot til at visualisere netværket.

Rekursiv Model og Matrix Formulering#

Ud fra de tidligere opgaver, kan vi nu se, at random surfer modellen med dæmpning faktisk giver fornuftige PageRanks for et sæt hjemmesider. Der er dog to væsentlige problemer ved den, nemlig at tilfældighedselementet gør, at man ikke nødvendigvis får den samme PageRank hver gang man laver det, samt at det er beregningstungt bl.a. fordi mange iterationer kan være nødvendigt. For at undgå disse problemer kan man kigge på en rekursiv model. Først sættes alle PageRanks af hjemmesiderne til at være \(PR_1(p) = \frac{1}{N}\), hvor \(N\) er antal sider. For enhver side \(p\), kan vi komme til \(p\) på to måder:

  • tilfældigt, altså med sandsynlighed \((1-d)\frac{1}{N}\)

  • gennem et link fra en anden side \(q\). Så skal vi først være ved \(q\), og derefter vælge \(p\) blandt alle de sider \(q\) linker til. Hvis en side ikke linker til \(p\), er sandsynligheden for at gå til \(p\) via link selvfølgelig \(0\). Med disse betragtninger, kan PageRank af \(p\) rekursivt opdateres ved

\[\begin{equation*} PR_{n+1}(p) = (1-d)\frac{1}{N} + d\sum_{q \in Inbound(p)}\frac{PR_n(q)}{deg^+(q)}. \end{equation*}\]

Opgave 14#

Forklar hvad hvert led i ovenstående formel for den rekursive version betyder.

Hint

Undersøg additionsprincippet og multiplikationsprincippet.

Opgave 15#

Implementér rank_update og recursive_PageRank og kør på netværkene \(W_1\) og \(W_2\) med d=0.85 og n=100.

def rank_update(web, PageRanks, page, d):

        """
        Opdaterer værdien af PageRank for en side baseret på den rekursive formel
        Sider uden udgående links (sinks) behandles som om de linker til alle sider på nettet.

        Input: 
            web og PageRanks er dictionaries som i outputtet fra "make_web" og "random_surf",
            page er nøglen til den side, hvis rank vi ønsker at opdatere, og
            d er dampingfaktoren.
        Output: 
            PageRank opdateres i henhold til ovenstående formel,
            og denne funktion returnerer et float "increment", den (absolutte) forskel
            mellem den tidligere værdi og den opdaterede værdi af PR(p).
        """

        return increment

def recursive_PageRank(web, stopvalue=0.0001, max_iterations=200, d=0.85):
    """
    Implementerer den rekursive version af PageRank-algoritmen ved først at oprette
    en PageRank på 1/N til alle sider (hvor N er det samlede antal sider)
    og derefter anvende "rank_update" gentagne gange, indtil en af de to stopbetingelser
    er opnået:
    stopbetingelse 1: den maksimale ændring fra trin n til trin (n+1) over alle PageRank
    er mindre end stopværdien,
    Stopbetingelse 2: antallet af iterationer har nået "max_iterations".

    Input: web er et dictionary som i outputtet af "make_web", d er dæmpningen,
    stopvalue er et positivt float, max_iterations er et positivt heltal.
    """

    PageRanks = dict()

    return PageRanks, iteration

I den rekursive model kan den rekursive formel skrives kompakt ved hjælp af den allerede definerede link matrix \(\pmb{L}\). Lader vi

\[\begin{equation*} \pmb{x_n} = \begin{bmatrix} PR_n(p_{1})\\ PR_n(p_{2})\\ \vdots\\ PR_n(p_{N}) \end{bmatrix} \end{equation*}\]

og

\[\begin{equation*} \pmb{e} = \begin{bmatrix} 1\\ 1\\ \vdots\\ 1 \end{bmatrix}, \end{equation*}\]

så kan den rekursive formel

\[\begin{equation*} PR_{n+1}(p) = (1-d)\,\frac{1}{N} + d \sum_{q \in \mathrm{Inbound}(p)} \frac{PR_n(q)}{deg^+(q)} \tag{▲} \end{equation*}\]

skrives i matrixform som

\[\begin{equation*} \pmb{x}_{n+1} = \frac{1-d}{N}\,\pmb{e} + d\,\pmb{L}\,\pmb{x}_n. \tag{■} \end{equation*}\]

Her er \(\pmb{e}\) en \(N\times 1\)-vektor af 1-taller, \(d\) er dæmpningsfaktoren, og \(\pmb{L}\) er link matricen, der beskriver sandsynlighederne for at følge links fra én side til en anden.

Opgave 16#

Argumentér for at (▲) kan omskrives til (■).

Antag, at \(\pmb{x}\) er en sandsynlighedsvektor, dvs. at dens elementer summerer til 1. Vis, at (■) kan skrives som

\[\begin{equation*} \pmb{x}_{n+1} = \pmb{M}_d \, \pmb{x}_n, \end{equation*}\]

hvor

\[\begin{equation*} \pmb{M}_d = \frac{1 - d}{N} \, \pmb{E_N} + d \, \pmb{L}, \end{equation*}\]

og \(\pmb{E_N}\) er en \(N \times N\)-matrix, der udelukkende består af 1-taller.

Matricen \(\pmb{M}_d\) kaldes for den modificerede link matrix. Hvis vi antager, at det altid går godt, dvs. at \(\pmb{x_n}\) på et tidspunkt går mod noget stabilt for større og større \(n\), kan vi konkludere, at den PageRank vi leder efter faktisk er netop det \(\pmb{x}\), som opfylder at være en sandsynlighedsvektor og

\[\begin{equation*} \pmb{x} = \pmb{M}_d\,\pmb{x}. \end{equation*}\]

Den ovenstående ligning udtrykker, at PageRank vektoren \(\pmb{x}\) er en egenvektor for \(\pmb{M}_d\) med egenværdi 1. Hvis dæmpningsfaktoren \(d\) ikke er nul, er der (op til omskalering) netop én egenvektor for denne matrix med egenværdi 1.

Vi vil i projektet vise, at dette altid er sandt, når \(0<d<1\), og at der dermed findes en entydig løsning for den (dampede) PageRank algoritme. Den matrixbaserede formulering giver os derfor endnu en måde at beregne PageRank på:

  • Find en egenvektor svarende til egenværdien et, og skalér vektoren, så dens elementer summerer til et.

Opgave 17#

Implementér modified_link_matrix og test på netværkene \(W_1\) og \(W_2\) med d=0.85.


def modified_link_matrix(web, pagelist, d=0.85):

    # Input: web (dictionary), pagelist (liste over nøgler), d (dæmpningsfaktor)
    # Output: d*A^T + (1-d)*E/N
    
    # A: NxN numpy array, hvor række j har ikke-nul elementer i søjler, som side j linker til.
    # Hvis side j ikke linker til nogen, får alle elementer i række j værdien 1/N.
    # E: np.ones([N,N])
    
    # INDSÆT KODE HER

Opgave 18#

Vis at summen af hver søjle i \(\pmb{M}_d\) er lig med 1.

Markov matricen: Egenskaber og Dæmpning i PageRank#

Vi ønsker at vise, at den dampede PageRank algoritme konvergerer mod en unik sandsynlighedsfordeling, som vi påstod i forrige afsnit. For at vise det får vi brug for at introducere Markov matricen:

Definition 3. Markov matrix: En Markov matrix \(\pmb{A} = [a_{ij}] \in \mathbb{R}^{n\times n}\) er en \(n \times n\) reel matrix med ikke-negative elementer, hvis rækker summerer til 1:

\[\begin{equation*} a_{ij} \ge 0 \quad \forall i, j \end{equation*}\]

og

\[\begin{equation*} \sum_{j=1}^n a_{ij} = 1 \quad \forall i. \end{equation*}\]

Eksempelvis er

\[\begin{equation*} \begin{bmatrix} 0.3 & 0.7 \\ 0 & 1 \end{bmatrix} \end{equation*}\]

en Markov matrix, men

\[\begin{equation*} \begin{bmatrix} 2 & -1 \\ 0 & 1 \end{bmatrix} \quad \text{og} \quad \begin{bmatrix} 0.2 & 0.5 \\ 0.4 & 0.6 \end{bmatrix} \end{equation*}\]

er det ikke.

Hvis \(\pmb{A}\) er en Markov matrix, så kombineret med ovenstående to betingelser, må vi have at

\[\begin{equation*} 0 \le a_{ij} \le 1, \end{equation*}\]

for alle \(i,j\).

Opgave 19#

Argumentér for at \(\pmb{L}^T\) er en Markov matrix.

Opgave 20#

Vis, at hvis \(\pmb{A}\) er en Markov matrix så er \(\pmb{A e} = \pmb{e}\), det vil sige, at \((1,\pmb{e})\) er et egenpar for \(\pmb{A}\).

Opgave 21#

Bevis at en matrix \(\pmb{A}\) og dens transponerede matrix \(\pmb{A}^T\) har de samme egenværdier. Vis derefter at de ikke nødvendigvis har de samme egenvektorer (det vil sige: giv et eksempel på en matrix \(\pmb{A}\), hvor \(\pmb{A}\) og \(\pmb{A}^T\) har forskellige egenvektorrum).

Definition 4. Stationære fordeling: Hvis \(\pmb{A}\) er en Markov matrix med strengt positive elementer, kaldes den entydige sandsynlighedsvektor \(\pmb{x}\), der opfylder

\[\begin{equation*} \pmb{A}^T \pmb{x} = \pmb{x}, \end{equation*} \]

for den stationære fordeling for \(\pmb{A}\).

Bemærk at Markov matricen kan have elementer med værdien 0. Vi vil senere i projektet vise, hvordan vi kan garantere, at \(\pmb{A}\) har strengt positive elementer. Da \(\pmb{L}=\pmb{A}^T\) og \(\pmb{A}\) har de samme egenværdier og ikke nødvendigvis de samme egenvektorer, ønsker vi at bestemme PageRanken ved at finde en egenvektor \(\pmb{x}\), der opfylder ligningen

\[\begin{equation*} \pmb{Lx} = \pmb{x} \end{equation*}\]

Vi er dog interesserede i at arbejde med den modificerede link matrix, når vi skal bestemme PageRanken, som beskrevet tidligere. Vi påstod, at der eksisterede en sandsynlighedsvektor \(\pmb{x}\), der opfylder \(\pmb{M}_d\pmb{x}=\pmb{x}\). For at kunne vise dette, skal vi først konstruere den tilhørende modificerede Markov matrix:

Lad \(0 < d < 1\). For \(\pmb{A} \in \mathbb{R}^{n \times n}\), sæt:

\[\begin{equation*} \pmb{A}_d = \frac{1-d}{n} \pmb{E}_n + d \pmb{A} \end{equation*}\]

Opgave 22#

Lad \(\pmb{A}\) være en Markov matrix, og lad \(0 < d < 1\). Bevis, at \(\pmb{A}_d\) også er en Markov matrix, og at \(\pmb{A}_d\) har strengt positive elementer, det vil sige \((\pmb{A}_d)_{ij} > 0\) for alle \(i\) og \(j\).

Opgave 23#

Vi antog tidligere, at den modificerede link matrix \(\pmb{M}_d\) havde egenværdi 1 for \(0<d<1\). Vis dette.

Da vi har vist, at \(\pmb{M}_d\) har egenværdi 1 for \(0<d<1\), ved vi, at der eksisterer en egenvektor \(\pmb{x}\), som opfylder \(\pmb{M}_d\pmb{x}=\pmb{x}\). Vi vil senere vise, at dette er den entydige løsning til den dampede PageRank algoritme.

Opgave 24#

Implementér en Python-funktion der, givet et netværk, kalder modified_link_matrix, finder en egenvektor tilhørende egenværdien 1, og laver den til en sandsynlighedsvektor.


def eigenvector_PageRank(web,d=0.85):
        # Input: web er en ordbog over websider og links.
        # d er dæmpningen
        # Output: En ordbog med de samme nøgler som web og værdierne er PageRank for nøglerne

        ranking = dict()

        # INDSÆT KODE HER

        return ranking

Opgave 25#

At beregne egenvektorer for store matricer kan være tidskrævende. Lav et netværk med make_web funktionen, hvor n=5000 og k=10, og find PageRanken ved brug af eigenvector_PageRank. Undersøg og kommentér på køretiden.

Hint

Brug pakken time til at bestemme køretiden.

web = make_web(5000,10,0)
eigenvector_PageRank(web)

PageRank algoritmen: Iterativ Konvergens og Dæmpning i Markov Matricer#

Da det er beregningsmæssigt tungt at finde egenværdier og egenvektorer for store matricer, vil vi gerne finde en anden måde at finde egenvektorer med tilhørende egenværdi 1. Det er der heldigvis en metode til at gøre med Markov matricer, og det er det, denne sektion bygger op til. Vi ønsker at nå frem til, at vi for en særlig klasse af Markov matricer kan opløfte den i en eksponent, og som eksponenten går mod uendelig bliver hver søjle i matricen netop en fornuftig PageRank for det netværk af hjemmesider, som Markov matricen repræsenterer.

Opgave 26 (*)#

Beregn produktet af følgende Markov matricer. Verificer at den resulterende matrix ligeledes er en Markov matrix?

\[\begin{equation*} A = \begin{bmatrix} 0.2 & 0.5 & 0.3 \\ 0.4 & 0.4 & 0.2 \\ 0.1 & 0.7 & 0.2 \end{bmatrix}, \quad B = \begin{bmatrix} 0.5 & 0.3 & 0.2 \\ 0.2 & 0.5 & 0.3 \\ 0.3 & 0.2 & 0.5 \end{bmatrix} \end{equation*}\]

At produktet af to Markov matricer er en Markov matrix er en nyttig egenskab, som vi får brug for senere.

Opgave 27#

Vis at produktet af to Markov matricer er en Markov matrix.

Opgave 28#

Konkludér at hvis \(\pmb{A}\) er en Markov matrix, så er \(\pmb{A}^k\) også en Markov matrix for alle \(k\in \mathbb{N}\).

Vi får også brug for, at ingen egenværdier af en Markov matrix har absolutværdi større end 1. En anden måde at sige dette på er, at den spektrale radius \(\operatorname{rad}_{\pmb{A}}\) af en Markov matrix \(\pmb{A}\) er lig 1:

\[\begin{equation*}\operatorname{rad}_{\pmb{A}} = \max \{|\lambda_1|, \ldots, |\lambda_n|\}\end{equation*}\]

Vi ser senere, hvordan dette er med til at sikre, at potenser af den særlige klasse af Markov matricer konvergerer.

Opgave 29#

Lad \(\pmb{A}\) være en \(n\times n\) Markov matrix. Vis at \(\operatorname{rad}_{\pmb{A}} = 1\).

Hint

Antag at \(\pmb{A}\) har en egenværdi \(\lambda\) med \(|\lambda|>1\). Lad \(\pmb{v}\) være den tilhørende egenvektor. For en Markov matrix er summen af hver række netop 1, altså kan \(\pmb{A}\pmb{v} = \lambda \pmb{v}\) ses som \(n\) (forskellige) vægtede gennemsnit af \(\pmb{v}_1, \pmb{v}_2, \ldots, \pmb{v}_n\). Hvor stor kan absolutværdien af et vægtet gennemsnit af \(n\) elementer maksimalt være?

Opgave 30 (*)#

Betragt følgende matrix:

\[\begin{equation*} \pmb{A} = \begin{bmatrix} 0 & 1 & 0\\ 0 & 0 & 1\\ 1 & 0 & 0 \end{bmatrix} \end{equation*}\]

Er det en Markov matrix? Find dens egenværdier og egenværdiernes modulus. Find \(\pmb{A}^2, \pmb{A}^3\). Konvergerer matricen \(\pmb{A}^k\) for \(k\to \infty\)?

Nu betragter vi den særlige klasse af Markov matricer nævnt før, nemlig Markov matricer med strengt positive elementer - endnu en grund til at dæmpningsfaktoren er en vigtig spiller i PageRank algoritmen. For at sikre os konvergensen af potenser af Markov matricer med strengt positive elementer, skal vi sikre, at \(1\) er den eneste egenværdi med modulus \(1\). Til dette får vi brug for trekantsuligheden:

Trekantsuligheden:
For alle komplekse tal \(z\) og \(w\) gælder

\[\begin{equation*} |z+w| \leq |z| + |w|, \end{equation*}\]

med lighed hvis og kun hvis \(z\) og \(w\) er på formen \(z = kw, k\in \mathbb{R}_{\geq 0}\)

Mere generelt følger det ved induktion, at for en samling af \(n\) komplekse tal \(z_1, \dots, z_n\) gælder:

  • \(\left| \sum_{i=1}^n z_i \right| \leq \sum_{i=1}^n |z_i|\)

  • Lighed opstår kun, hvis alle tallene \(z_i\) har samme hovedargument.

Opgave 31#

Hvis \(\pmb{A}\) er en Markov-matrix med strengt positive elementer (\(a_{ij} > 0\) \(\forall\) \(i,j\)), bevis at der er præcis én egenværdi \(\lambda\) med \(|\lambda| = 1\), nemlig \(\lambda = 1\), og desuden at det tilsvarende egenrum er \(\mathcal{E}_1 = \hbox{span}\{ \pmb{e} \}\), hvor \(\pmb{e} = [1,1,\dots,1]^t\). Alle andre egenværdier har modulus mindre end 1.

Hint: Maks-normen af en vektor \(\pmb{x}\) defineres som

\[\begin{equation*} \Vert\pmb{x}\Vert_{\infty} := \max_k \{|x_k|\}, \end{equation*}\]

dvs. værdien af det største element i absolut/numerisk værdi, jf. Example 2.1.2. i lærebogen.

Antag, at \(\lambda\) er en egenværdi med \(|\lambda|=1\), og at \(\pmb{v}\) er en tilhørende egenvektor. Lad \(k\) være et indeks, så \(\Vert\pmb{v}\Vert_{\infty} = |v_k|\). Da kan vi skrive:

(9)#\[\begin{align} \Vert\pmb{v}\Vert_{\infty} &= |\lambda| |v_k| = |\lambda v_k| = \left|\sum_{j=1}^n a_{kj}v_j\right| \\ &\leq \sum_{j=1}^n |a_{kj}v_j| = \sum_{j=1}^n a_{kj}|v_j| \\ &\leq \sum_{j=1}^n a_{kj} \Vert\pmb{v}\Vert_{\infty} = \Vert\pmb{v}\Vert_{\infty}. \end{align}\]

Giv begrundelse for hvert trin ovenfor.

Da den første og sidste led i denne kæde er ens, må der være lighed i hver ulighed. Brug den første af disse uligheder sammen med punkt (2) i trekantsuligheden ovenfor, samt den anden af disse ligheder (og betingelsen \(a_{ij}>0\)) til at vise, at vi må have \(\pmb{v} = C \pmb{e}\), hvor \(|C| = \Vert\pmb{v}\Vert_{\infty}\).

Opgave 32 (*)#

Tag matricen \(\pmb{A}\) fra opgave 30. Dæmp den med faktor \(0.85\), kald denne matrix \(\pmb{A}_d\). Find herefter dens egenværdier, deres modulus, og kommenter på resultatet. Konvergerer \(\pmb{A}_d^k\) for \(k \to \infty\)?

Hint

Diagonalisér matricen.

Sætning 1: Lad \(n\geq 2\) og \(\pmb{A}\) være en \(n \times n\) Markov matrix med strengt positive elementer. Så er der en entydig vektor \(\pmb{x} \in \mathbb{R}^n\) således at \(\pmb{A}^T\pmb{x} = \pmb{x}\), alle elementer i \(\pmb{x}\) er strengt positive og summerer til 1, samt:

\[\begin{equation*} \lim_{k\to \infty} (\pmb{A}^T)^k = \pmb{xe}^t = [\pmb{x}, \pmb{x}, \ldots, \pmb{x}] \end{equation*}\]

Opgave 33#

Forklar hvorfor Sætning 1 er relevant for PageRank algoritmen.

Opgave 34.#

Lad \(\pmb{A}\) være en \(n \times n\) Markov matrix med strengt positive elementer. Bevis Sætning 1 under antagelsen at \(\pmb{A}\) er diagonaliserbar.

Hint

Hvis \(\pmb{A}\) er diagonaliserbar er \(\pmb{A} = \pmb{V}\pmb{D}\pmb{V}^{-1}\) for en matrix \(\pmb{V}\) og en diagonalmatrix \(\pmb{D}\). Hvad er \(\pmb{A}^k\)?

Opgave 35#

Skriv en Python-funktion der givet et netværk, eksponent power og en dæmpningsfaktor d, kalder modified_link_matrix og ganger den med sig selv power gange, og returnerer en PageRank for netværket.


def matrix_PageRank(web,power,d=0.85):

    # Input: web er et dictionary med websider og links.
    # d er en positiv float, dæmpningskonstanten.
    # Output: Et dictionary med de samme nøgler som web, og værdierne er PageRank for hver nøgle.

    ranking = dict()

    # INDSÆT KODE HER

    return ranking

Opgave 36 (**)#

Vi ønsker at vise, at konvergensen af matrix_PageRank algoritmen er afhængig af valget af dæmpningsfaktoren \(d\). Vis at hvis \(\pmb{A}\) har egenværdier 1, \(\lambda_1\), \(\lambda_2\),…,\(\lambda_{n-1}\), så har \(\pmb{A}_d\) egenværdier 1, \(d\lambda_1\), \(d\lambda_2\),…,\(d\lambda_{n-1}\).

Hint

Vis først at \(1\) er en egenværdi for \(\pmb{A}_d\). Betragt herefter \(\pmb{A}^T\). Hvad er \(\pmb{e}^T\pmb{A}^T\)? Vis at hvis \(\pmb{v}\) er egenvektor for \(\pmb{A}^T\) med egenværdi forskellig fra \(1\), da er \(\pmb{v}\perp \pmb{e}\). Hvilke egenværdier har \(\pmb{E}_n\)? Hvordan forholder deres egenrum sig til hinanden? Vis herefter at enhver egenvektor for \(\pmb{A}^T\) også er en egenvektor for \(\pmb{A}_d^T\). Hvad er deres tilhørende egenværdier?

Opgave 37#

Diskutér valget af dæmpningen i PageRank algoritmen ud fra konvergens og korrekthed. Overvej konvergensen hvis \(\pmb{L}\) er en \(n \times n\)-matrix med egenværdier \(\lambda_1=1\), \(\lambda_2=-0.999\) og \(|\lambda_k|<0.5\) for \(k=2,...,n\). Inddrag en geometrisk visualisering og sammenlign konvergensen for \(\pmb{L}\) og \(\pmb{M}_d\). Hvad sker der hvis vi erstatter \(\lambda_2=-0.999\) med \(\lambda_2=0.999\cdot i\)?

Opgave 38#

Argumentér hvorfor vi kan tillade os at bruge matrix_PageRank funktionen til at bestemme PageRanken, når det er en approksimativ algoritme.

Analyse af PageRank Modeller og Undersøgelse af Dæmpning#

Opgave 39#

Skriv en Python-funktion, der givet et netværk og en ranking, laver en grafisk repræsentation af netværket, hvor pile illustrerer links mellem hjemmesider, og størrelser af hjemmesiderne angiver størrelsen af PageRanken. Test funktionen på \(W_1\) og \(W_2\).

def plot_ranking(web, ranking, d=0.85):

    # Input: web og ranking er dictionary, eksempelvis som output fra funktionerne "make_web" og "random_surf".

    # Output: Grafisk repræsentation af webstrukturen med links som #pile og PageRank visualiseret ved størrelsen af hjemmesider.

    # INSERT CODE HERE

    plt.show()

Opgave 40#

Test de fire PageRank algoritmer på store netværk oprettet ved hjælp af funktionen make_web. For at sammenligne to forskellige implementeringer skal du beregne PageRank for det samme netværk til samme præcisionsgrad og sammenligne tiden. Ændrer de relative tider sig, hvis der kræves højere eller lavere præcision?

Indtil videre har vi benyttet d=0.85. Eksperimentér med forskellige værdier af dæmpningen (f.eks. 0.5, 0.75, 0.9) i matrix_PageRank. Kør funktionen på det samme netværk (benyt make_web) og mål, hvor mange iterationer der kræves for at opnå konvergens, samt hvordan den endelige rangordning af siderne ændres. Diskutér valget af dæmpningen.

Jordans Normal Form: Generalisering af Diagonaliserbarhed#

I opgave 34 viste vi gyldigheden af PageRank algoritmen (matrix_PageRank) under antagelse af, at \(\pmb{A}\) er diagonaliserbar. Dette er dog ikke altid tilfældet, og vi er derfor interesserede i at vise, at PageRank algoritmen konvergerer selvom \(\pmb{A}\) ikke kan diagonaliseres. Derfor får vi brug for Jordans normal form:

Jordans normal form er en normalform for kvadratiske matricer, som generaliserer diagonaliserbarhed. Lad \(\pmb{A} \in \mathbb{C}^{n \times n}\) have \(m\) forskellige egenværdier \(\lambda_1, \lambda_2, \dots, \lambda_m\). Så findes en invertibel matrix \(\pmb{P}\), således at

\[\begin{equation*} \pmb{A} = \pmb{PJP}^{-1}, \end{equation*}\]

hvor \(\pmb{J}\), Jordans normal form for \(\pmb{A}\), er en blokdiagonal matrix bestående af Jordan blokke. Hele \(\pmb{J}\) kan skrives som

\[\begin{equation*} \pmb{J} = \begin{bmatrix} \pmb{J}_{k_1}(\lambda_1) & 0 & \cdots & 0 \\ 0 & \pmb{J}_{k_2}(\lambda_2) & \cdots & 0 \\ \vdots & \vdots & \ddots & \vdots \\ 0 & 0 & \cdots & \pmb{J}_{k_m}(\lambda_m) \end{bmatrix}, \end{equation*}\]

hvor \(\lambda_i\)’erne ikke behøver at være forskellige. Hver Jordan blok \(\pmb{J}_{k_i}(\lambda_i)\) for egenværdien \(\lambda_i\) har dimension \(k_i \times k_i\) og har formen

\[\begin{equation*} \pmb{J}_{k_i}(\lambda_i)= \begin{bmatrix} \lambda_i & 1 & 0 & \cdots & 0 \\ 0 & \lambda_i & 1 & \cdots & 0 \\ \vdots & \ddots & \ddots & \ddots & \vdots \\ 0 & \cdots & 0 & \lambda_i & 1 \\ 0 & \cdots & \cdots & 0 & \lambda_i \end{bmatrix}. \end{equation*}\]

Opgave 41 (**)#

Vis Sætning 1 ved at bruge Jordans normal form. I må derfor ikke antage, at \(\pmb{A}\) er diagonaliserbar.

Contents