Närhet centralitet, först beaktas av Bavelas (1948), är ett viktigt mått på en nod i ett nätverk som bygger på avstånden från noden till alla andra noder. Den klassiska definitionen, som föreslagits av Bavelas (1950), Beauchamp (1965) och Sabidussi (1966), är (omvänt av) den genomsnittliga avståndet till alla andra noder. Vi föreslår den första mycket skalbara (nära linjär-tid bearbetning och linjära rymden overhead) algoritm för att uppskatta, inom en liten relativ fel, den klassiska närhet centraliteter av alla noder i grafen. Vår algoritm gäller för oriktade grafer, samt för centralitet som beräknas med avseende på tur- och returavstånd i riktade grafer. För riktade grafer föreslår vi också en effektiv algoritm som approximerar generaliseringar av klassisk närhet centralitet till utgående och inkommande centraliteter. Även om den inte ger de värsta teoretiska approximationsgarantierna, är den utformad för att fungera bra i verkliga nätverk. Vi utför omfattande experiment på stora nätverk, visar hög skalbarhet och noggrannhet.
Den klassiska närhet centralitet REF karakteriserar hur nära en nod är till andra noder i en graf, och kan enkelt ändras för att mäta hur nära de andra noderna till mål noden.
Computing classic closeness centrality, at scale
{'venue': "COSN '14", 'journal': None, 'mag_field_of_study': ['Computer Science']}