Abstrakt. Vi anser att inkrementell beräkning av mellanhet centralitet (BC) av alla hörn i en graf G = (V, E), riktad eller oriktad, med positiva reella kant-vikter. Den nuvarande allmänt använda algoritmen är Brandes algoritm som körs i O(mn + n 2 log n) tid, där n =  och m =. Vi presenterar en inkrementell algoritm som uppdaterar BC poäng för alla hörn i G när en ny kant läggs till G, eller vikten av en befintlig kant minskas. Vår inkrementella algoritm körs i O(m ′ n+n 2 ) tid, där m ′ begränsas av m * =  och E * är den uppsättning kanter som ligger på en kortaste vägen i G. Vi uppnår samma gräns för den mer allmänna inkrementella uppdateringen av en vertex v, där edge uppdateringen kan utföras på någon delmängd av kanter incident till v. Vår inkrementella algoritm är den första algoritmen som är asymptotiskt snabbare på sparse grafer än recomputing med Brandes algoritm även för en enda edge uppdatering. Det är också sannolikt att vara mycket snabbare än Brandes algoritm på täta grafer eftersom m * är ofta nära linjär i n. Vår inkrementella algoritm är mycket enkel, och vi ger en effektiv cache-oblivious implementation som ådrar sig O(scan(n 2 )+n·sort(m ′ ) cache missar, där skanning och sortering är välkända åtgärder för effektiv cachelagring. Vi ger också en statisk BC-algoritm som körs i tiden O(m * n + n 2 log n), som är snabbare än Brandes algoritm på någon graf med m = (n log n) och m * = o(m). Mellanhet centralitet (BC) är en allmänt använd åtgärd i analysen av stora komplexa nätverk. BC av en nod v i ett nätverk är fraktionen av alla kortaste vägar i nätverket som går igenom v, och denna åtgärd används ofta som ett index som bestämmer den relativa betydelsen av v i nätverket. Vissa tillämpningar av BC inkluderar att analysera sociala interaktionsnätverk [12], identifiera dödlighet i biologiska nätverk [21], och identifiera nyckelaktörer i terroristnätverk [13, 4]. Med tanke på att de berörda nätverken förändras är det önskvärt att ha algoritmer som beräknar BC snabbare än att beräkna det från grunden efter varje förändring. Vårt huvudsakliga bidrag är den första inkrementella algoritm för beräkning BC efter en inkrementell uppdatering på en kant eller på en vertex som är bevisligen snabbare på glesa grafer än den allmänt använda statiska algoritm av Brandes [3]. Med en inkrementell uppdatering på en kant (u, v) menar vi en minskning av vikten av en befintlig kant (u, v), eller tillägg av en ny kant (u, v) med ändlig vikt om (u, v) inte finns i grafen; i en inkrementell vertex uppdatering, uppdateringar kan ske på någon delmängd av kanter incident till v, inklusive tillägg av nya kanter. Låt G = (V, E) vara en graf med positiva reella kantvikter. Låt n = "V" och m = "E" För att ange vårt resultat behöver vi följande definitioner. För en vertex x V, låt m * x betecknar antalet kanter som ligger på kortaste vägar genom x. Letm * betecknar genomsnittet över alla m * x, d.v.s.,m * = 1 n x till V m * x. Slutligen, låt m * betecknar det totala antalet kanter som ligger på kortaste vägar i G. För vår inkrementella gräns, anser vi maximum av var och en av dessa termer i de två graferna före och efter uppdateringen. Här är vårt huvudsakliga resultat. Vår metod är att effektivt upprätthålla den enda källan kortaste vägar (SSSP) riktad acyklisk graf (DAG) rotad vid varje källa s  på V, och därför se till att efter varje förändring vi bara undersöka
Nasre m.fl. REF presenterar en tätare övre gräns för O(nm * ) på tids komplexitet, där m * är antalet kanter som ligger på kortaste vägar.
Betweenness Centrality -- Incremental and Faster
{'venue': 'ArXiv', 'journal': 'ArXiv', 'mag_field_of_study': ['Computer Science', 'Mathematics']}