Degree distribution modeller är otroligt viktiga verktyg för att analysera och förstå strukturen och bildandet av sociala nätverk, och kan hjälpa till att styra utformningen av effektiva graf algoritmer. I synnerhet, Power-law examen distribution har länge använts för att modellera strukturen av online sociala nätverk, och är grunden för algoritmer och heuristik i graf applikationer såsom influence maximization och social sökning. Tillsammans med de senaste mätresultaten väcktes vårt intresse för detta ämne av våra egna experimentella resultat på sociala grafer som avvek avsevärt från dem som förutspåddes av en Power-law-modell. I detta arbete söker vi en djupare förståelse av dessa avvikelser och föreslår en alternativ modell med betydande konsekvenser för grafalgoritmer och tillämpningar. Vi börjar med att kvantifiera denna artefakt med hjälp av en mängd verkliga sociala grafer, och visar att deras strukturer inte exakt kan modelleras med hjälp av elementära fördelningar inklusive Power-law. Istället föreslår vi ParetoLognormal (PLN) modell, verifiera dess godhet-of-fit med hjälp av grafiska och statistiska metoder, och presentera en analytisk studie av dess asymptotiska skillnader med Power-law. För att visa de kvantitativa fördelarna med PLN-modellen jämför vi resultaten från tre omfattande graftillämpningar på verkliga sociala grafer med dem på syntetiska grafer som genereras med hjälp av PLN- och Power-law-modellerna. Vi visar att syntetiska grafer som genereras med hjälp av PLN är mycket bättre prediktorer av grad fördelningar i verkliga grafer, och producerar experimentella resultat med fel som är order-of-magnitude mindre än de som produceras av Power-law-modellen.
I REF, Sala et al. analysera Facebooks sociala nätverksdata och rapportera att Pareto lognormala (PLN) distributioner är mycket bättre prediktorer av examen distributioner i verkliga grafer än power-law distributioner är.
Revisiting Degree Distribution Models for Social Graph Analysis
{'venue': 'ArXiv', 'journal': 'ArXiv', 'mag_field_of_study': ['Computer Science', 'Physics']}