Abstrakt. Nätverk kan representeras som evolutionära grafer i en mängd olika spatio-temporala tillämpningar. Förändringar i noder och kanter över tiden kan också resultera i motsvarande förändringar i strukturella garph egenskaper såsom kortaste väg avstånd. I det här dokumentet studerar vi problemet med att upptäcka de mest betydande förändringarna på kortaste vägen mellan två ögonblicksbilder av en graf som utvecklas. Även om problemet kan lösas med två tillämpningar av alla-par kortaste vägen algoritm, en sådan lösning skulle vara extremt långsam och opraktisk för mycket stora grafer. Detta beror på att när en graf kan innehålla miljontals noder, även lagring av avstånd mellan alla nodpar kan bli ineffektiv i praktiken. Därför är det önskvärt att utforma algoritmer som direkt kan bestämma de betydande förändringarna i kortaste banavstånd, utan att materialisera avstånden i enskilda ögonblicksbilder. Vi presenterar algoritmer som är upp till två storleksordningar snabbare än en sådan lösning, samtidigt som vi behåller jämförbar noggrannhet.
Till exempel, REF beskriva en metod som gör det möjligt att upptäcka de mest betydande förändringarna i avståndet mellan noder, förutsatt att sådana förändringar motsvarar viktiga händelser i utvecklingen av grafen.
Finding Top-k Shortest Path Distance Changes in an Evolutionary Network
{'venue': 'SSTD', 'journal': None, 'mag_field_of_study': ['Computer Science']}