Abstract-A key challenge in the social network community is the problem of network generation - som är, hur kan vi skapa syntetiska nätverk som matchar egenskaper som traditionellt finns i de flesta verkliga nätverk? Viktiga egenskaper som finns i sociala nätverk inkluderar en makt lag grad distribution, liten diameter, och stora mängder kluster. De flesta nuvarande nätgeneratorer, såsom Chung Lu- och Kronecker-modellerna, ignorerar dock till stor del den klusterbildning som finns i en graf och fokuserar på att bevara annan nätstatistik, såsom distributionen av ellag. Modeller som den exponentiella slumpmässiga grafmodellen har en transitivitetsparameter som kan fånga kluster, men de är beräknings svårt att lära, vilket gör skalning till stora verkliga nätverk intractable. I detta arbete föreslår vi en förlängning till Chung Lu slumpmässiga grafen modell, Transitive Chung Lu (TCL) modell, som innehåller begreppet transitiva kanter. Specifikt kombinerar den standard Chung Lu modellen med kanter som bildas genom transitiv stängning (t.ex. genom att ansluta en "vän till en vän"). Vi bevisar att TCL: s förväntade gradfördelning är lika med graden av fördelningen av den ursprungliga indatagrafen, samtidigt som den ger möjlighet att fånga klustret i nätverket. Den enda parameter som krävs av vår modell kan läras i sekunder på grafer med miljontals kanter; nätverk kan genereras i tid som är linjär i antalet kanter. Vi demonstrerar prestandan av TCL på fyra verkliga sociala nätverk, inklusive en e-post dataset med hundratusentals noder och miljontals kanter, visar TCL genererar grafer som matchar graden distribution, kluster koefficienter och humle tomter i de ursprungliga nätverken.
Transitive Chung Lu Model (TCL) REF.
Fast Generation of Large Scale Social Networks While Incorporating Transitive Closures
{'venue': '2012 International Conference on Privacy, Security, Risk and Trust and 2012 International Confernece on Social Computing', 'journal': '2012 International Conference on Privacy, Security, Risk and Trust and 2012 International Confernece on Social Computing', 'mag_field_of_study': ['Computer Science']}