大象传媒

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.