En guide til linkforudsigelse - Sådan forudsiger du dine fremtidige forbindelser på Facebook

Oversigt

  • En introduktion til linkforudsigelse, hvordan den fungerer, og hvor du kan bruge den i den virkelige verden
  • Lær om vigtigheden af ​​Link Prediction på sociale medier
  • Byg din første Link Prediction-model til en Facebook-brugssag ved hjælp af Python

Introduktion

Har du nogensinde spekuleret på, hvem din næste Facebook-forbindelse kan være? Er du nysgerrig efter, hvad den næste anmodning kan komme fra?

Hvad hvis jeg fortalte dig, at der var en måde at forudsige dette på?

Jeg elsker brainstorming og kommer med disse problemstillinger, når jeg gennemser min Facebook-konto. Det er en af ​​fordelene ved at have en dataforskers tankegang!

De fleste sociale medieplatforme, inklusive Facebook, kan struktureres som grafer. De registrerede brugere er sammenkoblet i et univers af netværk. Og for at arbejde på disse netværk og grafer har vi brug for et andet sæt tilgange, værktøjer og algoritmer (i stedet for traditionelle maskinlæringsmetoder).

Så i denne artikel vil vi løse et socialt netværksproblem ved hjælp af grafer og maskinlæring. Vi vil først forstå de grundlæggende begreber og komponenter i linkforudsigelse, inden vi tager en casestudie på Facebook og implementerer den i Python!

Jeg anbefaler at gennemgå nedenstående artikler for at få et kig på, hvad grafer er, og hvordan de fungerer:

Indholdsfortegnelse

  1. En oversigt over Social Network Analytics
  2. En grundlæggende på linkforudsigelse
  3. Strategi til at løse et linkforudsigelsesproblem
  4. Casestudie: Forudsig fremtidige forbindelser mellem Facebook-sider - Forstå dataene - Datasæt Klargøring Modelbygning - Funktionsekstraktion - Modelbygning: Linkprædikationsmodel

En oversigt over Social Network Analytics

Lad os definere et socialt netværk først, før vi dykker ned i begrebet linkforudsigelse.

Et socialt netværk er i det væsentlige en repræsentation af forholdet mellem sociale enheder, såsom mennesker, organisationer, regeringer, politiske partier osv.

Interaktionerne mellem disse enheder genererer ufattelige mængder data i form af indlæg, chatbeskeder, tweets, likes, kommentarer, delinger osv. Dette åbner et vindue med muligheder og brugssager, vi kan arbejde på.

Det bringer os til Social Network Analytics (SNA). Vi kan definere det som en kombination af flere aktiviteter, der udføres på sociale medier. Disse aktiviteter inkluderer dataindsamling fra online sociale mediesider og brug af disse data til at tage forretningsbeslutninger.

Fordelene ved analyse af sociale netværk kan være meget givende. Her er et par vigtige fordele:

  • Hjælper dig med at forstå dit publikum bedre
  • Bruges til kundesegmentering
  • Bruges til at designe anbefalingssystemer
  • Opdage falske nyheder blandt andet

En grundlæggende på linkforudsigelse

Link-forudsigelse er et af de vigtigste forskningsemner inden for grafer og netværk. Formålet med linkforudsigelse er at identificere par noder, der enten vil danne et link eller ikke i fremtiden.

Link-forudsigelse har masser af brug i applikationer i den virkelige verden. Her er nogle af de vigtige anvendelsestilfælde af linkforudsigelse:

  • Forudsig hvilke kunder der sandsynligvis vil købe hvilke produkter på online markedspladser som Amazon. Det kan hjælpe med at udarbejde bedre produktanbefalinger
  • Foreslå interaktion eller samarbejde mellem ansatte i en organisation
  • Uddrag vigtig indsigt fra terrornetværk

I denne artikel vil vi udforske et lidt anderledes tilfælde af linkforudsigelse - forudsigelse af links i et online socialt netværk!

Strategi til at løse et linkforudsigelsesproblem

Hvis vi på en eller anden måde kan repræsentere en graf i form af et struktureret datasæt med et sæt funktioner, kan vi måske bruge maskinlæring til at forudsige dannelsen af ​​links mellem grafens ikke-forbundne nodepar.

