Eftersom en ansluten graf G = (V, E), där V betecknar uppsättningen noder och E uppsättningen av kanter av grafen, längden (det vill säga antalet kanter) av den kortaste vägen mellan två noder v och w betecknas av d (v, w ). Närheten centralitet av en vertex v definieras sedan som n-1 w -V d (v,w ), där n = -V -. Denna åtgärd används allmänt i analysen av verkliga komplexa nätverk, och problemet med att välja k mest centrala hörn har analyserats djupt under det senaste årtiondet. Detta problem är dock inte lätt att beräkna, särskilt för stora nätverk: i den första delen av artikeln, visar vi att det inte går att lösa i tid O (-) 2-ε ) på riktade grafer, för varje konstant ε > 0, under rimliga komplexa antaganden. Dessutom föreslår vi en ny algoritm för att välja k mest centrala noder i en graf: vi experimentellt visar att denna algoritm avsevärt förbättrar både läroboksalgoritmen, som bygger på att beräkna avståndet mellan alla par av hörn, och state of the art. Till exempel kan vi beräkna de översta k noderna på några dussintals sekunder i verkliga nätverk med miljontals noder och kanter. Slutligen, som en fallstudie, beräknar vi de 10 mest centrala aktörerna i Internet Movie Database (IMDB) samarbetsnätverk, där två aktörer är kopplade om de spelade tillsammans i en film, och i Wikipedia citering nätverk, som innehåller en riktad kant från en sida p till en sida q om p innehåller en länk till q. Graphs 53:3 och hundratals miljoner kanter. Den nya metoden kombinerar den BFS-baserade algoritmen med en beskärningsteknik: under algoritmen, vi beräkna och uppdatera övre gränser på närhet av alla noder, och vi utesluter en nod v från beräkningen så snart dess övre gräns är "liten nog", det vill säga, vi är säkra på att v inte tillhör de översta k noderna. Vi föreslår två olika strategier för att ställa in de initiala gränserna, och två olika strategier för att uppdatera gränserna under beräkningen: detta innebär att vår algoritm kommer i fyra olika varianter. De experimentella resultaten visar att olika variationer fungerar bra på olika typer av nätverk, och den bästa variationen av vår algoritm överträffar drastiskt både ett probabilistiskt tillvägagångssätt (Okamoto et al. 2008), och den bästa exakta algoritmen hittills (Olsen et al. 2014)................................................................. Vi har för första gången beräknat de 10 mest centrala noderna (när det gäller närhetsmåttet) i nätverk med miljontals noder och hundratals miljoner kanter, och vi har gjort det på mycket kort tid. Ett viktigt exempel är nätverket wiki-Talk, som också användes i (Sariyüce et al. 2013), där författarna föreslår en algoritm för att uppdatera närhet centraliteter efter kant tillägg eller raderingar. Vår prestation är cirka 30 000 gånger bättre än prestandan av läroboksalgoritmen: om bara den mest centrala noden behövs, kan vi återskapa den från grunden mer än 150 gånger snabbare än den geometriska genomsnittliga uppdateringstiden i (Sariyüce et al. 2013)................................................................. Dessutom är vårt tillvägagångssätt inte bara mycket effektivt, utan det är också mycket lätt att koda, vilket gör det till en mycket bra kandidat att implementera i befintliga grafbibliotek. Vi tillhandahåller en implementering av det i NetworKit (Staudt et al. 2016) och en av dess variationer i Sagemath (Csárdi och Nepusz 2006). Vi skissar de viktigaste idéerna i algoritmen i Avsnitt 4, och vi ger alla detaljer i Avsnitt 5-8. Vi utvärderar experimentellt den nya algoritmens effektivitet i Avsnitt 9. Dessutom kan vårt tillvägagångssätt enkelt utvidgas till någon centralitet mäter i form c (v) = w v f (d (v, w ) ), där f är en minskande funktion. Bortsett från Lins index, nästan alla metoder som försöker generalisera närhet centralitet till frånkopplade grafer faller under denna kategori. Den mest populära bland dessa åtgärder är harmonisk centralitet (Marchiori och Latora 2000), definieras som h(v) = w v 1 d (v,w ). För fullständighetens skull visar vi i Avsnitt 9 att vår algoritm fungerar bra även för denna åtgärd. I den sista delen av artikeln (avsnitt 10 och 11) behandlar vi två fallstudier: aktörsnätverket (1.797.446 hörn, 72.880.156 kanter) och Wikipedias citeringsnätverk (4.229.697 hörn, 102.165.832 kanter). I aktörsnätverket analyserar vi utvecklingen av de 10 mest centrala hörnen, med tanke på ögonblicksbilder tagna vart femte år mellan 1940 och 2014. Beräkningen utfördes på lite mer än 45 minuter. I Wikipedia fallstudien anser vi att både standardciteringsnätverket, som innehåller en riktad kant (p, q) om p innehåller en länk till q, och det omvända nätverket, som innehåller en riktad kant (p, q) om q innehåller en länk till p. För de flesta av dessa grafer, kan vi beräkna de 10 mest centrala sidorna på några minuter, vilket gör dem tillgängliga för ytterligare analyser.
REF utvecklade en algoritm för att hitta topp k högsta närhet centralitet hörn som finner en övre gräns på närhet poäng för varje vertex.
Computing top-k Closeness Centrality Faster in Unweighted Graphs
{'venue': 'TKDD', 'journal': None, 'mag_field_of_study': ['Computer Science', 'Mathematics']}