Glosar

Selectați unul dintre cuvintele cheie din stânga ...

Grafice și rețeleGrafice în viața de zi cu zi

Timp de citit: ~20 min

Am văzut multe aplicații diferite ale teoriei graficelor în capitolele anterioare, deși unele dintre ele au fost puțin conturate. Totuși, se dovedește că graficele sunt la baza multor obiecte, concepte și procese din viața de zi cu zi.

Internetul, de exemplu, este un grafic vast, virtual. Fiecare vertex este o pagină web individuală și fiecare muchie înseamnă că există un hyperlink între două pagini. Rețineți că legăturile merg doar într-un singur sens, astfel încât acest grafic este și că acest grafic este foarte, foarte, mare .

Unele site-uri web, cum ar fi Wikipedia sau Facebook, au o mulțime de link-uri primite, în timp ce multe site-uri web mai mici pot avea foarte puține legături primite. Acesta este conceptul de bază pe care Google îl folosește pentru a sorta rezultatele căutării.

Site-urile web cu mai multe link-uri primite tind să fie de o calitate superioară și ar trebui să fie afișate în partea de sus a rezultatelor căutării. De exemplu, atunci când căutați „Londra”, site-urile de informații turistice oficiale sunt afișate în fața magazinelor mici din Londra sau a blogurilor oamenilor care locuiesc în Londra. Această idee simplă din teoria graficului, algoritmul Page Rank , a făcut ca Google să fie semnificativ mai bun decât alte motoare de căutare timpurii.

Internetul este cea mai mare rețea creată vreodată de omenire. Această imagine arată o proporție foarte mică din toate serverele conectate la Internet:

© LyonLabs, LLC and Barrett Lyon, 2014

În timp ce site-urile web și hyperlink-urile formează un grafic virtual , există și rețeaua fizică de computere, servere, routere, linii de telefon și cabluri.

De fiecare dată când efectuați un apel telefonic sau încărcați un site web, operatorii de rețele trebuie să găsească o modalitate de a conecta expeditorul și receptorul, fără a depăși capacitatea fiecărui cablu sau conexiune individuală. Teoria și probabilitatea graficului fac posibilă garantarea unui serviciu fiabil, de exemplu, găsind devieri atunci când o anumită conexiune este ocupată.

De asemenea, graficele joacă un rol important în transport și navigație. Toate rețelele de zbor, tren și metrou formează grafice, care pot fi utilizate la crearea de programe eficiente. Unul dintre cele mai recunoscute grafice este harta metroului din Londra:

Toate drumurile și autostrăzile formează, de asemenea, o rețea mare, care este utilizată de serviciile de navigație, cum ar fi Google Maps, atunci când se lucrează la cea mai scurtă rută între două puncte.

În viitor, sistemele de transport inteligent vor reduce congestia și accidentele, dirijând mașinile mai eficient, folosind datele despre locația colectate de pe smartphone-uri și autovehiculele auto. Acest lucru ar putea economisi milioane de ore pierdute pe drum în fiecare an, reduce semnificativ poluarea și permite serviciilor de urgență să călătorească mai rapid.

Această imagine arată rețeaua de zboruri aeriene comerciale din toată Europa de nord.

Există nenumărate alte grafice în știință, inginerie sau viața de zi cu zi:

Legăturile dintre atomii din molecule și grilele de cristal formează un grafic.

Răspândirea bolilor și epidemiilor poate fi modelată folosind o rețea.

În Biologie, arborii evolutivi care arată strămoșii speciilor formează un grafic.

Diferitele componente ale circuitelor electrice și ale cipurilor de computer formează o rețea.

Structura gramaticală a limbilor poate fi modelată folosind grafice, de exemplu pentru a crea algoritmi de traducere.

Graficele au, de asemenea, multe aplicații în probabilitate , teoria jocurilor și matematica financiară .

Retele sociale

În cele din urmă, să ne gândim la un exemplu deosebit de bun de grafice care există în viața de zi cu zi: social media. Aici, vârfurile reprezintă și marginile reprezintă prietenii, like-uri, abonamente sau adepți.

Când desenăm graficele social media, s-ar putea să vedem anumite grupuri de prieteni reciproci, care poate au plecat la aceeași școală sau au locuit în același oraș. De asemenea, putem determina centralitatea oamenilor, care depinde de cât de bine este conectat un vertex și care poate fi o măsură a popularității unei persoane pe rețelele de socializare.

În 2014, Facebook a avut 1,4 miliarde de utilizatori activi și un total de peste 200 de miliarde de prieteni. Jumătate dintre utilizatorii Facebook au peste 200 de prieteni și, din moment ce majoritatea prietenilor noștri au un număr similar de prieteni, am putea avea cu ușurință zeci de mii de prieteni .

O întrebare interesantă ar fi acum: dacă alegeți doi utilizatori Facebook aleatori, câte „muchii de prietenie” ar trebui să urmați pentru a trece de la unul la altul? De exemplu, distanța dintre prieteni este , distanța dintre prietenii prietenilor este de și așa mai departe.

În 2016, Facebook a realizat un studiu pentru a determina modul în care utilizatorii săi sunt conectați între ei. Ei au descoperit că, în medie, sunteți conectat la oricine altcineva pe Facebook prin cel mult 3.57 alte persoane. Și asta include celebrități, politicieni sau chiar regalitate!

Cu alte cuvinte, dacă alegeți unul dintre miliardele de utilizatori Facebook din întreaga lume, probabil vor avea un prieten al unui prieten care cunoaște un prieten al unuia dintre prietenii tăi. Spunem că există 3,57 grade de separare .

Geographic visualisation of all Facebook friendships in 2010.

În 1929, când autorul maghiar Frigyes Karinthy a propus prima dată ideea „șase grade de separare”, nu exista internet sau social media, dar lumea începuse deja să fie mai interconectată.

În 1967, Stanley Milgram a realizat un prim experiment empiric, unde 296 de participanți care locuiesc în Nebraska și Kansas au fost rugați să livreze o scrisoare unei anumite persoane care locuiește în Boston, Massachusetts. Toți au fost nevoiți să aleagă un prieten pentru a trimite scrisoarea, care apoi a ales un alt prieten. La fiecare pas, scrisoarea s-a apropiat de Boston. Milgram a descoperit că, în medie, erau doar 5,2 prieteni intermediari - 5,2 grade de separare.

Astăzi, fiecare dintre noi face parte din nenumărate grafice invizibile, care stau la baza interacțiunilor noastre sociale, călătorii, internet și tehnologie, știință și multe altele.