Lad os tage en dummy-graf for at forstå denne idé. Nedenfor er vist en 7-noden graf, og de ikke-forbundne knudepar er AF, BD, BE, BG og EG:

Graf på tidspunktet t

Lad os nu sige, at vi analyserer dataene og kom med nedenstående graf. Der er oprettet et par nye forbindelser (links i rødt):

Graf på tidspunktet t + n

Vi er nødt til at have et sæt prediktorvariabler og en målvariabel for at opbygge enhver form for maskinlæringsmodel, ikke? Så hvor er disse variabler? Vi kan få det fra selve grafen! Lad os se, hvordan det gøres.

Vores mål er at forudsige, hvorvidt der ville være en forbindelse mellem 2 uknyttede knudepunkter. Fra netværket på tidspunktet t kan vi udtrække følgende nodepar, som ikke har nogen forbindelser imellem dem:

  1. AF
  2. BD
  3. VÆRE
  4. BG
  5. FOR EKSEMPEL

Bemærk, at jeg for nemheds skyld kun har overvejet de knudepunkter, der er et par links fra hinanden.

Det næste trin for os er at oprette funktioner til hvert eneste par af noder. Den gode nyhed er, at der er flere teknikker til at udtrække funktioner fra knudepunkterne i et netværk. Lad os sige, at vi bruger en af ​​disse teknikker og bygger funktioner til hvert af disse par. Vi ved dog stadig ikke, hvad målvariablen er. Intet at bekymre sig om - vi kan let få det også.

Se på grafen på tidspunktet t + n. Vi kan se, at der er tre nye links i netværket for henholdsvis parene AF, BD og BE. Derfor tildeler vi hver enkelt af dem en værdi på 1. Knudeparene BG og EG tildeles 0, fordi der stadig ikke er nogen links mellem knudepunkterne.

Derfor vil dataene se sådan ud:

Nu hvor vi har målvariablen, kan vi opbygge en maskinlæringsmodel ved hjælp af disse data til at udføre linkforudsigelse.

Så det er sådan, vi er nødt til at bruge sociale grafer i to forskellige tilfælde af tid til at udtrække målvariablen, dvs. tilstedeværelsen af ​​en forbindelse mellem et knudepar. Husk dog, at vi i virkelige scenarier kun har data fra den nuværende tid.

Uddrag data fra en graf til opbygning af din model

I afsnittet ovenfor kunne vi få etiketter til målvariablen, fordi vi havde adgang til grafen på tidspunktet t + n. I virkelige scenarier ville vi imidlertid have kun et grafdatasæt i hånden. Det er det!

Lad os sige, at vi har nedenstående graf over et socialt netværk, hvor noderne er brugerne, og kanterne repræsenterer en slags relation:

Kandidatknudeparrene, som kan danne et link på et fremtidig tidspunkt, er (1 & 2), (2 & 4), (5 & 6), (8 & 10) og så videre. Vi er nødt til at opbygge en model, der vil forudsige, om der ville være en forbindelse mellem disse nodepar eller ej. Det er det, linkforudsigelse handler om!

For at opbygge en linkforudsigelsesmodel er vi imidlertid nødt til at udarbejde et træningsdatasæt ud af denne graf. Det kan gøres ved hjælp af et simpelt trick.

Forestil dig dette - hvordan ville denne graf have set ud på et tidspunkt i fortiden? Der ville være færre kanter mellem knudepunkterne, fordi forbindelser i et socialt netværk opbygges gradvist over tid.

Derfor kan vi huske dette, og vi kan tilfældigt skjule nogle af kanterne fra den givne graf og derefter følge den samme teknik som forklaret i det foregående afsnit for at oprette træningsdatasættet.

Slå af links fra grafen

Mens vi fjerner links eller kanter, bør vi undgå at fjerne enhver kant, der kan producere en isoleret knude (knude uden nogen kant) eller et isoleret netværk. Lad os fjerne nogle af kanterne fra vores netværk:

Som du kan se, er kanterne i nodeparene (1 & 4), (7 & 9) og (3 & 8) fjernet.

Føj etiketter til udpakkede data

Dernæst bliver vi nødt til at oprette funktioner til alle de ikke-tilsluttede nodepar, herunder dem, som vi har udeladt kanterne for. De fjernede kanter vil blive mærket som '1' og de ikke tilsluttede nodepar som '0'.

