mellomsentralitet

Mellomsentralitet, også kalt betweenness centrality, er et måltall i grafteori som beskriver i hvilken grad en node ligger på korteste veier mellom andre par av noder. En høy mellomsentralitet indikerer at noden ofte fungerer som mellomstasjon eller bro i informasjonsflyt, og dermed kan ha betydning for effektivitet og kontroll i nettverket. Begrepet brukes for å identifisere formidlere, flaskehalser og kritiske koblingspunkter i ulike typer nettverk, som sosiale nettverk, biologiske nettverk og transport- eller kommunikasjonsinfrastrukturer.

Beregningen av mellomsentralitet for en node v innebærer å summere andelen av de korteste stiene mellom alle par s og t (der s og t er forskjellige fra hverandre og fra v) som passerer gjennom v. Mer presist: B(v) er summen over s≠t, s≠v, t≠v av σ_st(v)/σ_st, der σ_st er antall korteste stier fra s til t og σ_st(v) er antall av disse som går gjennom v. Normalisering brukes ofte for å gjøre tallene sammenlignbare på tvers av nettverk. I urettede grafer deles ved (n-1)(n-2)/2, i rettede grafer deles ved (n-1)(n-2).

Brandes-algoritmen er vanlig brukt for å beregne mellomsentralitet effektivt. Den kjører et korteste-sti-søk ( BFS for uveide grafer, Dijkstra for vekta grafer) fra hver node som kilde og akkumulerer bidragene tilbake til kilden. Dette gir i praksis O(nm) tid for uveide nettverk og omtrent O(nm + n^2 log n) for vekta nettverk, avhengig av implementasjon. Anvendelser inkluderer identifikasjon av nøkkelpersoner i sosiale nettverk, målrettet markedsføring, oppdagelse av flaskehalser i transport og analyse av kritiske proteinnettverk.

Begrensninger: verdiene er følsomme for små endringer i grafen; i svært store nettverk kan beregningen være kostbar, og tolkningen av mellomsentralitet bør ses i lys av kontekst og andre nettverksmål.