Sammanfattning av denna webbsida: En nods excentricitet i en graf definieras som längden på en kortaste väg som börjar vid den noden. Ecentricitetsfördelningen över alla noder är en relevant beskrivande egenskap hos grafen, och dess extrema värden gör det möjligt att härleda åtgärder som radie, diameter, centrum och periferi av grafen. I detta dokument beskrivs två nya metoder för beräkning av excentricitetsfördelningen av stora grafer som sociala nätverk, webbgrafer, biologiska nätverk och routingnätverk. Vi föreslår först en exakt algoritm baserad på excentricitet lägre och övre gränser, som uppnår betydande hastigheter jämfört med den enkla algoritmen när man beräknar både de extrema värdena av distributionen samt excentricitetsfördelningen som helhet. Den andra algoritmen som vi beskriver är en hybridstrategi som kombinerar det exakta tillvägagångssättet med en effektiv provtagningsteknik för att få en ännu större hastighetshöjning på beräkningen av hela excentricitetsfördelningen. Vi utför en omfattande uppsättning experiment på ett antal stora grafer för att mäta och jämföra våra algoritmers prestanda, och demonstrera hur vi effektivt kan beräkna excentricitetsfördelningen av olika stora verkliga grafer.
Takes och Kosters REF presenterade en exakt excentrisk beräkningsalgoritm, baserad på lägre och övre gränser på excentriciteten av varje vertex i grafen.
Computing the Eccentricity Distribution of Large Graphs
{'venue': 'Algorithms', 'journal': 'Algorithms', 'mag_field_of_study': ['Mathematics', 'Computer Science']}