Målvariablen vil være meget ubalanceret i dette datasæt. Dette er, hvad du også vil støde på i virkelige grafer. Antallet af ikke-forbundne knudepar ville være enormt.

Lad os tage et casestudie og løse problemet med linkforudsigelse ved hjælp af Python.

Casestudie: Forudsig fremtidige forbindelser mellem Facebook-sider

Det er her, vi anvender alt det ovenstående i et fantastisk virkelighedsscenarie.

Vi vil arbejde med et grafdatasæt, hvor knudepunkterne er Facebook-sider med populære madfuger og velkendte kokke fra hele verden. Hvis to sider (noder) kan lide hinanden, er der en kant (link) mellem dem.

Du kan downloade datasættet herfra.

Formål: Lav en linkforudsigelsesmodel for at forudsige fremtidige links (gensidige likes) mellem ikke-tilsluttede noder (Facebook-sider).

Lad os affyre vores Jupyter Notebook (eller Colab)!

Forståelse af dataene

Vi importerer først alle de nødvendige biblioteker og moduler:

Lad os indlæse Facebook-siderne som knudepunkter og gensidige likes mellem siderne som kanter:

Output: (620, 2102)

Vi har 620 noder og 2.102 links. Lad os nu oprette et dataframe af alle noder. Hver række af denne dataframe repræsenterer et link dannet af noder i henholdsvis kolonnerne 'node_1' og 'node_2':

fb_df.head ()

Knuderne '276', '58', '132', '603' og '398' danner links til knudepunktet '0'. Vi kan nemt repræsentere dette arrangement af Facebook-sider i form af en graf:

Wow, det ser godt ud. Dette er, hvad vi skal beskæftige os med - et trådnet af Facebook-sider (blå prikker). De sorte streger er linkene eller kanterne, der forbinder alle noder til hinanden.

Datasætforberedelse til modelbygning

Vi er nødt til at forberede datasættet fra en ikke-rettet graf. Dette datasæt har funktioner af nodepar, og målvariablen vil være binær, hvilket indikerer tilstedeværelsen af ​​links (eller ikke).

Hent ikke-tilsluttede nodepar - negative prøver

Vi har allerede forstået, at vi skal forberede et datasæt fra den givne graf for at løse et linkforudsigelsesproblem. En væsentlig del af dette datasæt er de negative prøver eller de ikke-tilsluttede nodepar. I dette afsnit vil jeg vise dig, hvordan vi kan udpakke de ikke-tilsluttede nodepar fra en graf.

Først opretter vi en adjacency matrix for at finde ud af, hvilke par noder der ikke er forbundet.

F.eks. Er justeringen af ​​grafen herunder en firkantet matrix, hvor rækkerne og kolonnerne er repræsenteret af noderne i grafen:

Links er angivet med værdierne i matrixen. 1 betyder, at der er en forbindelse mellem nodeparet, og 0 betyder, at der er en forbindelse mellem nodeparet. For eksempel har knudepunkter 1 og 3 0 ved deres tværkrydsning i matrixen, og disse knudepunkter har heller ingen kant i grafen ovenfor.

Vi vil bruge denne egenskab i adjacency-matrixen til at finde alle de ikke-forbundne nodepar fra den originale graf G:

Lad os tjekke formen på adjacency matrix:

adj_G.shape

Output: (620, 620)

Som du kan se, er det en firkantet matrix. Nu vil vi krydse adjacency-matrixen for at finde nulernes positioner. Bemærk, at vi ikke behøver at gennemgå hele matrixen. Værdierne i matrixen er den samme over og under diagonalen, som du kan se nedenfor:

Vi kan enten søge gennem værdierne over diagonalen (grøn del) eller værdierne nedenfor (rød del). Lad os søge i diagonale værdier efter nul:

Her er hvor mange ikke-tilsluttede nodepar, vi har i vores datasæt:

len (all_unconnected_pairs)

Output: 19.018

Vi har 19.018 uforbundne par. Disse nodepar fungerer som negative prøver under træningen af ​​linkforudsigelsesmodellen. Lad os holde disse par i en dataframe:

Fjern links fra tilsluttede nodepar - Positive prøver

