netwerkafstand

Netwerkafstand is de minimale lengte van een pad tussen twee knooppunten in een netwerk. In een ongewogen netwerk wordt de afstand meestal gemeten als het aantal randen in de kortste pad. In gewogen netwerken, waarbij elk rand een gewicht heeft dat kosten, lengte of tijd vertegenwoordigt, is de afstand de som van de gewichten langs de kortste pad.

Berekenen van netwerkafstand gebeurt met verschillende algoritmen afhankelijk van het type netwerk. Voor ongewogen netwerken bepaalt breadth-first search (BFS) de kortste padlengte. Voor gewogen netwerken gelden Dijkstra’s algoritme (bij niet-negatieve gewichten) en het Bellman-Ford-algoritme (ook bij aanwezigheid van negatieve gewichten). All-pairs afstanden kunnen worden verkregen met Floyd-Warshall of Johnson’s algoritme.

Eigenschappen: afstanden zijn altijd niet-negatief. In onverwijderde/undirected netwerken is de afstand vaak symmetrisch; in directed graphs kan de afstand van A naar B verschillen van die van B naar A. Afstanden voldoen aan de driehoeksongelijkheid. Voor knopen geldt de eccentriciteit (de grootste afstand vanaf een knoop naar alle anderen), de diameter (de grootste van alle paren afstanden) en de straal (de minimale eccentriciteit).

Toepassingen: netwerkanalyse en routing, verkeersplanning, sociale netwerken (zoals stappen tussen personen), logistiek en epidemiologie. Varianten van netwerkafstand richten zich op verschillende aspecten van netwerkconnectiviteit en dynamiek, zoals geodetische afstand in ruimtelijke netwerken, effectieve weerstand afstand, diffusieafstand en commute distance.