Prosjekt 5 – Kan vi stole på rangeringen?

Kan et annet besøksmønster få to sider til å bytte plass?

PageRank gir hver nettside en verdi som mål på viktighet ut fra en besøksmodell. Vi rangerer sidene fra høyest til lavest verdi. Men besøkende kan ha ulike interesser. Hvor mye må vi endre besøksmønsteret før to sider bytter plass?

I dette prosjektet skal du først bygge og kontrollere modellen. Deretter bruker du lineær algebra til å undersøke et selvvalgt besøksmønster. Koden brukes til å regne og kontrollere; de matematiske begrunnelsene er hovedarbeidet. Prosjektet er lagt opp til omtrent 4–6 timers arbeid når du har notatene for hånden.

Prosjektet bygger på besøksmodellen i 5.5, PageRank og tilfeldige hopp i 5.6 og fikspunktiterasjon fra uke 2. Utledningene under bruker også egenverdier og egenvektorer fra 5.2–5.4. Alle nødvendige data og kodefunksjoner finnes på denne siden.

Arbeidsform: Skriv ned hva du forventer, før hvert forsøk. Regn og begrunn, bruk koden som kontroll, og forklar eventuelle forskjeller. Alle fire delene inngår i prosjektet. Det er ikke nødvendig å bygge flere nettverk eller prøve mange parameterverdier.

1. Fra lenker til en overgangsmatrise

Vi bruker seks nettsider. Hver rad i tabellen viser hvilke lenker som finnes på en side:

Fra side	Lenker til
A	B, C
B	C, D
C	A
D	C, E
E	F
F	D

En tenkt besøkende velger én av lenkene på siden hen er på, med lik sannsynlighet, og åpner siden lenken peker til. Dette kaller vi ett steg. Vi følger sannsynligheten for å være på hver side etter et bestemt antall steg, ikke antall besøk samlet over tid.

a. Tegn og forutsi. Tegn de seks sidene og pilene mellom dem. Hvilken side tror du besøksregelen vil gi høyest verdi? Begrunn forventningen med lenkene. En side med mange innkommende lenker er én mulig kandidat, men hvilke sider lenkene kommer fra, kan også ha betydning.

b. Skriv matrisen. Bruk rekkefølgen A, B, C, D, E, F. Elementet \(S_{ij}\) er sannsynligheten for å gå fra side \(j\) til side \(i\). Kolonne \(j\) beskriver altså siden vi går fra, og rad \(i\) siden vi går til.

Svar: en \(6\times6\) overgangsmatrise \(S\). Forklar én kolonne og én rad med ord.

c. Beregn ett steg og vis at summen bevares. La

\[u_0=\frac16(1,1,1,1,1,1)^T.\]

Beregn \(Su_0\) for hånd. Vis deretter at \(Sp\) har ikke-negative elementer og sum én når \(p\) har begge disse egenskapene. Du kan bruke \(\mathbf1=(1,1,1,1,1,1)^T\) og uttrykke kolonnesummene som \(\mathbf1^TS=\mathbf1^T\).

Svar: én sannsynlighetsvektor og en kort generell utledning. En matrise med ikke-negative elementer og kolonnesum én kalles kolonnestokastisk.

2. Finn en stasjonær fordeling og kontroller beregningen

Vi legger til tilfeldige hopp, slik som i 5.6. Ved hvert steg følger den besøkende en lenke med sannsynlighet \(\alpha\), og velger ellers neste side etter en hoppfordeling \(u\). Denne sannsynlighetsvektoren beskriver hvor et hopp ender, uavhengig av nåværende side. Vi bruker \(\alpha=0.85\) i denne delen og i del 4.

Ett steg er altså oppdateringen

\[T(p)=\alpha Sp+(1-\alpha)u,\qquad p_{k+1}=T(p_k).\]

En stasjonær fordeling \(p_*\) er et fikspunkt: \(T(p_*)=p_*\). Den besøkende fortsetter å bevege seg, men fordelingen endres ikke. PageRank-verdiene er koordinatene i \(p_*\).

a. Utled et lineært system. Start med \(T(p_*)=p_*\). Samle leddene som inneholder \(p_*\) på venstre side, og skriv systemet på formen \(Mp_*=b\). Oppgi \(M\) og \(b\) uttrykt ved \(S\), \(u\) og \(\alpha\).