Som vi diskuterede ovenfor, vil vi tilfældigt droppe nogle af kanterne fra grafen. Tilfældigt fjernelse af kanter kan imidlertid resultere i afskæring af løst tilsluttede knuder og fragmenter af grafen. Dette er noget, vi er nødt til at tage os af. Vi er nødt til at sikre, at alle knudepunkter i grafen forbliver tilsluttet under processen med at tabe kanter.

I kodeblokken nedenfor kontrollerer vi først, hvis det at droppe et knudepar resulterer i opdelingen af ​​grafen (antal_tilslutne_komponenter> 1) eller reduktion i antallet af noder. Hvis begge ting ikke sker, dropper vi det nodepar og gentager den samme proces med det næste nodepar.

Til sidst får vi en liste over nodepar, der kan droppes fra grafen, og alle noder vil stadig forblive intakte:

len (omissible_links_index)

Output: 1483

Vi har over 1400 links, som vi kan droppe fra grafen. Disse faldne kanter vil fungere som positive træningseksempler under træning af linkforudsigelsesmodellen.

Data til modeluddannelse

Dernæst tilføjer vi disse aftagelige kanter til dataframmen for ikke-tilsluttede nodepar. Da disse nye kanter er positive prøver, har de en målværdi på '1':

Lad os kontrollere fordelingen af ​​værdier for målvariablen:

data [ 'linket']. value_counts ()

0 -19018 1 -1483

Det viser sig, at dette er meget ubalancerede data. Forholdet mellem link og intet link er bare tæt på 8%. I det næste afsnit vil vi udtrække funktioner til alle disse nodepar.

Funktionsekstraktion

Vi vil bruge node2vec-algoritmen til at udtrække nodefunktioner fra grafen, når vi har droppet linkene. Så lad os først oprette en ny graf efter at have droppet de aftagelige links:

Dernæst installerer vi node2vec-biblioteket. Det ligner DeepWalk-algoritmen. Dog involverer det partiske tilfældige vandreture. Hvis du vil vide mere om node2vec, skal du bestemt tjekke dette papir node2vec: Scalable Feature Learning for Networks.

For tiden er det bare at huske, at node2vec bruges til vektorrepræsentation af knudepunkter i en graf. Lad os installere det:

! pip installere node2vec

Det kan tage et stykke tid at installere på din lokale maskine (det er ret hurtigt, hvis du bruger Colab).

Nu træner vi node2vec-modellen på vores graf (G_data):

Dernæst anvender vi den træne node2vec-model på hvert eneste nodepar i dataframe 'data'. For at beregne funktionerne i et par eller en kant, tilføjer vi funktionerne i knudepunkterne i det par:

x = [(n2w_model [str (i)] + n2w_model [str (j)]) for i, j in zip (data ['node_1'], data ['node_2'])]

Bygning af vores Link Prediction Model

For at validere ydelsen af ​​vores model skal vi opdele vores data i to dele - den ene til at træne modellen og den anden til at teste modellens ydelse:

Lad os først passe til en logistisk regressionsmodel:

Vi vil nu komme med forudsigelser om testsættet:

forudsigelser = lr.predict_proba (xtest)

Vi bruger AUC-ROC-score til at kontrollere vores model's ydeevne.

roc_auc_score (ytest, forudsigelser [:, 1])

Output: 0.7817

Vi får en score på 0,78 ved hjælp af en logistisk regressionsmodel. Lad os se, om vi kan få en bedre score ved at bruge en mere kompleks model.

Træningen stoppede efter den 208. iteration, fordi vi anvendte kriterierne for tidligt stop. Vigtigst af alt fik modellen en imponerende 0,9273 AUC-score på testsættet. Jeg opfordrer dig til at tage et kig på lightGBM-dokumentationen for at lære mere om de forskellige parametre.

Slutnotater

Der er et enormt potentiale i grafer. Vi kan udnytte dette for at løse et stort antal problemer i den virkelige verden, hvor linkforudsigelse er et.

I denne artikel har vi vist, hvordan et linkforudsigelsesproblem kan løses ved hjælp af maskinlæring, og hvad er de begrænsninger og vigtige aspekter, vi skal huske på, mens vi løser et sådant problem.

Du er velkommen til at stille spørgsmål eller give din feedback i kommentarfeltet nedenfor. Fortsæt med at udforske!

Oprindeligt offentliggjort på https://www.analyticsvidhya.com den 16. januar 2020.