Sidste Numb3rs-afsnit. Jeg sad og blev helt vemodig; især da jeg så ekstramateriale på DVD’en med skuespillernes afskedsfest…. Nå, men var der matematik? Ja! Noget i grafteoribranchen: Analyse af sociale netværk. Der var søgning i store datamængder og brug af Bayesianske filtre. (Se tidligere på bloggen.)
Netværk og “small world”
Et netværk består af knuder og kanter, der forbinder knuderne. Mange strukturer kan repræsenteres som netværk: Det har vi haft noget om tidligere, men her kommer mere:
De rent fysiske: Byer og flyforbindelser. Huse og elledninger. Byer og veje.
Men også mindre oplagte: Personer og emails mellem dem – en kant mellem A og B viser, der er sendt mails mellem de to personer A og B. Og man kan sætte et tal (en vægt), der repræsenterer antallet af mails – måske to tal, som repræsenterer hhv. mails fra A til B og fra B til A.
Hjernens neuroner interagerer med hinanden, og det kan beskrives som et netværk.
Internettets servere og forbindelser mellem dem, eller WWW, hvor kanterne er links, giver to (forskellige) netværk.
Hjernen, Internettet og andre store netværk er umiddelbart fuldstændig uoverskuelige. Men som vi alle ved, er det en meget begrænset del af nettet/www, vi faktisk bruger. Hjernen og Internettet er “Small World Networks”. At hjernen er det, kan man naturligvis ikke selv mærke, men det er der forskere, der har set på. Se Plus Magazine om komplekse systemer og om hjernen og twitterspace.
Filmen, fra Plus Magazine artiklen ovenfor, viser, hvordan hjernens netværk kan opdeles i mindre områder (delmængder af neuronerne), der allesammen har mange forbindelser til hinanden. Disse områder har så forbindelser til hinanden, men ikke så mange. OBS: Et område er ikke nødvendigvis et fysisk område. Man kan godt have forbindelse til moster Gerda i USA, men ikke til genboen.
Skal man analysere et netværk, er det en fordel, hvis man kender den underliggende struktur. Er det et small world netværk, er forbindelserne opdelt i “indenrigs” (internt i de grupper, der har tætte forbindelser) og “udenrigs”.
Eksempelvis har forskere fra Stanford undersøgt fMRI fra Alzheimerpatienter og set, at deres “udenrigskommunikation” er ok, mens der er problemer med nogle områders kommunikation internt. Så der groft sagt når information rundt hurtigt, men fra visse områder er det en forkert information.
Man kan bruge small world, når man opbygger netværk af computere (eller interne forbindelser i computeren.) Måske er det bedst at lave lokale tætte forbindelser – det kaldes kliker – og forbinde hver klike med andre kliker, men ikke hvert medlem af kliken med hvert medlem af andre kliker. Om det er en god ide, afhænger af, hvad netværket skal kunne.
Definition:
Small world grafer er karakteriseret ved, at gennemsnitsafstanden mellem to knuder (antallet af kanter man skal gå ad for at komme fra en knude til en anden) vokser som Log(N), hvor N er antallet af knuder. Og at “clustering koefficienten” er høj. -Det er ikke en præcis definition, men der er, så vidt jeg kan finde ud af, ikke en, man alle er enige om….
En anden tilgang er at analysere, hvor mange kanter, der er i hvert hjørne. Og se på antallet af hjørner med en kant, antallet med to etc. Det regner man om til sandsynligheden for, at et tilfældigt hjørne har et givet antal kanter. (Man dividerer simpelthen antallet af hjørner, der har 7 kanter med det totale antal hjørner. det er sandsynligheden for at finde et hjørne med 7 kanter. ) Man får en sandsynlighedsfordeling. Fordelingen af antallet af hjørner er en egenskab ved grafer. Small world grafers kantfordeling ligner et polynomium. Den har tyk hale – der er stor sandsynlighed for mange kanter.
D.J.Watts og S.Strogatz skrev en artikel i Nature i 1998, Collective dynamics of ‘small-world’ networks, hvor de navngav fænomenet. Watts skrev den populære bog “Six degrees of separation”. Steven Strogatz har skrevet nogle klummer i New York Times om matematik. De er meget velskrevne.
Egenskaber ved small world grafer:
Afstanden melem tilfældige knuder er kort – som i et netværk, hvor kanterne er indsat tilfældigt. (Med samme totale antal kanter. Afstanden er naturligvis kortes, hvis alle er forbundet med alle.)
Fjernes en tilfældig knude vil gennemsnitsafstanden mellem andre knuder sandsynligvis ikke stige voldsomt. (Gør man det i en graf, hvor kanterne er indsat tilfældigt, er der stor sandsynlighed for, at andre skal gå en omvej).
Til gengæld er small worlds sårbare overfor bevidste angreb: Man kan ved at fjerne få udvalgte knuder skabe mange problemer for de andre.
Matematikken bag er grafteori kombineret med bl.a. sandsynlighedsteori.
| Labeled graph | Adjacency matrix |
|---|---|
 |  |
Otto snakkede om “adjacency matricer”. Her er et billede fra Wikipedia. Der er et 1-tal i femte tal i øverste række, fordi der er en kant fra knude 1 til knude 5. I række 6 er der kun et 1-tal, nemlig i fjerde søjle. Det skyldes, at knude nummer 6 kun er forbundet til knude 4. Ganger man matricen med sig selv, kan man se, hvilke knuder, der kan forbindes i to skridt. Etc.