Hvorfor finnes nøyaktig én løsning? Du kan bruke at egenverdiene til en kolonnestokastisk matrise har absoluttverdi høyst én. Forklar hvorfor matrisen \(M\) er invertibel når \(0<\alpha<1\). Fra 5.6 vet vi dessuten at positiv \(u\) gir en positiv stasjonær fordeling som iterasjonen nærmer seg fra enhver startfordeling.

b. Fullfør to regneuttrykk. I koden under er løkken, stoppkontrollen og den direkte løsningen ferdig skrevet. Du fyller bare inn besøksregelen og residualnormen:

\[r(p)=T(p)-p,\qquad \lVert r(p)\rVert_1=\sum_i|r(p)_i|.\]

S er en NumPy-matrise med form (n, n). p og u er NumPy-vektorer med form (n,). visit_step skal returnere en vektor med samme form; residual_norm skal returnere ett ikke-negativt tall. Bruk np.linalg.norm(vektor, 1) for 1-normen.

c. Sammenlign to metoder. Bruk jevn hoppfordeling \(u=u_0\). Forutsi om startfordelingen kan endre den stasjonære løsningen. Kjør iterasjonen fra både jevn startfordeling og sikker start på A.

Svar: rangeringen og kontrolltabellen fra de to startfordelingene. Forklar hva enighet mellom iterasjon og direkte løsning kontrollerer. Kan begge metodene være enige selv om en lenke er lagt inn feil?

Stoppkravet bygger på feilgrensen fra 5.6:

\[\lVert p-p_*\rVert_1\leq\frac{\lVert T(p)-p\rVert_1}{1-\alpha}.\]

Forklar hvorfor koden sammenligner residualnormen med \((1-\alpha)\cdot10^{-8}\) når målet er en feil på høyst \(10^{-8}\). Du trenger ikke utlede denne grensen på nytt.

3. Forklar konvergens med egenverdier

Vi bruker nå et lite nettverk som kan analyseres helt for hånd: to sider som bare lenker til hverandre. La \(S_2\) være overgangsmatrisen og \(u_2=(1/2,1/2)^T\) den jevne hoppfordelingen. I denne delen er \(\alpha\) en parameter med \(0<\alpha<1\).

a. Finn egenverdiene. Skriv \(S_2\) og Google-matrisen \(G_2=\alpha S_2+(1-\alpha)u_2\mathbf1^T\), der \(\mathbf1=(1,1)^T\). Beregn \(G_2v\) og \(G_2w\) for \(v=(1,1)^T\) og \(w=(1,-1)^T\). Finn begge egenverdiene uttrykt ved \(\alpha\), og bestem den stasjonære sannsynlighetsvektoren.

b. Utled feiloppdateringen. For det generelle nettverket setter vi \(e_k=p_k-p_*\). Trekk de to likningene

\[p_{k+1}=\alpha Sp_k+(1-\alpha)u,\qquad p_*=\alpha Sp_*+(1-\alpha)u\]

fra hverandre. Vis at \(e_{k+1}=\alpha Se_k\). Forklar også hvorfor \(\mathbf1^Te_k=0\). Utledningen krever ikke at \(S\) har en egenvektorbasis.

c. Finn hele følgen for to sider. Bruk \(p_0=(1,0)^T\). Skriv startfordelingen som en lineærkombinasjon av \(v\) og \(w\), og finn et uttrykk for \(p_k\) og \(p_k-u_2\) for alle heltall \(k\geq0\). Forklar både fortegnsvekslingen og konvergensfarten. Hva skjer ved \(\alpha=1\), når hoppene fjernes?

Svar: de to egenverdiene, en stasjonær fordeling, feiloppdateringen og en eksplisitt vektorformel for \(p_k\). Sammenlign med fortegnsforsøket i 5.4.

4. Egen undersøkelse: når bytter to sider plass?

Vi vender tilbake til seksidersgrafen. Hold \(S\) og \(\alpha=0.85\) faste. Vi endrer bare hvor tilfeldige hopp lander. Ingen side i denne grafen mangler utgående lenker, så \(S\) er uavhengig av hoppfordelingen.

