linkforudsigelse

Linkforudsigelse, også kendt som linkprediktion, er studiet af at bedømme sandsynligheden for, at et link mellem to noder i et netværk eksisterer i nutiden eller opstår i fremtiden, baseret på observerede mønstre i netværket. Opgaven er central i grafbaserede data og anvendes i mange domæner, fra sociale netværk til biologiske og vidensbaserede grafer.

Netværk kan være sociale, biologiske, tekniske eller videnbaserede. Opgaven deles typisk i to: at rekonstruere manglende kanter i et givet netværk og at forudsige fremtidige kanter i dynamiske netværk, hvor forbindelser ændrer sig over tid. Kanter kan være enten urettede eller rettede, og data kan indeholde eller udelade attributter om noder og kanter.

Metoder spænder fra enkle, ikke-læringsbaserede mål til avancerede modeller. Enkle metoder inkluderer Common Neighbours (antal fælles naboer), Jaccard-koefficienten, Adamic–Adar-score og Preferential Attachment. Mere avancerede metoder omfatter Katz-score og SimRank. Maskinlæringsbaserede tilgange bruger funktioner trukket fra par af noder og deres omkringliggende struktur eller knytter graf-embeddings som node2vec, DeepWalk og grafneuralnetværk (GCN, GraphSAGE). For viden grafer bruges også relation-embedding teknikker som TransE, DistMult og ComplEx.

Evaluering kræver typiske datamaterialer med træning og testopdelinger, hvor nogle kanter fjernes eller tidsbaserede splits anvendes. Metrikker som AUC (area under ROC), gennemsnitlig præcision (AP) og top-k præcision bruges til at måle prædiktionens kvalitet.

Anvendelser inkluderer anbefalingssystemer i sociale netværk, fuldførelse af interaktioner i biologiske netværk og relationforudsigelse i vidensgrafer. Udfordringer omfatter data-sparsitet, skævheder, koldstart for nye noder, stor-skala-udfordringer og etiske hensyn som privatliv og bias.