Organisationen av verkliga nätverk förkroppsligar vanligtvis både regularitet och oegentligheter, och i princip kan den förra modelleras. I vilken utsträckning bildandet av ett nätverk kan förklaras sammanfaller med vår förmåga att förutsäga saknade länkar. För att förstå nätverksorganisation, bör vi kunna uppskatta länken förutsägbarhet. Vi antar att regelbundenheten i ett nätverk återspeglas i konsekvensen av strukturella funktioner före och efter ett slumpmässigt avlägsnande av en liten uppsättning länkar. Baserat på perturbationen av adjacensmatrisen föreslår vi ett universellt strukturindex som är fritt från förkunskaper om nätverksorganisation. Omfattande experiment på olika Realworld-nätverk visar att i) strukturell överensstämmelse är en god uppskattning av länkförutsägbarhet och ii) en derivatalgoritm överträffar toppmoderna länkförutsägelsemetoder i både noggrannhet och robusthet. Denna analys har ytterligare tillämpningar för utvärdering av länkförutsägelsealgoritmer och övervakning av plötsliga förändringar i föränderliga nätverksmekanismer. Det kommer att ge unika grundläggande insikter inom ovannämnda akademiska forskningsområden och kommer att främja utvecklingen av avancerad informationsfiltreringsteknik av intresse för IT-utövare. Sammanlänkningsförutsägelse - komplexa nätverk - strukturell perturbation - förutsägbarhet Att stå ut med organisationen av verkliga nätverk är en långvarig utmaning inom många vetenskapsgrenar (1). Även om vissa mekanismer redan har accepterats som primära drivkrafter i nätverksorganisationen, inklusive homofily (2-4), triadisk stängning (5-7), förmånsbindning (8-10), ömsesidighet (11) och social balans (12), kan en eller två av dessa mekanismer inte ge en fullständig förklaring; dvs. länkbildning i verkliga nätverk drivs vanligtvis av både regelbundna och oregelbundna faktorer, och endast de förstnämnda kan förklaras med hjälp av mekanistiska modeller. Denna inneboende nätverk komplexitet ger oss frågan om hur man kan uppskatta vilka delar av ett verkligt nätverk kan kategoriseras som regelbunden, med andra ord, i vilken utsträckning länkbildningen i nätverket är oförklarlig. Denna fråga påminner om det problem med kopplingsförutsägelser där uppsättningen observerade länkar i ett nät används för att uppskatta sannolikheten för att det finns en icke-observerad länk (13). I vilken utsträckning nätverksbildningen kan förklaras sammanfaller med vår förmåga att förutsäga felande länkar (14, 15). Å ena sidan, en effektiv länk förutsägelse algoritm ger starka bevis för motsvarande mekanism(er) för nätverksorganisation, t.ex., effektivitet av gemensam-grannskap-baserade metoder indikerar betydelsen av triadisk stängning (16, 17). Å andra sidan bör en bättre förståelse av nätverksorganisationen kunna överföras till en bra länkförutsägelsealgoritm, t.ex. kan förhandsantagandet av hierarkisk organisation av nätverk direkt tillämpas på utformningen av en förutsägelsealgoritm (18). I detta avseende, precisionen i en länk förutsägelse algoritm berättar i vilken utsträckning länkbildningen i nätverket kan förklaras av denna algoritm. Men olika algoritmer ger olika precisioner i samma nätverk (se tabell 1, precisionerna i sju länk förutsägelse (LP) metoder på 10 nätverk) och därmed precisionen endast återspeglar länken förutsägbarhet i samband med en specifik algoritm, inte den inneboende funktionen i själva nätverket. Förutsägbarhet definieras vanligen som möjlig maximal precision för en förutsägelsealgoritm (19). Denna typ av definition är dock inte lämplig för kopplingsförutsägelse eftersom ett verkligt nätverks förutsägbarhet enligt en sådan definition bör vara 1 eftersom deras icke-observerade länkar nästan alltid kan urskiljas (se Material och Metoder). I detta dokument, länk förutsägbarhet verkligen karakteriserar den inneboende svårigheten med förutsägelse som inte är beroende av specifika algoritmer, och vår grundläggande hypotes är att saknade länkar är svåra att förutsäga om deras tillägg orsakar enorma strukturella förändringar, och därmed nätverk är mycket förutsägbar om avlägsnande eller tillägg av en uppsättning slumpmässigt utvalda länkar inte väsentligt ändrar nätverkets strukturella funktioner. Därför föreslår vi ett så kallat "strukturell överensstämmelse" index som bygger på den första ordningens matris perturbation, som kan återspegla den inneboende länken förutsägbarhet av ett nätverk och inte kräver någon förkunskaper om nätverkets organisation. Vi föreslår också en strukturell perturberingsmetod för länkprognoser som är mer exakt och robust än de senaste metoderna. Betrakta en enkel oriktad nätverk GðV ; E och där V är uppsättningen av noder och E är uppsättningen av länkar. Det givna nätverket kan representeras av en N × NðN = jV j på adjacensmatris A, där elementet A ij = 1 om noderna i och j är anslutna och A ij = 0 annars. Vi väljer slumpmässigt ett bråk p H av länkarna för att utgöra en perturbation uppsättning ΔE, medan resten av länkarna E − ΔE utgör uppsättningen E R. Beteckna av A R och ΔA motsvarande adjacency matriser; uppenbarligen, A = A R + ΔA. Eftersom A R är verkligt symmetrisk, kan det diagonaliseras som Significance Kvantifiera ett nätverk länk förutsägbarhet gör att vi kan (i) utvärdera prediktiva algoritmer associerade med nätverket, (ii ) uppskatta i vilken utsträckning organisationen av nätverket är explicerbar, och (iii) övervaka plötsliga mekanistiska förändringar under nätverkets utveckling. Hypotesen i detta dokument är att en grupp länkar är förutsägbar om avlägsnandet av dem bara har en liten effekt på nätverkets strukturella egenskaper. Vi introducerar ett kvantitativt index för att mäta länk förutsägbarhet och en algoritm som överträffar state-of-theart länk förutsägelsemetoder i både noggrannhet och universalitet. Denna studie ger grundläggande insikter i viktiga vetenskapliga problem och kommer att bidra till utvecklingen av informationsfiltreringsteknik.
LV m.fl. REF lade fram ett gemensamt strukturellt likhetsindex som är oberoende av tidigare kunskaper om nätet när det gäller perturbering av adjacensmatrisen.
Toward link predictability of complex networks
{'venue': 'Proceedings of the National Academy of Sciences of the United States of America', 'journal': 'Proceedings of the National Academy of Sciences of the United States of America', 'mag_field_of_study': ['Computer Science', 'Medicine']}