På bloggen for et par uger siden, skrev jeg om pseudotilfældige tal. Det er vigtigt at kunne frembringe tilfældige tal. Det må de amerikanske immigrationsmyndigheder sande. De har tilbagekaldt resultatet af årets lodtrækning om visa, fordi det ikke var tilfældigt nok. “The results were not valid because they did not represent a fair, random selection of entrants, as required by U.S. law. “
Man kan godt få visum udenom lodtrækningen, men der udloddes altså også nogle visa via lodtrækning.

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.

Lige lidt mere om punkt match.
På http://greatpanic.com/pntmatch.html er beskrivelse af, Denton/Beveridge algoritem. To billeder gennesøges først for hjørnepunkter med en hjørnepunktsalgoritme. Matching sker iteativt: Start med en lille delmængde af billede 1 og find et match til dem. Nu forsøger vi at udvide med endnu en lille delmængde etc. Tilder ikke er flere muligheder. Hvis alle er matchet, er vi glade. Ellers starter vi forfra med en ny delmængde (en “seeding”, et såsæd.) udvider etc.

Billedet fra http://greatpanic.com/pntmatch.html viser, hvordan punkter, der matches iterativt.

Mere kendt er RANSAC, (RANdom SAmple and Consensus) som
1) Vælger (tilfældigt /random) en lille mængde punkter og matchende punkter
2) Udfra dette match beskriver en afbildning (rotation og parallelforskydning for eksempel)
3) Regner på, hvor godt resten af punkterne matches ved denne afbildning.

Jeg fik denne Calculus Rhapsody fra projektet Maths in the City. Nyd den…

Der var matematik i, da Carlie gennemsøgte overvågningsvideooptagelser, for at finde morderen. Jeg hørte det som “Point pattern matching” og line detection/edge detection. Der var “gait analysis”, hvor man identificerer folk på måden, de går på. Så var der separation af skygger på deb grumme video.

Point pattern matching
Jeg har fundet en “tutorial” om det overordnede problem: Man har nogle punkter, et punktmønster, givet ved deres koordinater (x1,…,xd), som kan repræsentere sted, farve, hastighed,…. Lad os sige, vi har 100 af dem på èt billede. Og vi har 100 punkter, et andet punktmønster, på et andet billede – på en anden overvågningsvideoer for eksempel. Er de så “det samme”, altså omrids af samme person, samme bil,…
Det kan de godt være, uden at se ens ud. Man kan se dem fra en anden vinkel, der kan være ændret lys, …

Det beskrives matematisk ved nogle tilladte afbildninger (funktioner) tænk f.eks. på rotationer. Spørgsmålet lyder nu: Findes der en tilladt afbildning, der bringer det ene punktmønster over i det andet.
Og ydermere: Findes der en algoritme, der afgør det? Og afgør det hurtigt.

Lad os holde os til translationer (parallelforskydning) og rotationer. Og at vores punkter har to koordinater, i.e., det foregår i planen. Vi har to punktmønster, A og B. Opgaven er at flytte A saa tæt på B som muligt, og så dernæst afgøre, om det er tæt nok til, at vi vil sige A og B er billeder af det samme.

Eksempel: Hvis der er tre punkter p,q,r i A og tre punkter s,t,u i B, så gælder det om at skubbe trekanten givet ved a,b,c over i trekanten s,t,u. Og det er ikke klart, om a skal ligge tættest på s eller t eller u.

Det er et enormt område, der er anvendelser mange steder, og algoritmerne tilpasses det område, de skal bruges på. I astronomi kunne man måske interessere sig for at finde stjernekonstellationer. De består af et lille antal punkter, så en optimal algoritme til det kan være helt anderledes end den, der bruges til store punktmængder.
Med et lille antal punkter kan man sommetider bruge en “brute force” algoritme, som gennemsøger alle flytninger af A og ser, hvilken der giver kortest afstand til B. Afstand til B findes ved (d(p,s)+d(q,t)+d(r,u)) hvor d(p,q) er afstanden fra det flyttede punkt p til q
og så d(p,t)+d(q,u)+d(r,s)
og endelig d(p,u)+d(q,s)+d(r,t)
Den mindste af disse er afstanden – vi har så taget hensyn til, at vi ikke ved, hvilke hjørner i A, der skal svare til hvilke i B. Kender man ikke “omløbsretningen ” for A og B er der flere muligheder, man skal undersøge.

