Protest. 2-16

Denne gang var matematikken mest i branchen grafteori. Om at analysere netværk og finde ledere. Det er højaktuelt med de store mængder data, man indsamler via diverse aflytninger og overvågninger – i USA kaldet Homeland Security. Aalborg Universitets afdeling i Esbjerg har forskning i den type “datamining”, og jeg vil se, om jeg kan få dem til at skrive lidt på bloggen. Men idag får i noget om Social Netværks analyse.  

SNA, Analyse af Sociale netværk (Social Network Analysis)

Et social netværk kan i denne sammenhæng være mange forskellige ting. Man repræsenterer forbindelser mellem individer som en graf. For hvert individ har man en liste over andre individer, dette individ er forbundet til. Og denne samling af informationer kan så repræsenteres grafisk som en graf:

(Hentet fra den amerikanske numb3rsblog, ved Mark Bridger)

En graf er den matematiske version af et netværk. Man laver forbindelseslinier, hvor der er forbindelser i netværket – og det kan igen dække over, at folk ringer til hinanden, at de har skrevet artikler sammen, er blevet anholdt sammen, eller hvad man nu har brug for at repræsentere. Internettet er for eksempel en kæmpegraf via links.

Nu har vi netværkene ovre i matematikken, og så kan vi se på dem med matematikværktøjer. Man kan, i samarbejde med sociologer og andre anvendere, definere, hvad det betyder at have et godt netværk, at to netværk er næsten ens, at et (socialt) netværk er skrøbeligt, at en person er central i et netværk etc. Og det er præcis det, SNA går ud på.

Man kan for eksempel se på

Valens: Hvor mange forbindelseslinier går der ud fra en givet knude? Knuderne B, D og E har valens 5, mens K har valens 2.

Tæthed: Hvor tæt ligger en knude på de andre knuder. Afstanden fra K til H (Hvor mange kanter skal man gå ad) er 3, men afstanden fra F til en anden knude er aldrig større end 2. Man definerer tætheden (closeness) for en knude, som den gennemsnitlige afstand til alle andre knuder. For F får man 1,6 hvis jeg har regnet rigtigt (10 andre knuder, og direkte forbundet til B, D, I og K, giver afstandene 4×1+6×2=16, som delse med 10). Mens man for A får 2,3

Kliker: En klike er en mængde knuder, som er parvis forbundet direkte: Knuderne A, B, C, D og E er en klike, og det er G, H, I og J også. (Det er NP-fuldstændigt at finde de(n) maksimale klike i en graf).

Uafhængig mængde: Det “omvendte” af en klike, nemlig en mængde knuder, hvor ingen er forbundet med en kant. For eksempel A, K, I. (Det er NP-fuldstændigt at finde de(n) maksimale uafhængige mængde i en graf).

Mellemliggenhed (Betweenness): I hvor høj grad ligger en knude “imellem” andre knuder. Vælg en knude, v. Lad p og q være to andre knuder. Se på antallet af stier mellem p og q med kortest afstand. Antallet af disse, som går via v, divideres med det samlede antal. Gør det for alle par af andre knuder og læg hele molevitten sammen.

For eksempel er der, hvis vi ser på knuden H ovenfor, ingen korteste stier, der går via H, så mellemliggenhed for H er 0.

Men knuden I ligger på enhver korteste sti mellem en af A, B, C, D, E, F, K og en af G, H, J, så mellemliggenhed for I er 3×7=21.

Knuden F ligger på enhver korteste sti mellem en af A,B,C,D,E,K og en af G,H,I,J, så mellemliggnehed er (mindst) 6×4=24. Desuden ligger F på den eneste korteste vej fra K til B, og på en af de to fra K til D og måske mere, jeg ikke lige har set, så mellemliggenhed af F er mindst 25,5.

Man kan se, at F er central. Selvom valensen kun var 4, og der er andre knuder med valens 5. Og det kan betyde mange ting, alt efter, hvad man har modelleret: Hvis det er smitteveje, vil F blive hurtigt smittet, hvis de andre bliver det, og det er omvendt smart at vaccinere F. Hvis det er et socialt netværk, er mange afhængige af F, så det er sårbart overfor, at F flytter, bliver syg eller måske bare bliver sur på de andre. Hvis det er et terrornetværk er det en god ide at fjerne F, hvad så end det indebærer.

Et andet mål for centralitet eller vigtigheden af en knude, er “egenvektorcentralitet”, hvor man vægter hjørner baseret på, hvor mange andre hjørner, de er forbundet til, og hvor mange disse igen er forbundet til. Det er det, Google gør, i PageRank algoritmen.

Charlie foreslår en “bipartite analysis”.

En todelt (bipartite) graf er en graf, der kan deles op i to mængder af knuder, som hver for sig er uafhængige. der er altså ikke nogen indbyrdes kanter i de to mængder, men kun kanter imellem dem. Grafen ovenfor kan ikke todeles: Antag vi har delt hjørnerne i mængderne M og N. Hvis A er med i den mængden M, kan B, C, D ikke være i M, men hvis B er i N, kan C og D ikke være der. Så C og D kan ikke være i hverken M eller N.

I en bipartite analysis leder man formentlig efter delgrafer, som kan 2-deles. Det har jeg ikke kunnet finde noget litteratur om.

I den matematiske tilgang til grafer, er det ofte nyttigt at se på “adjacency” matricen eller nabomatricen. For dem, der kender matricer, er det nemt at forstå, og andre kan springe over… For en graf med n knuder nummereret fra 1 til n er nabomatricen en nxn matrix med 1 i indgang ij, hvis der er en kant mellem knude i og j, og 0 ellers. (Generelt er det antallet af kanter fra i til j). For grafen ovenfor er den i denne fil matrice2.pdf

Man kan nu manipulere matricen: Benytte matrixmultiplikation, regne egenværdier ud etc. Matricen ganget med sig selv repræsenterer antallet af forbindelser via to kanter. Men det kan I selv lege med…

Man har analyseret forbindelser (ægteskabelig) i de italienske fyrstedømmer og set, at Medicierne spillede en central rolle som forbindelsesled, forbindelser mellem folk, der arbejder på OpenSource programmer, terrornetværk,…

Lidt bonusinformation: 

I udsendelsen nævnes The Weather Underground. Det var en voldelig protestbevægelse i 70’erne, og er altså ikke noget, man har fundet på til serien. Se for eksempel denne omtale af en Dokumentarfilm på IMDB. (Googler man, finder man også en vejrtjeneste under weather underground…) Derimod er organisationen Californians for Peace vist frit opfundet til lejligheden. Men lignende protestbevægelser fandtes.