Ordlista

Välj ett av nyckelorden till vänster ...

Grafer och nätverkGrafer i vardagen

Lästid: ~15 min

Vi har sett många olika tillämpningar av grafteori i de föregående kapitlen, även om vissa av dem var lite motstridiga. Det visar sig dock att grafer är grunden för många objekt, begrepp och processer i vardagen.

Internet är till exempel en stor, virtuell graf. Varje toppunkt är en enskild webbsida och varje kant innebär att det finns en hyperlänk mellan två sidor. Observera att länkar bara går en väg, så den här grafen är , och att denna graf är mycket, mycket, stor .

Vissa webbplatser, som Wikipedia eller Facebook, har massor av inkommande länkar, medan många mindre webbplatser kan ha mycket få inkommande länkar. Detta är det underliggande konceptet som Google använder för att sortera sökresultat.

Webbplatser med fler inkommande länkar tenderar att vara av högre kvalitet och bör visas högst upp i sökresultaten. När du till exempel söker efter "London" visas officiella turistinformationssidor före små butiker i London eller bloggar om människor som bor i London. Denna enkla idé från grafteori, Page Rank Algoritmen , gjorde Google betydligt bättre än andra tidiga sökmotorer.

Internet är det största nätverket som någonsin skapats av mänskligheten. Den här bilden visar en mycket liten andel av alla servrar som är anslutna till Internet:

© LyonLabs, LLC and Barrett Lyon, 2014

Medan webbplatser och hyperlänkar bildar en virtuell graf, finns det också det fysiska nätverket av datorer, servrar, routrar, telefonlinjer och kablar.

Varje gång du ringer eller laddar en webbplats måste nätoperatörer hitta ett sätt att ansluta avsändare och mottagare, utan att överskrida kapaciteten för någon enskild kabel eller anslutning. Grafteori och sannolikhet gör det möjligt att garantera en tillförlitlig tjänst, till exempel genom att hitta avledningar när en viss anslutning är upptagen.

Grafer spelar också en viktig roll i transport och navigering. Alla flyg-, tåg- och tunnelbana nätverk bildar diagram som kan användas när du skapar effektiva scheman. En av de mest kända graferna är London Underground-kartan:

Alla vägar och motorvägar bildar också ett stort nätverk, som används av navigeringstjänster som Google Maps när man arbetar med den kortaste vägen mellan två givna punkter.

I framtiden kommer intelligenta transportsystem att minska trafikstockningar och olyckor genom att dirigera bilar mer effektivt genom att använda platsdata som samlas in från smartphones och självkörande bilar. Detta kan spara miljoner timmar förlorade på vägen varje år, minska föroreningar avsevärt och låta räddningstjänsterna resa snabbare.

Den här bilden visar nätverket av kommersiella flygbolag över norra Europa.

Det finns otaliga andra grafer i vetenskap, teknik eller vardagsliv:

Länkarna mellan atomer i molekyler och kristallgaller bildar en graf.

Spridningen av sjukdomar och epidemier kan modelleras med hjälp av ett nätverk.

I biologi bildar de evolutionära träden som visar arternas ursprung en graf.

De olika komponenterna i elektriska kretsar och datorchips bildar ett nätverk.

Den grammatiska strukturen för språk kan modelleras med hjälp av grafer, till exempel för att skapa översättningsalgoritmer.

Grafer har också många tillämpningar inom sannolikhet , spelteori och finansiell matematik .

Sociala nätverk

Låt oss slutligen tänka på ett särskilt bra exempel på diagram som finns i vardagen: sociala medier. Här representerar vertikaler och kanter representerar vänskap, gillar, prenumerationer eller följare.

När vi ritar diagram på sociala medier kan vi se vissa kluster av ömsesidiga vänner, som kan ha gått på samma skola eller bo i samma stad. Vi kan också bestämma människors centralitet , vilket beror på hur välkopplad en toppunkt är, och som kan vara ett mått på en persons popularitet på sociala medier.

2014 hade Facebook 1,4 miljarder aktiva användare och totalt mer än 200 miljarder vänskap. Hälften av alla Facebook-användare har mer än 200 vänner, och eftersom de flesta av våra vänner har ett liknande antal vänner, kan vi lätt ha tiotusentals vänner av vänner .

En spännande fråga skulle nu vara: om du väljer två slumpmässiga Facebook-användare, hur många "vänskapskanter" skulle du behöva följa för att komma från det ena till det andra? Till exempel är avståndet mellan vänner , avståndet mellan vänner till vänner är osv.

2016 genomförde Facebook en studie för att avgöra hur dess användare är anslutna till varandra. De fann att du i genomsnitt är ansluten till någon annan på Facebook via högst 3,57 andra personer. Och detta inkluderar kändisar, politiker eller till och med kungligheter!

Med andra ord, om du väljer någon av miljarder Facebook-användare över hela världen kommer de förmodligen att ha en vän till en vän som känner en vän till en av dina vänner. Vi säger att det finns 3,57 graders separering .

Geographic visualisation of all Facebook friendships in 2010.

1929, när den ungerska författaren Frigyes Karinthy först föreslog idén om "sex graders separation", fanns det inget internet eller sociala medier, men världen hade redan börjat bli mer sammankopplade.

1967 genomförde Stanley Milgram ett första empiriskt experiment, där 296 deltagare som bodde i Nebraska och Kansas uppmanades att leverera ett brev till en viss person som bor i Boston, Massachusetts. De var tvungna att välja en vän att skicka brevet till, som sedan valde en annan vän. Vid varje steg flyttade brevet närmare Boston. Milgram fann att det i genomsnitt bara var 5,2 mellanliggande vänner - 5,2 graders separation.

Idag är var och en av oss en del av otaliga osynliga grafer som ligger till grund för våra sociala interaktioner, resor, Internet och teknik, vetenskap och så mycket mer.

Archie