Mellanhet centralitet är kärnan i både transport och strukturella sårbarhet egenskaper komplexa nätverk, men det är beräknings dyrt, och dess mätning för nätverk med miljontals noder är nästan omöjligt. Genom att införa en flerskalig nedbrytning av kortaste vägar, visar vi att bidrag till mellanhet som kommer från geodesik inte längre än L lyda en karakteristisk skalning vs L, som kan användas för att förutsäga fördelningen av de fulla centraliteterna. Metoden illustreras också på ett verkligt socialt nätverk av 5,5 × 10 6 noder och 2,7 × 10 7 länkar. Många komplexa nätverk utvecklas organiskt utan någon centraliserad kontroll eller design, och därför har intensiv forskning ägnats åt att förstå deras prestandaegenskaper och ännu viktigare, deras sårbarheter och fellägen. I dessa studier spelar centralitetsåtgärder en grundläggande roll (som ursprungligen infördes inom samhällsvetenskapen [1] [2] [3] [4] [5] ), särskilt mellanhet centralitet [6] [7] [8] [9]. Mellanhet centralitet (BC) av en nod (kanten) definieras som fraktionen av alla geodesik (kortaste vägar) som passerar genom den noden (kanten). Eftersom transport tenderar att minimera kostnaden/tiden för rutten från källa till destination, geodesik, och därmed centralitet åtgärder och deras fördelningar kommer starkt att avgöra övergripande transportprestanda. Intressant nog är geodesik inte bara viktigt för nätverksflöden utan också för strukturell konnektivitet: att ta bort noder (kanter) med hög centralitet man får en snabb ökning i diameter, och så småningom den strukturella uppdelningen av grafen. Analys av trafik, eller informationsflöde [7, [9] [10] [11] [12] [13] [14], nätsårbarhet inför attacker [15], kaskadfel [16, 17] eller epidemier [18], alla omfattar beräkningar mellanhet. Tyvärr är beräkningen av förhållandet mycket kostsam [13, 14, [19] [20] [21] [22] och för stora nätverk med miljoner till miljarder noder är det nästan omöjligt, och därför behövs approximeringsmetoder. Befintliga approximationer [23, 24] är dock provtagningsbaserade och dåligt kontrollerade. Här visar vi att när geodesik begränsas till en maximal längd L, antar motsvarande områdesbegränsad L-mellanhet (introducerad av Borgatti och Everett som avgränsad avstånd mellanhet [5] ) för stora grafer en karakteristisk skalningsform som funktion av L. Denna skalning kan sedan användas för att förutsäga mellanhetens fördelning i (vanligtvis ouppnåelig) diametergräns, och med god approximation, för att förutsäga rangordningen av noder/kanter genom mellanhet. Dessutom genererar den områdesbegränsade metoden l-mellanhetsvärden för alla noder och kanter och för alla 1 ≤ l ≤ L, vilket ger systematisk information om geodesik på alla längder. Detta är av intresse i sin egen rätt, när den transporterade enheten har en liten överföringsannolikhet (rummor, virus) och därmed hög attritionshastighet, inte utforska längre geodesik. Som vi visar har L-vågen redan uppnåtts för relativt små L-värden och det blir allt mindre ny information om BC-distribution och rankning när man går från L till L + 1. Den beräkningsmässiga overhead, dock, inblandade i L → L+1 steg är vanligtvis enorm. Den intervallbegränsade centralitet algoritm presenteras här, även i diameter gräns (L = D), har ingen större komplexitet än de för närvarande kända snabbaste algoritmer av Brandes [19] och Newman [20], det vill säga O(N M ), där N är antalet noder och M är antalet (direkta) kanter, och det är helt parallelliserbara. För L < D kör vår algoritm sublinjärt i O(N M ), vilket gör det möjligt att studera nätverk med miljontals noder. Som en illustration analyserade vi ett socialt nätverk (SocNet) som härleddes från mobilens spårloggar [25] med ett gigantiskt kluster med N = 5, 568, 785 och M = 26, 822, 764. För detta nätverk beräknade vi alla L-mellanhet centraliteter (L-BC) för alla noder och kanter upp till L = 5 på 6 dagar, på 10 processorer. Med ökande L rankingen av de högsta BC noderna fryser och man kan förutsäga de översta noderna tidigt. Antalet geodesik som går genom dessa noder exploderar dock med L. Till exempel, medan noden med högsta centralitet för L = 4 har 40, 084, 702 geodesik, för L = 5 har den 500, 903, 498 av dem passerar igenom. Beräkna mellanhet centralitet av en nod eller kant i en riktad graf G(V, E) kräver att räkna antalet alla-par kortaste riktade vägar incident på den. Här inkluderar vi slutpunkter, men algoritmen kan lätt ändras för att utesluta dem, eller producera andra varianter. Den stress centralitet (SC) S(i) av en node i  på V är helt enkelt summan av det totala antalet σ mn (i) av kortaste riktade vägar från node m till n som går igenom i, S(i) = m,n till V σ mn (i). Mellanhet centralitet (BC) [6, 8] normaliserar antalet banor genom en nod genom det totala antalet banor (σ mn ) för ett givet källdestination par (m, n): B(i) = m,n σ mn (i)/σ mn. Likvärdiga mängder kan definieras för en kant (j, k) E: S(j, k) = m,n-V σ mn (j, k) och B(j, k) = m,n-V σ mn (j, k)/σ mn.
Mária m.fl. REF använder den kortaste vägen med en längd som inte är större än L för en beräkning av mellanhet.
Centrality scaling in large networks
{'venue': 'Phys. Rev. Lett 105, 038701, 2010', 'journal': None, 'mag_field_of_study': ['Medicine', 'Physics']}