Kunsten å avdekke strukturer i komplekse nettverk

Nettverk, som er et system av forbindelser, finnes over alt rundt oss, som i veinettverk, strømnett, nettverk av nevroner og datanettverk, og mer abstrakt som i sosiale nettverk og kommunikasjonsnettverk.  Studiet av strukturer og egenskaper ved slike nettverk er en vesentlig del av informasjonsteknologi, sosiologi, ingeniørvitenskap, lingvistikk og så videre.  Et nettverk uten åpenbare topologiske strukturer, som nevrale, biologiske, sosiale og kommunikative nettverk, kalles ofte komplekse nettverk.

En av de essensielle oppgavene i nettverksteori er å identifisere viktige noder i komplekse nettverk.  Noen eksempler på viktige noder kan være infrastrukturnoder i datanettverk, superspredere av sykdom, og nøkkelpersoner i sosiale nettverk.  Grunnet stadig større tilgjengelige datamengder og nettverk, er det mer kritisk enn noensinne at algoritmer for å identifisere slike noder er raske.

Å oppdage nøkkelpersoner kan gjøres på flere måter.  En nylig introdusert metode hadde en hittil ukjent kompleksitet.  Å fastslå kompleksiteten til et problem er et fundamentalt spørsmål innen datavitenskap og matematikk.  Hva som var kompleksiteten til denne sentralitetsindeksen har vært et åpent spørsmål i over femten år.  I denne avhandlingen blir det fastslått at det dessverre ikke er mulig å finne slike nøkkelpersoner innen rimelig tid.  På den positive siden blir det vist, til alles overraskelse, at eksponentiell tid ikke er nødvendig.

Et annet problem i komplekse nettverk er å finne underliggende grupper og hierarkier.  Om man har fått tilgang til et kommunikasjonsnettverk, kan det være interessant å avdekke den underliggende hierarkistrukturen.  I denne oppgaven blir det også vist at en nylig foreslått hierarkiindeks ikke lar seg beregne i rimelig tid; gitt et stort nok nettverk vil det være umulig å finne det korrekte underliggende hierarkiet.  På den positive siden blir det gitt gode matematiske garantier for preprosessering.

Personalia:

Pål Grønås Drange (1983) født i Bergen, har en mastergrad fra Universitetet i Bergen (2011) og liker å klatre.