a. Velg et besøksmønster og en påstand. Velg en positiv sannsynlighetsvektor \(u_1\ne u_0\) som uttrykker en interesse du kan beskrive. For eksempel kan du la besøkende hoppe oftere til F. Alle seks koordinatene skal være større enn null og summere til én.

Vi blander jevn hopping og dette besøksmønsteret:

\[u(t)=(1-t)u_0+tu_1,\qquad 0\leq t\leq1.\]

Her er \(t\) vekten på det nye besøksmønsteret, ikke antall steg. \(t=0\) gir jevne hopp, og \(t=1\) gir hopp etter \(u_1\). Vis at \(u(t)\) er en positiv sannsynlighetsvektor for hver verdi i intervallet.

Velg to forskjellige sider, \(i\) og \(j\), og skriv en påstand før du kjører koden: Vil de bytte plass når \(t\) øker fra 0 til 1? Hvorfor? Bruk lenkene til å begrunne forventningen. Oppgi hva som ville avkrefte den.

b. Vis hvordan løsningen avhenger av \(t\). La \(p(t)\) være den stasjonære fordelingen for hoppfordelingen \(u(t)\). Notasjonen \(p(0)\) og \(p(1)\) betegner altså to stasjonære løsninger, ikke startvektoren og første iterasjon.

Bruk det lineære systemet fra del 2 til å vise at

\[p(t)=(1-t)p(0)+tp(1).\]

Du kan sette høyresiden inn i systemet og bruke at løsningen er entydig. Dette er en eksakt matematisk sammenheng; et plott alene beviser den ikke.

c. Finn en terskel, eller vis at det ikke finnes noen. Sett \(d(t)=p_i(t)-p_j(t)\). Utled et uttrykk for \(d(t)\) fra del b. Finn når \(d(t)=0\), og bestem hvilken av de to sidene som ligger høyest før og etter en eventuell terskel. Ta med tilfellene der \(d(t)\) er konstant, der sidene har like verdier for alle \(t\), og der likhet bare oppstår ved et endepunkt.

Svar: et uttrykk for \(d(t)\), en terskel i \([0,1]\) dersom den finnes, og en konklusjon om plassforholdet. En terskel utenfor intervallet gir ikke et plassbytte i forsøket. Uteblir plassbyttet, er det også et gyldig resultat, så lenge du begrunner hvorfor.

d. Kontroller med få beregninger. Beregn \(p(0)\) og \(p(1)\) direkte. Bruk tallene til å bestemme terskelen numerisk, etter at du har utledet formelen. Velg noen få verdier av \(t\) som tester konklusjonen, for eksempel én på hver side av terskelen. Sammenlign direkte løsning med uttrykket fra del b. Du trenger ikke søke gjennom et stort antall verdier.

Hvor sikker er konklusjonen? Oppgi hvor mange sifre du bruker i terskelen. Et svært lite beregnet avvik betyr ikke automatisk at verdiene er eksakt like. Hvis to verdier er så nær hverandre at beregningsfeilen kan avgjøre fortegnet, rapporter usikkerheten eller bruk et strengere nøyaktighetskrav. Drøft også forskjellen på at to sider bytter innbyrdes plass og at en side blir høyest rangert blant alle seks.

Dette skal leveres

Lever én kjørbar notebook eller Quarto-side med:

Grafen, overgangsmatrisen og håndberegningen av ett steg.
Korte utledninger av at summen én bevares, av referansesystemet og av feiloppdateringen.
Tosideanalysen med egenverdier, stasjonær fordeling og formel for iterasjonsfølgen.
Rangeringen og kontrolltabellen fra del 2, samt høyst to figurer totalt.
Den egne undersøkelsen: valgt \(u_1\) og sidepar, påstanden før forsøket, beviset for blandingsformelen, terskelberegningen og de numeriske kontrollene.

Skriv omtrent 300–500 ord analyse i tillegg til formler og beregninger. Bruk de konkrete resultatene til å skille mellom:

Om koden løser likningen for modellen slik du har lagt den inn.
Om iterasjonen konvergerer.
Hva modellen måler som «viktighet», og hvordan besøksmønsteret påvirker dette.

En påstand som blir avkreftet, er et godt prosjektresultat når undersøkelsen og begrunnelsen er tydelige. Det er ikke nødvendig å finne et dramatisk plassbytte. Kode du får hjelp til å skrive, må du kunne forklare og kontrollere.