Skyggeseparation.
Her er en temmelig langhåret artikel om, hvordan man finder det, der er gemt i skyggen på et billede. Der er fysik i: Lys polariserer, og det skal udnyttes. I denne artikel kan de ikke behandle gamle billeder. Man optager billeder med information om polarisering (ved at optage på flere bølgelængder, tror jeg nok), og så kan man bagefter finde det, der er i skyggerne.
Andre tilgange (shadow segmentation hedder det, hvis I vil søge) går ud på, at spketret – fordeleingen af rød, grøn, blå i skyggen er anderledes end i noget, der er belyst. På den måde kan man automatisk opdage, når noget er i skyggen, og forøge intensiteten der – til Videokonferencer for eksempel.
Man har også mere geometriske metoder, hvor man bruger, at skyggers facon er givet ved andre objekter. Og så leder man efter figurer, der kunne være fremkommet som skygger.

Larry er tilbage! Jeg har savnet ham. Matematikken var noget crowd flux, altså dynamikken i, hvordan flokke bevæger sig. Der vr en “retrograde analysis” af, hvor forbryderne skulle sidde for at sidde optimalt. Ansigtsgenkendelsesalgoritmer blev også brugt.
Crowd dynamics – mylderdynamik
Det har vi haft på bloggen tidligere, men jeg vil opdatere jer lidt. Store flokke af mennesker kan mase hinanden ihjel, som vi har set det flere gange. Keith Still har en lang liste. Keith Still er matematiker og underviser i, hvordan man undgår den slag ulykker ved f.eks. at lave udgange de rigtige steder, at sætte skilte, at sætte barrierer, så folk ikke maser i midten og skaber propper.
Der er flere væsensforskellige måder at betragte den type problemer på: Man kan se på hver enkelt aktør i sammenhæng med de andre og simulere det samlede forløb – hver aktør reagerer på de andres bevægelser. Det er i branchen kompleske systemer, som er en blanding af fysik, datalogi og matematik.
Man kan anlægge en “flow” betragtning – man betragter flokken på samme måde som en væske og ser på hvor mange der er på vej gennem en dør på et givet tidspunkt, og ikke så meget hvem det er. En lidt anden vinkel er den, vi kender fra termodynamik/statistisk mekanik, hvor rigtig mange molekyler betragtes fra en statistisk synsvinkel.
I USA er Mathematics Awareness Month 2011 netop om komplekse systemer. Der er mange links, som I kan surfe rundt i.

Det, Charlie og co. bruger her, er “agent based simulation” – så vidt jeg kan se. Det er der masser af artikler om på nettet. For større områder kombinerer man med GIS (Geografiske Informationssystemer), atlså kort og information om transport etc. For bygninger skal man bruge en plan over bygningen inklusive møbler, hvad vej dørene åbner, belysning, skiltning,… Jo mere info, jo bedre model, men som altid må det afbalanceres med, hvor godt et program og hvor stor en computer, man har til rådighed. Hver enkelt agent har sit eget reaktionsmønster (det kan være det samme for alle, men behøver det ikke.) Og så kører man en simulation af, hvad de gør.
Her er en simulering af en bombeeksplosion på et stadion i Pittsburgh. (Jeg kan ikke få den embedded her, så I må klikke jer hen til den.) Man kan ændre på antallet af mennesker på stadion, sætte hastigheden op, udløse bomber og meget andet. Og man kan så se, hvor mange der bliver såret af bomberne og hvor mange der bliver trampet ihjel.
Det er jo meget underholdende, hvis man glemmer, hvad det drejer sig om, men det kan være blodig alvor at simulere det, før det sker i virkeligheden.

Her er en video, hvor det er knap så dramatisk.