Naturlige nettverk

Abstract

En innføring i naturlige nettverk. Vi forklarer og diskuterer begrepet naturlige nettverk og vurderer hvilke nettverk som bør kalles naturlige. Vi ser på forskjeller og likheter mellom tilfeldige, planlagte og naturlige nettverk. Vi gir en innføring i "verden er liten" fenomenet og strukturell balanse. Vi vurderer kompleksiteten for å avgjøre om et nettverk har strukturell balanse. Vi avslutter med hva som kan gjøres for å forbedre kjøretiden på algoritmer der naturlige nettverk er del av innput. En parameter for rettede grafer som kan bli viktig i denne sammenheng er Kelly-bredde. Siste del av oppgaven er opptrykk av en artikkel, på engelsk, som gir den første polynomiske algoritmen for gjenkjenning av rettede grafer med Kelly-bredde 2.