Analiza Retelelor Complexe Utilizând Hiperbolicitatea Gromov

Universitatea "Politehnica" din Timișoara

Facultatea de Automatică și Calculatoare

Departamentul Calculatoare

2, Vasile Pârvan Bv., 300223 – Timișoara, Romania

Tel: +40 256 403261, Fax: +40 256 403214

Web: http://www.cs.upt.ro

Analiza rețelelor complexe utilizând hiperbolicitatea

Gromov

Lucrare de licență

Conducător științific: Student:

Conf.dr.ing. Mihai UDRESCU Rareș ZBÎRCEA

Timișoara,

2016

1. Introducere

1.1. Contextul problemei

Rețelele complexe sunt tot mai atractive pentru cercetătorii de pretutindeni. Aceștia continuă să dezvolte noi metrici care să ajute la analiza acestor rețele complexe. Printre cele mai cunoscute metrici a rețelelor se numără modularitatea, distanța dintre noduri, distribuția gradelor nodurilor și multe altele.

O problemă interesantă a acestor grafuri o reprezintă capacitatea de reprezentare a lor prin arbori. Despre multe astfel de rețele se presupune că înclină spre o astfel de structură, asemănătoare arborilor, dar această presupunere este foarte rar testată. Aici intervine hiperbolicitatea lui Gromov. Această metrică are rădăcinile în geometrie, iar ea indică cât de bine se poate reprezenta o rețea sau un graf sub forma unui arbore, din punct de vedere al structurii metrice.

1.2. Motivația

Cum am menționat mai sus, analiza rețelelor complexe se dezvoltă pe zi ce trece. În literatură, mai exact în lucrările "Metric tree-like structures in real-world networks: an empirical study." și ”Tree-like structure in large social and information networks” este expus faptul că hiperbolicitatea Gromov este utilizată în rețelele complexe din lumea reală, cum ar fi sociale sau informaționale, pentru a determina coeficientul de care am discutat mai sus.

În continuare, voi face o scurtă introducere în Gephi. Acesta este un software pentru vizualizarea și analiza rețelelor complexe. Aș putea spune că este unul din cele mai utilizate programe, care servesc scopului menționat. Totuși, Gephi nu dispune de posibilitatea de a calcula hiperbolicitatea Gromov a unui graf, sau a unei rețele complexe. De aici a izvorât motivația mea. Fiind o metrică utilizată în rețelele din lumea reală, am considerat că ar fi o idee bună să o implementez ca pe un plugin, programului Gephi.

1.3. Descrierea proiectului

Funcționalitatea pluginului implementat de mine este simplă. Acesta calculează hiperbolicitatea Gromov a unei rețele complexe, astfel oferind posibilitatea utilizatorilor programului Gephi să aibă acces la mai multe informații referitoare la rețeaua pe care o vizualizează, sau analizează.

Pe lângă calculul hiperbolicității întregii rețele, pluginul dezvoltat de mine calculează hiperbolicitatea fiecărei comunități dintr-un graf, obținute prin aplicarea modularității pe graful respectiv.

2. Fundamentarea teoretică

2.1. Rețele complexe

Rețelele complexe sunt, în momentul actual, studiate în multe ramuri ale științei. Multe sisteme din natură pot fi descrise prin modele ale rețelelor complexe, care sunt structuri formate din noduri sau vârfuri, conectate prin muchii sau legături. Există foarte multe exemple. Cum se poate observa și în figurile 2.1, respective 2.2, internetul este o rețea de routere sau domenii, iar world wide web-ul este o rețea de site-uri.

Fig. 2.1. Rețeaua Internet

Fig. 2.2. Rețeaua WWW

Creierul este o rețea de neuroni. O organizație este o rețea de oameni. Economia globală este o rețea de economii naționale, care la rândul ei este o rețea de piețe, iar piețele sunt la rândul lor rețele de producători și consumatori care interacționează. Relațiile dintre cuvintele unei limbi pot fi reprezentate cu ajutorul rețelelor, subiectele unei conversații, de asemenea, și chiar și strategiile de rezolvare a problemelor matematice. Mai mult, bolile sunt transmise prin rețele sociale, iar virușii virtuali se răspândesc adesea cu ajutorul internetului. Energia este distribuită prin rețele de transport.

Omniprezența rețelelor complexe în știință și tehnologie au dus, în mod natural, la un set comun și important de probleme de cercetare, privind cum structura rețelelor facilitează și constrânge comportamentele dinamice ale rețelei, care au fost foarte neglijate în studiile disciplinelor tradiționale. De exemplu, cum mijlocesc rețelele sociale, transmisia unei boli? Cum se propagă eșecurile în cascadă, printr-o rețea financiară globală? Care este cea mai eficientă și robustă arhitectură pentru o organizație particulară sau pentru un artefact, supus unui mediu schimbător și nesigur? Ne confruntăm cu probleme de genul acesta zi de zi, probleme care cer răspunsuri și soluții.

2.1.1. Concepte de bază

Chiar dacă multe cantități și măsuri ale rețelelor complexe au fost propuse și investigate în ultimii ani, trei concepte spectaculare joacă un rol important în studiul recent și dezvoltarea teoriei rețelelor complexe: average path length, clustering coefficient și degree distribution.

2.1.1.1. Average path length

Într-o rețea, distanța dij dintre două noduri, notate i și j, este definită ca numărul de muchii care alcătuiesc calea cea mai scurtă dintre cele două noduri. Diametrul D la rețelei, este definit ca fiind distanța maximă dintre toate distanțele, între oricare noduri, din rețea. Average path length „L” a rețelei, este definită ca distanța medie dintre două noduri, iar apoi făcută media pentru toate perechile de noduri. Aici, „L” determină „mărimea” efectivă a unei rețele, cea mai tipică separare a unei perechi de noduri din ea. Într-o rețea de prietenie, de exemplu, „L” este numărul mediu de prieteni care există în lanțul care conectează două persoane din rețea. A fost o descoperire interesantă faptul că lungimea distanței medii a celor mai multe rețele reale complexe este relativ mică, chiar și în cazurile în care au mult mai puține muchii decât o rețea globală tipică cu un număr egal de noduri.

2.1.1.2. Clustering coefficient

Într-o rețea de prietenie, este foarte posibil ca prietenul prietenului tău sa fie și prietenul tău direct; sau, doi dintre prietenii tăi, e foarte posibil să fie și ei prieteni unul cu celălalt. Această proprietate se referă la gruparea rețelei. Mai precis, se poate defini un clustering coefficient „C” ca fracția medie de perechi de vecini a unui nod, care sunt și ei vecini. Să presupunem că un nod i din rețea are ki muchii și ele conectează acest nod de alte ki noduri. Aceste noduri sunt toate vecine cu nodul i. Evident, cel mult ki(ki-1)/2 muchii pot exista între ele, și asta se întămplă când fiecare vecin al lui i e conectat la fiecare alt vecin de al lui i. Clustering coefficient „Ci” al nodului i este atunci definit ca rația între numărul „Ei” de muchii care chiar există între aceste ki noduri și numărul maxim posibil, „Ci”=2„Ei”/(ki(ki-1)). Clustering coefficient „C” al întregii rețele este media tuturor coeficientelor nodurilor. Evident, „C” ≤ 1; și „C”=1 doar dacă rețeaua este cuplată global, ceea ce înseamnă că fiecare nod din rețea este conectat cu fiecare alt nod din rețea. Într-un graf complet aleator, format din N noduri, „C” este aproximativ 1/N, care este foarte mic, comparat cu cele mai multe rețele reale. S-a dovedit că cele mai multe rețele reale „large-scale” au o tendință către grupare, în sensul că clustering coefficient este mult mai mare decât O(1/N), deși tot este semnificativ mai mic ca unu. Acest lucru ne spune la rândul său ca majoritatea rețelelor complexe reale nu sunt complet aleatoare. În concluzie, ele nu ar trebui tratate ca și cum ar fi complet aleatoare și latice cuplate total.

Tabel. 2.1. Metrici ale diferitelor rețele

2.1.1.3. Degree distribution

Cea mai simplă și probabil cea mai importantă caracteristică a unui nod este „degree”-ul. „Degree”-ul ki a unui nod i este de regulă definit ca numărul total de conexiuni. De aici rezultă faptul că importanța nodului este dată de acest „degree”, în sensul că un „degree” mare implică importanță mare. Media tuturor ki a nodurilor i se numește „average degree” al rețelei, și se notează < k >. Împărțirea „degree”-urilor nodurilor într-o rețea este caracterizată de o funcție de distribuție P(k), care este probabilitate ca selectând un nod aleator din rețea, acesta să aibă exact k muchii. O latice normală are o secvență simplă de „degree” deoarece toate nodurile au același număr de muchii; și astfel, o reprezentare grafică a distribuției „degree”-urilor conține un singur vârf ascuțit. Orice valoare aleatoare în rețea va aplatiza forma acestui vârf. În cazul unei rețele complet aleatoare, această secvență de „degree” se supune distribuției Poisson; iar forma distribuției Poisson scade exponențial, departe de valoare de vârf < k >. Datorită acestui declin, probabilitatea de a găsi un nod cu k muchii devine neglijabil de mică pentru k >> < k >. În ultimii ani, multe rezultate empirice au arătat că pentru majoritatea rețelelor reale „large-scale”, distribuția „degree”-urilor deviaza semnificativ de la distribuția Poisson. În particular, pentru câteva rețele, distribuția „degree”-urilor poate fi mai bine descrisă de o lege a puterii de forma P(k) ~ k-Ɣ. Această distribuție a legii a puterii scade mai treptat decât cea exponențială, permițând astfel unor noduri cu un „degree” foarte mare să existe. Pentru că aveste legi a puterii nu depind de nicio scară, o rețea cu o astfel de distribuție poartă numele de rețea „scale-free”.

În continuare, în figura 2.3 avem exemple pentru distribuțiile discutate anterior, dar și diferite rețele.

Fig. 2.3. Distribuții și diferite rețele

2.1.2. Tipuri de rețele

2.1.2.1. Rețele de comunicare

Nu a trecut foarte mult de când pentru a da un telefon în cealaltă parte a lumii era necesară intervenția unui operator uman. Mai mult, o conexiune nu asigura și faptul că cele persoanele se vor și înțelege, deoarece calitatea putea să fie foarte proastă. Multă lume își aduce aminte de întâmplările acestea, de prin jurul anilor 1970, deci nu vremuri foarte îndepărtate. În ziua de astăzi, telefoanele mobile ne permit să fim conectați permanent cu oricine din orice colț al lumii, și acoperirea zonelor continuă să se extindă. Setarea unei convorbiri telefonice de cea mai înaltă calitate cu colegi din întreaga lume este destul de simplu în ziua de azi. Totuși, mai este nevoie să așteptăm până să avem conexiuni video de cea mai bună calitate și ieftine, care să ne lase impresia că suntem în aceeași încăpere cu persoana cu care vorbim.

Lumea pare să devină din ce în ce mai mică, iar oamenii devin tot mai conectați. Evident, telecomuncațiile au avut un rol esențial în realizarea unei lumi conectate, iar convergența între aceste telecomunicații și internet este greu să nu fii conectat în ziua de azi. Faptul că suntem conectați are un efect profund în difuzarea informației.

Web-ul

La fel de important ca și e-mailurile și alte sisteme de transmitere de mesaje pe Internet, este și World Wide Web-ul. Web-ul este un exemplu de spațiu digital de informații: o colecție de informații unite împreună într-o rețea. Web-ul este probabil cel mai mare spațiu de informații de care știm în ziua de azi: la sfârșitul lunii ianuarie, 2005, era estimat că sunt cel puțin 11,5 miliarde de pagini indexabile, care sunt pagini care pot fi găsite și indexate de motoarele importante de căutare, cum ar fi Google. Trei ani mai târziu, alte studii indicau că numărul paginilor se ridică undeva la 30-50 de miliarde. În orice caz, creșterea e impresionantă.

Ceea ce face spațiul informațiilor, Web-ul, interesant pentru noi, este faptul că aceste spații formează o rețea. În cazul Web-ului, fiecare pagină poate conține legături către alte pagini care corespund unui nod în rețea.

Un spațiu de informații legat de Web este cel al enciclopediei online Wikipedia. La sfârșitul anului 2007, au fost numărate peste 7,5 milioane de pagini, scrise în mai mult de 250 de limbi diferite. Versiunea în engleză este de departe cea mai mare, cu peste 2 milioane de articole. Este de asemenea, și cea mai populară din punct de vedere al cererii: 45% din tot traficul de pe Wikipedia este direcționat către versiunea în engleză a enciclopediei. De asemenea, Wikipedia formează o rețea cu paginile sale ca noduri, și referințele către alte pagini, ca legături. Ca și în cazul web-ului, se pare că există puține pagini foarte populare, și multe nepopulare.

2.1.2.2. Rețele sociale

Pe lângă rețelele de comunicare, rețelele care sunt construite în jurul oamenilor sunt de mult timp studiate. Considerăm prima oară rețelele moderne sociale care apar ca și comunități online, datorită Internetului.

Comunități online

Probabil că cel mai mare succes al internetului este abilitatea de a permite oamenilor să facă schimb de informații prin sisteme de mesaje, de tip utilizator la utilizator. Cel mai cunoscut astfel de sistem este e-mailul, care este prezent de când a apărut și Internetul. Un alt exemplu foarte cunoscut sunt știrile online, prin care utilizatorii pot posta mesaje, iar alții pot reacționa provocând dezbateri de toate tipurile și diferite durate. De asemenea, foarte populare sunt și sistemele de mesaje instante, care permit utilizatorilor să interschimbe mesaje între ei.

Este interesant de observat, că aceste sisteme nu sunt chiar foarte sofisticare și că au fost implementate cu tehnologii care există de zeci de ani. În multe moduri, aceste sisteme sunt simple, și rămân simple, lucru ce le permite să ajungă la dimensiuni foarte greu de imaginat. De exemplu, în 2006 s-a estimat că aproape 2 milioane de mesaje e-mail erau trimise în fiecare secundă, de un total de 1 milion de utilizatori. Este adevărat că din aceste mesaje, 70% conțineau viruși, dar chiar și așa este evident că avea loc multa comunicare online. Aceste numere continuă să crescă.

Pe lângă tehnologie, este interesant de văzut ce efecte au aceste facilități ale comunității asupra oamenilor care le folosesc. Suntem martori la creșterea comunităților online, în care oameni care nu s-au cunoscut fizic împărtășesc idei, opnii, sentimente și așa mai departe. Mai mult, pentru comunitățile online avem de-a face cu o small world. În termeni mai simpli, aceasta este caracterizată prin faptul că oricare 2 oameni pot să își transmită mesaje printr-un lanț de doar cinci mesaje.

Există un studiu, care se referă la faptul dacă utilizatorii de e-mail pot trimite un mesaj unei anumite persoane, fără să știe adresa persoanei respective. În acest caz, tot ce poți să faci este să trimiți mesajul unui apropiat de al tău și să speri că el sau ea e mai apropiat de persoana țintă decât tine. În acest experiment, au participat peste 60 de mii de utilizatori, și rezultatele sunt următoarele: 384 din cele aproximativ 24 de mii de lanțuri de mesaje au ajuns la detinație. Din aceste 384 de lanțuri, jumătate au avut lungimea mai mică decât 5-7, depinzând daca destinația era localizată în aceeași țară cu locul de unde a început lanțul.

Ceea ce tocmai am descris este fenomenul de călătorie a mesajelor printr-o rețea de utilizatori de e-mail. Utilizatorii sunt conectați prin faptul că se cunosc între ei, iar rețeaua rezultată are proprietatea de small world, conectând fiecare persoană cu celălalte prin lanțuri relativ mici. Descrierea și caracterizarea acestora și altor rețele formează esența studiului rețelelor.

Rețele sociale tradiționale

Cu mult timp înainte ca Internetul să aibă un rol în viața oamenilor, sociologii și alți cercetători se interesau de structura grupurilor de oameni. În cele mai multe cazuri, grupuri relativ mici de oameni erau luate în considerare, pentru că analiza grupurilor mari adesea nu era fezabilă.

O contribuție importantă la analiza rețelelor sociale a venit de la Jacob Moreno care au introdus sociogramele în jurul anilor 1930. O sociogramă, precum cea din figura 2.4, poate fi văzută ca o reprezentare grafică a unei rețele: oamenii sunt reprezentați prin puncte (noduri), iar relațiile dintre ei prin linii care conectează punctele (muchii).

Fig. 2.4. Sociogramă

Zeci de ani mai târziu, sub influența matematicienilor, sociogramele au fost formalizate în grafuri. Grafurile sunt obiecte matematice, ce au o arhitectură teoretică ce permit cercetătorilor să se focuseze pe structra rețelelor pentru a putea face afirmații despre un grup social.

Analiza rețelelor sociale a fost foarte importantă pentru dezvoltarea teoriei grafurilor, de exemplu, introducerea metricilor pentru identificarea importanței oamenilor sau grupurilor. De exemplu, o persoană care are multe legături către alte persoane, poate fi considerată o persoană importantă. De asemenea, o persoană aflată în centrul rețelei ar părea să fie mult mai influențabilă, decât una care se află la marginea grafului. Ceea ce teoria grafurilor ne oferă sunt instrumentele să descriem formal ceea ce vrem să zicem prin important, sau mai multă influență. Mai mult, utilizând teoria grafurilor putem destul de ușor să dăm o alternativă descrierii importanței și a altora. Având la dispoziție asemenea instrumente, a facilitat precizia afirmațiilor cu privire la poziția sau rolul unei anumite persoane într-o comunitate.

Rețelele sunt pretutindeni

Rețelele de comunicație și cele sociale sunt două tipuri de rețele cunoscute de foarte multă lume. Totuși, există mult mai multe tipuri de rețele. Ceea ce deja ar trebui să fie foarte clar, e faptul că rețelele apar în discpline științifice foarte diferite: economie, studii organizate, științe sociale, biologie, logistică, și așa mai departe. Mai mult, terminologia care este folosită pentru a descrie diferitele tipuri de rețele în fiecare disciplină, este în mare, la fel, ceea ce face să fie relativ ușor pentru membrii a diferite comunități să coopereze în înțelegerea fundațiilor a rețelelor complexe.

Diferite rețele:

Transportul aerian

Noduri: Aeroporturile

Muchii: Zborurile

Descriere: Considerați zborurile programate ale unui anumit operator de transport, între două aeroporturi.

Planurile străzilor

Noduri: Joncțiuni

Muchii: Segment de drum

Descriere: Un segment de drum se întinde între două joncțiuni. Se poate face distincția între segmente cu un singur sens, și segmente cu ambele sensuri.

Transportarea cu trenul

Noduri: Stațiile

Muchii: Conexiune

Descriere: Două stații sunt conectate doar dacă există programată o rută a vreunui tren care nu trece prin stații intermediare.

Rețeaua de cale ferată

Noduri: Joncțiuni

Muchii: Segment de șină

Descriere: Considerați șinele de cale ferată actuale. Unde se îmbină sau se intersectează două segmente de șină, înseamnă ca avem o joncțiune.

Creierul

Noduri: Neuronii

Muchii: Sinapsele

Descriere: Fiecare neuron poate fi considerat că este format din intrări (dendrite) și ieșiri (axon). Sinapsele transportă semnale electrice între neuroni.

Rețele genetice

Noduri: Gene

Muchii: Factor de transcriere

Descriere: În rețelele genetice, modelăm cum genele se influențează unele pe altele, în particular, cum produsul unei gene determină rata la care o altă genă este transcrisă.

Coloniile de furnici

Noduri: Joncțiuni

Muchii: Feromoni

Descriere: O furnică, pentru a înștiința celălalte furnici, unde este sursa de mâncare, produc feromoni care este o substanță chimică ce poate fi ridicată de alte furnici. Feromonii constituie împreună căi.

Rețea de citații

Noduri: Autori

Muchii: Citații

Descriere: În literatura științifică, este ceva normal să citezi din alte lucrări similare și să se menționeze sursele citatelor, astfel ajungându-se la rețele de citații.

Apeluri telefonice

Noduri: Număr

Muchii: Apel

Descriere: Rețelele de apeluri telefonice reflectă perechi de oameni ce schimbă informații, astfel formând o rețea reprezentată de numere de telefon și apeluri efectiv.

Rețea de reputație

Noduri: Oameni

Muchii: Apreciere

Descriere: În rețelele de târguri electronice, cum ar fi e-Bay, cumpărătorii apreciază tranzacțiile. Cum cumpărătorii pot fi la rândul lor vânzători, obținem o rețea care reflectă reputația dintre oamenii din rețea.

Înțelegerea rețelelor complexe necesită un set potrivit de instrumente. În cazul nostru, instrumentele de care avem nevoie vin dintr-o ramură a matematicii, numită teoria grafurilor.

2.2 Grafuri

Până acum, am introdus formal noțiunea de rețea și am dat câteva exemple. Pentru a studia rețelele, avem nevoie de o terminologie care ne permite să fim preciși. Multe afirmații pot fi formulate cu acuratețe, utilizând terminologia din teoria grafurilor. Teoria grafurilor este o ramură a matematicii care a crescut în popularitate în secolele 19 și 20, în principal pentru că permitea descrierea unor fenomene din diferite domenii: infrastructura de comunicații, desenarea și colorarea hărților, programarea taskurilor, și structuri sociale, ca să zic câteva.

Rețelele care au fost introduse până acum, sunt cunoscute din punct de vedere matematic, ca și grafuri. Cea mai simplă definiție ar fi aceea că un graf este o colecție de noduri care pot fi conectate între ele prin muchii. Fiecare muchie a unui graf leagă exact două noduri a acestuia. Nodurile unite printr-o muchie poartă numele de puncte de capăt ale muchiei respective. De asemenea, nodurile unite se numesc adiacente, iar muchia care le unește este incidentă cu ambele noduri.

Din această definiție, ne dăm seama ca nimic nu ne împiedică să avem o muchie care să pornească din același nod în care și ajunge. De asemenea, putem avea mai multe muchii care să unească aceleași două noduri. Un graf care nu are astfel de bucle, sau de muchii multiple, poartă numele de graf simplu.

Totodată, nu împiedică nimeni și nimic ca un graf să aibă zero noduri. Implicit, și numărul de muchii este zero. Graful acesta poartă numele, evident, de graf gol. Un alt caz special este acela în care un graf simplu care are n noduri, și fiecare este adiacent cu fiecare alt nod. Un astfel de nod este cunoscut sub denumirea de graf complet.

Ca în multe situații practice, este adesea foarte convenient să discutăm despre vecini. În termeni din teoria grafurilor, vecinii unui nod sunt acele noduri care sunt adiacente cu nodul respectiv.

Cuvântul „graf” se trage de la faptul că este foarte la îndemână să folosim o reprezentare grafică, cum avem în figura de mai jos. Exemplul nostru conține opt noduri și optsprezece muchii. Fiecare nod e reprezentat cu un punct negru, în timp ce liniile reprezintă muchiile. Când desenăm un graf, este adesea recomandat să adăugăm etichete.

Este clar că există multe moduri de a desena un graf. În primul rând, nu există un motiv anume pentru care să rămânem la puncte și linii, deși este o practică foarte comună chestia asta. În al doilea rând, nu este specificat nicăieri unde trebuie să fie poziționate nodurile sau daca muchiile trebuie desenate în linie dreaptă. Totuși, este important cum desenăm graful nostru când vine vorba de vizualizarea anumitor aspecte.

O proprietate importantă a nodurilor unui graf este numărul de muchii cu care este incident. Aceste număr se numește degree a unui nod. În figura 2.5 este un exemplu de graf, iar în tabelul 2.2 este făcută o analiză a acestuia.

Fig. 2.5. Un graf aleator și muchiile sale

Tabel. 2.2. Datele grafului din figura 2.5

Dacă adunăm toate degree-urile a tuturor nodurilor din graf, obținem 36, care este dublul numărului de muchii din graf. Aceasta constituie o teoremă a grafurilor.

Există un corolar foarte interesant care reiese din proprietatea menționată mai devreme, și anume: numărul de noduri cu un degree impar trebuie să fie par. Acest lucru poate fi demonstrat, relativ foarte ușor. Dacă împărțim nodurile unui graf în două grupuri, unul care conține toate verticele care au degree-ul impar, iar celălalt este cel în care toate nodurile au degree-ul par. Dacă facem suma tuturor degree-urilor obținem un număr par. Evident că suma grupului cu noduri care au degree par, este pară. De aici rezultă că și suma degree-urilor impare, trebuie să dea un număr par, implicit numărul de noduri cu degree impar trebuie să fie par.

Degree-ul unui nod este simplu, dar totuși un concept foarte important. Aceste valori sunt folosite în diferite moduri. De exemplu, dacâ considerăm rețele sociale, putem folosi acest degree pentru a exprima importanța unei persoane într-un grup. De asemenea, când discutăm structura unei rețele de comunicații reale, cum ar fi Internetul, vom vedea că putem afla multe luând în considerare distribuția degree-urilor nodurilor.

Secvența de degree-uri

Listând degree-urile unor noduri dintr-un graf, vom avea o secvență de degree-uri. Acestea sunt de regulă listate descrescător, caz în care ne referim la o secvență de degree-uri ordonată. De exemplu, dacă considerăm cele opt noduri din graful prezentat mai sus, avem următoarea afișare, în tabelul 2.3:

Tabel. 2.3. Afișare degree-uri

de la care, dacă se ordonează descrescător degree-urile, se ajunge la secvența de degree-uri ordonată [7, 5, 5, 4, 4 , 4, 4, 3].

Dacă fiecare nod are are același degree, graful se numește regular. Într-un graf k-regular, fiecare nod al grafului are degree-ul egal cu k. Ca și caz special, grafurile 3-regular se mai numesc grafuri cubice.

Când ne gândim la secvențe de degree-uri, este recomandat să ne focusăm pe grafurile simple, adică acele grafuri care nu au bucle sau muchii multiple. O întrebare foarte interesantă este aceea dacă primim o listă de numere, există oare și un graf simplu a cărei secvență de degree-uri să corespundă cu acea listă? Există câteva cazuri despre care se știe deja că listele nu pot reprezenta secvențe de degree-uri. De exemplu, am arătat că suma degree-urilor nodurilor este tot timpul pară. Prin urmare, o cerință minimă este ca suma elementelor unei liste să fie pară. De asemenea, nu este greu de observat că secvența [ 4, 4, 3, 3] nu poate corespunde unei secvențe a degree-urilor. În acest caz, am avea un graf simplu cu 4 noduri. Primul nod se presupune că are 4 muchii incidente. Cum graful e simplu, fiecare muchie trebuie să fie incidentă cu un nod diferit. Astfel, avem doar 3 noduri de unde să alegem, deci secvența [ 4, 4, 3, 3] nu poate niciodată să corespundă unei secvențe de degree-uri a unui graf simplu.

Desigur, această abordare nu e cea mai indicată pentru a verifica dacă unei liste de numere îi corespunde o secvență de degree-uri. Dar, există o modalitate sistematică prin care putem verifica ceea ce ne interesează pe noi. Dacă ne referim tot la graful prezentat anterior, să presupunem că avem doar lista [ 7, 5, 5, 4, 4, 4, 4, 3]. Ne întrebăm dacă această listă este grafică. Dacă da, ar trebui să fim capabili să construim un graf care are această secvență de degree-uri. Ne vom adresa problemei în felul următor:

Dacă această secvență corespunde unui graf G1, înseamnă ca am putea construi acest graf G1 dintr-un alt graf G2, prin adăugarea unui nod v1 la G2 și să unim nodul v1 cu alte 7 noduri din G2. Astfel G1 ar avea un nod cu cel mai mare degree, 7. De reținut, ca să putem să avem graful G1, trebuie să putem să construim G2.

Ar trebui să fie clar că dacă nu schimbăm ordinea degree-urilor nodurilor, că secvența grafului G2 este [ 4, 4, 3, 3, 3, 3, 2]. În primul rând, conține un element mai puțin ca secvența de degree-uri a grafului G1. În al doilea rând, primului element din această secvență îi corespunde al doilea element din secvența grafului G1: este degree-ul aceluiași nod, dar pentru graful G2 este mai mic cu 1, deoarece acest nod nu este încă unit cu nodul v1. Tot așa, al doilea element ai secvenței grafului G2 îi corespunde al treilea element al secvenței de deegre-uri a grafului G1, și tot așa mai departe.

Dacă secvența [4, 4, 3, 3, 3, 3, 2] este grafică, putem aplica același principiu: G2 ar trebui să poată fi construit pe baza unui graf G3, prin adăugarea nodului v2 și unind v2 cu 4 noduri din G3. Urmând o procedură analog cu cea de dinainte, v2 este unit cu nodurile din G3 astfel că aceste noduri vor avea apoi degree-urile 4, 3, 3 și 3. Asta înseamnă că în G3, ele vor avea degree-urile 3, 2, 2 și 2, obținând următoarea listă: [3, 2, 2, 2, 3, 2].

În exemplul anterior, al cincilea element este la fel cu al șaselea din G2. Primele patru elemente reprezintă nodurile care vor fi unite cu noul nod v2. Celălalte elemente reprezintă nodurile care rămân neatinse, deci vor avea același număr de muchii de incidență ca și în graful G2.

Dacă continuăm pe linia asta, [3, 3, 2, 2, 2, 2] este acum secvența (ordonată) a grafului G3. Atunci înseamnă că am putea construi graful G3, dintr-un graf G4 la care să adăugăm nodul v3. Acest nod ar trebui unit cu nodurile care au degree-urile 2, 1 și 1 din graful G4, reieșind secvența [2, 1, 1, 2, 2]. Din nou, remarcați că această listă conține un element mai puțin decât secvența de degree-uri a grafului G3, dar elementele de la al patrulea până la sfârșit reprezintă noduri care au aceeași valoare a degree-ului și în graful G3, cât și în graful G4.

Acum, dacă lista ordonată [2, 2, 2, 1, 1] este grafică, atunci la fel ar trebui să fie și lista [1, 1, 1, 1], care corespunde grafului G5.

De asemenea, dacă [1, 1, 1, 1] este grafică, la fel ar trebui să fie și lista degree-urilo nodurilor [0, 1, 1] care corespunde unui graf G6.

În final, dacă [1, 1, 0] este grafică, la fel ar trebui să fie și [0, 0], ceea ce este adevărat, deoarece reprezintă un graf G7 care conține doar două noduri, și nu are nicio muchie în componența sa.

Putem trage concluzia că secvența [7, 5, 5, 4, 4, 4, 4, 3] corespunde unui graf simplu. În figura următoare, 2.6, ilustrăm construcția grafului G1, și se prezintă fiecare graf, de la G1 până la G7 și modul în care se adaugă nodurile și muchiile respective.

Fig. 2.6. Construcția grafului G1

Intuitiv, ar trebui să fie clar că tocmai am introdus o metodă sistematică de verificare dacă o listă dată de numere corespunde unei secvențe de degree-uri a unui graf.

De reținut este că două grafuri cu aceeași secnveță de degree-uri nu trebuie sa fie la fel. Cu alte cuvinte, când se dă o secvență de degree-uri, este posibil să se construiască câteva grafuri diferite care să corespundă secvenței date. Acest lucru putem să îl observăm ușor în figura care urmează, 2.7, în care secvențele de degree-uri sunt [3, 3, 2, 2, 2] și [7, 5, 5, 4, 4, 4, 4, 3]:

Fig. 2.7. Grafuri diferite cu aceeași secvență

2.2.1. Subgrafuri

Un alt concept important al grafurilor sunt subgrafurile. Un graf H este un subgraf al lui G dacă H este constituit dintr-un subset de muchii și noduri ale lui G, astfel încât capetele muchiilor din H, există și ele în H.

În figura 2.8, avem un exemplu de graf cubic cu 8 noduri și 3 subgrafuri de ale sale:

Fig. 2.8. Graf cubic și subgrafurile sale

Când analizăm proprietățile unui graf, este adesea foarte convenient să considerăm subgrafuri formate cu un set specific de noturi. Acestea se numesc subgrafuri induse, și se construiesc prin luarea unui subset de noduri, V*, și adăugarea fiecărei muchii din graful original, care conectează două noduri din V*.

Un subgraf indus special este unul care se construiește prin eliminarea unui nod specific dintr-un graf G. Acest lucru se poate nota G-v, unde G este graful din care obținem subgraful, iar v este nodul care urmează să fie eliminat. De asemenea, notația G-e este similară, doar că în cazul de față, e corespunde unei muchii.

2.2.2. Reprezentarea grafurilor

Ar trebui să fie destul de clar deja că grafurile se pot desena în diferite moduri, dar de asemenea sunt descrise de obicei în termeni de noduri și muchii.

Structuri de date

Sunt mai multe moduri în care se pot reprezenta grafurile. Probabil că cea mai atrăgătoare este folosirea matricelor de adiacență. Să considerăm un graf G cu n noduri și m muchii. Matricea de adiacență a grafului G nu este altceva decât un tabel cu n rânduri și coloane, în care elementul A[i,j] reprezintă numărul de muchii care unește nodul vi cu nodul vj.

Deja putem observa câteva proprietăți:

O matrice de adiacență este simetrică față de diagonala principală, adică A[i,j] = A[j,i], pentru orice graf neordonat.

Un graf G este simplu dacă și numai dacă pentru oricare ar fi i și j, A[i,j] ≤ 1 și A[i,i] = 0. Cu alte cuvinte, poate fi maxim o muchie care să unească două noduri și nicio muchie să unească un nod de el însuși.

Suma valorilor de pe rândul i este egală cu degree-ul nodului vi.

În figura 2.9, avem un exemplu de graf, împreună cu matricea sa de adiacență:

Fig. 2.9. Graf și matricea sa de adiacență

Această metodă de reprezentare a grafurilor este cea pe care am utilizat-o în dezvoltarea pluginului. Am ales această metodă pentru că era cea mai convenabilă din punct de vedere al înțelegerii algoritmului, și era metoda care îmi oferea cele mai multe avantaje în dezvoltarea codului, adică diminua dificultatea manipulării grafurilor.

Ca o alternativă, putem folosi o matrice de incidență a unui graf pentru a-l reprezenta. O matrice de incidență M a unui graf G este formată din n rânduri și m coloane, astfel încât M[i,j] numără de câte ori muchia ej este incidentă cu nodul vi. De observat că M[i,j] ia valorile 0, 1 sau 2: o muchie poate să nu fie incidentă cu nodul vi, poate să aibă nodul vi ca unul din capete, sau poate să fie o buclă care unește nodul vi cu el însuși. În figura 2.10, este prezentată matricea de incidență pentru același graf:

Fig. 2.10. Graf și matricea sa de incidență

De asemenea, avem și aici cîteva proprietăți:

Un graf G nu conține bucle dacă și numai dacă pentru oricare ar fi i și j, M[i,j]≤1.

Suma tuturor valorilor de pe rândul i este egală cu valoarea degree-ului nodului vi.

Pentru că fiecare nod are exact două, nu necesar distincte, puncte de capăt, știm că suma tuturor elementelor de pe oricare coloană a matricei este 2.

Una din problemele utilizării matricelor de adiacență sau de incidență este aceea că fără optimizări, numărul total de elemente pentru reprezentarea unui graf este n x n sau n x m. Acest lucru nu este foarte eficient când avem de lucru cu grafuri foarte mari, mai ales când numărul de muchii este foarte mic. Ca să vedem de ce acest lucru e adevărat, vom considera reprezentarea unei matrici de adiacență într-un computer. Să presupunem că folosim un singur byte pentru a număra numărul de muchii ce unesc o pereche de noduri. Fără alte optimizări, un graf cu 100,000 de noduri ar necesita un total de 100,000 x 100,000 de bytes de memorie, care reprezintă aproape 10 Gbytes.

Folosind o matrice de incidență și presupunând că avem un total de 250,000 de muchii, o reprezentare neoptimizată ar necesita aproape 25 de Gbytes de memorie. Ambele variante de reprezentare, chiar și cu optimizări de memorie, tind să fie foarte ineficiente.

O metodă de reprezentare utilizată mai des și este mai eficientă, este o listă de muchii. În acest caz, listăm muchiile grafului G, specificând nodurile cu care sunt incidente muchiile. Această reprezentare crește liniar odată cu numărul de muchii. Reprezentarea printr-o listă de muchii a grafului anterior: ((v1,v1),(v1,v2),(v1,v3),(v2,v3),(v2,v3),(v3,v4),(v4,v4)).

În particular, pentru m muchii, am avea nevoie să stocăm doar 2*m date. Să presupunem că un nod poate fi reprezentat pe 4 bytes, asta înseamnă că pentru graful nostru cu 100,000 de noduri și 250,000 de muchii, am avea nevoie doar de aproape 2 Mbytes de memorie. În practică, acest număr va fi mai mare deoarece avem nevoie de structuri de date adiționale pentru a naviga ușor prin lista de muchii. Totuși, spațiul de stocare de care este nevoie pentru reprezentarea unui graf cu ajutorul listei de muchii rămâne semnificativ mai mic decât spațiul necesar pentru reprezentarea acestuia cu matrice de adiacență sau matrice de incidență.

E clar că parcurgând lista de muchii, vom găsi și nodurile asociate grafului, ținând cont că fiecare nod e incident cu cel puțin una din muchii. În practică, o listă de muchii e adesea acompaniată de o listă de noduri.

2.2.3. Conectivitatea

În toate grafurile de care am discutat până acum, fiecare nod v putea fi ajuns din oricare alt nod w, în sensul că putem avea un lanț de noduri adiacente de la v la w.

Utilizând noțiunea de cale, definim un graf ca fiind conectat atunci când există o cale între orice pereche de noduri distincte.

În mod evident, toate grafurile pe care le-am considerat până acum sunt conectate. Totuși, nu există niciun motiv pentru care să presupunem că un graf este tot timpul conectat. În definiția grafului, nu este nimic specificat de faptul că toate nodurile trebuie să fie conectate. Asta înseamnă că un graf poate fi constituit dintr-o colecție de componente, unde fiecare componentă este un subgraf conectat.

Noțiunea de conectivitate este importantă, mai ales când considerăm robustețea rețelelor. Robustețea în acest caz, se referă la cât de bine stă rețeaua conectată atunci când eliminăm noduri sau muchii. De exemplu, Internetul poate fi văzut ca un graf uriaș în care routerele formează nodurile, iar comunicațiile dintre routere formează legăturile. Într-un sens formal, Internetul este conectat. Totuși, dacă ar fi posibilă partiționarea rețelei în multiple componente prin eliminarea unui singur nod sau a unei singure muchii, am putea spune că Internetul nu e robust. Mai mult, este extrem de important pentru rețele precum Internetul, să poată să reziste la atacuri serioase și eșecuri, cauzate de routere și legături eșuate, astfel încât conectivitatea să nu fie afectată.

Există mai multe rețele pentru care robustețea joacă un rol important.

2.3 Hiperbolicitatea Gromov

Fie G un graf conectat, și fie d(a,b) distanța cea mai scurtă între nodurile a și b care aparțin lui G. Hiperbolicitatea unui graf a fost definită de Gromov astfel:

Un graf G este δ-hiperbolic dacă pentru oricare patru noduri a, b, c, d din G, cele mai mari două sume dintre următoarele trei S1 = d(a, b) + d(c, d), S2 = d(a, c) + d(b, d), și S3 = d(a, d) + d(b, c) diferă prin cel mult 2δ.

Figura următoare, 2.11, ilustrează această definiție, cunoscută și sub numele de „condiția celor 4 puncte”:

Fig. 2.11. 4-point condition

Hiperbolicitatea unui graf este maximul hiperbolicităților componentelor biconectate ale grafului. Pentru a demonstra asta, să presupunem că x este un nod care eliminat din graful G, descompune acesta în două componente. Să zicem că cele două componente ale grafului vor fi B1 și B2. Fie a,b,c din B1, iar d aparține lui B2. În acest caz, avem:

S1 = d(a,b) + d(c,d) = d(a,b) + d(c,x) + d(x,d)

S2 = d(a,c) + d(b,d) = d(a,c) + d(b,x) + d(x,d)

S3 = d(a,d) + d(b,c) = d(a,x) + d(x,d) + d(b,c)

Valoarea calculată pentru gruparea (a,b,c,d) este aceeași cu valoarea calculată pentru gruparea (a,b,c,x). Similar, când a și b aparțin lui B1, iar c și d aparțin lui B2, valoarea calculată va fi 0. Acest lucru se observă din figura 2.12.

Fig. 2.12. Valori ale hiperbolicității

Pentru anumite familii de grafuri este posibil să dăm valoarea exactă a hiperbolicității lor. În particular, avem:

grafurile block sunt 0-hiperbolice, la fel ca arborii și clique-urile;

ciclurile de ordinul n = 4p + ε, cu p ≥ 1 și ε aparține {0, 1, 2, 3}, sunt (p-½)-hiperbolice când ε=1, sau p-hiperbolice în caz contrar;

grilele n x m, cu condiția că 2 ≤ n ≤ m, sunt (n-1)-hiperbolice;

grilele d-dimensionale de latură s sunt (s-1)[d/2]-hiperbolice.

3. Specificațiile proiectului

3.1. Gephi

Gephi este un software pentru vizualizarea și analiza rețelelor, și a grafurilor dinamice sau ierarhice.

Este un program pe care utilizatorii îl folosesc pentru a înțelege și a explora grafuri. Utilizatorul are posibilitatea aici, să interacționeze cu reprezentarea, să manipuleze structura, formele sau culorile grafului pentru a scoate în evidență anumite proprietăți ale acestuia. Scopul acestui program a fost să dea o mână de ajutor analiștilor, în a afirma câteva ipoteze, descoperi modele sau pentru a izola diferite specificuri ale unei structuri. În figura 3.1 este un mic preview la gephi.

Fig. 3.1. Gephi

3.1.1. Statistici disponibile

Gephi dispune de o multitudine de statistici. Printre acestea se numără: average clustering coefficient, average path length, betweenness centrality, closeness centrality, connected components, degree, degree power law, diameter, eigenvector centrality, graph density, hits, modularity sau pagerank.

În continuare, voi prezenta pe scurt aceste statistici.

3.1.1.1. Average clustering coefficient

Acest coeficient, dacă este aplicat asupra unui singur nod, măsoară cât de completă este vecinătatea acelui nod. Aplicat unei întregi rețele, este media tuturor coeficienților nodurilor din rețea.

Vecinătatea unui nod, este setul de noduri care sunt conectate cu acel nod. Dacă toate nodurile din vecinătatea unui nod sunt conectate cu toate celălalte noduri din aceeași vecinătate, atunci vecinătatea lui u este completă și coeficientul va fi 1. Dacă niciun nod din vecinătatea unui nod nu este conectat cu alt nod din vecinătate, atunci coeficientul va avea valoarea 0.

3.1.1.2. Average path length

Reprezintă media distanțelor dintre noduri a unui graf.

Nodurile conectate au distanța 1. Cea mai lungă distanță dintre două noduri într-o rețea, poartă numele de diametru.

3.1.1.3. Betweenness centrality

Această statistică măsoară cât de des apare un nod în căile cele mai scurte între noduri, din rețea.

3.1.1.4. Closeness centrality

Reprezintă distanța medie de la un nod dat către toate celălalte noduri din rețeaua complexă.

3.1.1.5. Connected components

Determină numărul de componente conectate din rețea.

Pentru un graf direcționat, detectează componentele conectate puternic, dar și pe cele conectate slab. La grafurile nedirecționate, această statistică arată doar componentele conectate mai slab.

3.1.1.6. Degree

Această valoare se determină pentru fiecare nod în parte, și reprezintă numărul de muchii adiacente nodului.

3.1.1.7. Degree Power Law

Măsoară cât de tare indică distribuția degree-urilor unei rețea, spre o funcție de power-law.

3.1.1.8. Diameter

Cum am precizat și înainte, reprezintă distanța maximă într-un graf sau o rețea, între toate perechile de noduri.

3.1.1.9. Eigenvector Centrality

Reprezintă o măsurare a importanței unui nod într-o rețea, bazată pe conexiunile acelui nod.

3.1.1.10. Graph Density

Măsoară cât de aproape este rețeaua, de a fi completă. Un graf complet este acela care are toate muchiile posibile și densitatea egală cu 1.

3.1.1.11. HITS

HITS (Hyperlink-Induced Topic Search) este un algoritm de analiză a linkurilor care evaluează paginile Web.

3.1.1.12. Modularity

Această statistică este extrem de utilă și măsoară cât de bine se descompune o rețea în comunități modulare.

Cu cât este mai mare această valoare, cu atât este mai sofisticată structura internă a rețelei. Această structură, denumită și structură de comunități, este compartimentată în sub-rețele. Aceste sub-rețele, sau comunități, s-a dovedit că au o importanță semnificativă în viața reală.

3.1.1.13. PageRank

Este un algoritm iterativ care măsoară importanța fiecărui nod dintr-o rețea. Această metrică asignează fiecărui nod o probabilitate, adică acea probabilitate ca nodul să fie la pagina respectivă după multe clickuri.

3.1.2. Arhitectura Gephi

Gephi a fost construit pe platforma Netbeans, și se bazează pe o arhitectură modulară, cât mai decuplată posibil.

Fiecare feature este împărțit în module. Modulele depind unul de altul, la fel ca și pachetele în Java. Dezvoltatorii de pluginuri creează astfel module noi care conțin codul lor propriu, și adaugă dependențele de celălalte module Gephi. În figura 3.2 este un exemplificat acest lucru.

Fig. 3.2. Arhitectura Gephi

3.2. NetBeans

NetBeans este o platformă de dezvoltare software scrisă în Java. Această platformă permite aplicațiilor să fie dezvoltate dintr-un set de componente software modulare, numite module.

Aceasta este platforma pe care am utilizat-o în dezvoltarea pluginului meu. În continuare voi face o scurtă prezentare a mediului de dezvoltare NetBeans IDE.

3.2.1. NetBeans IDE

NetBeans IDE este un mediu de dezvoltare open-source. Acesta suportă dezvoltarea tuturor tipurilor de aplicații Java. Printre numeroasele feature-uri, se numără refactorizarea de cod, suport Maven, sau versionarea.

Toate funcțiile acestui IDE sunt oferite prin module. Fiecare modul are o funcție foarte bine definită, cum ar fi suportul pentru limbajul Java, editarea sau suport pentru versionarea CVS. NetBeans conține toate modulele de care este nevoie pentru a dezvoltarea în Java, într-un singur download, pemițând astfel utilizatorului să se apuce de lucru cât de repede. Modulele mai au un rol, ele permit extinderea NetBeans. Noi feature-uri, cum ar fi suportul pentru alte limbaje de programare, pot fi adăugate prin instalarea unor module adiționale.

3.3 Limbajul de programare JAVA

Java este un limbaj de programare care este concurent, bazat pe clase, orientat pe obiecte și este intenționat să aibă cât mai puține dependențe posibile. O caracteristică extrem de importantă a acestui limbaj de programare este portabilitatea, adică codul Java compilat poate rula pe toate platformele care suportă Java fără a necesita încă o compilare.

3.3.1. Principii de programare orientată pe obiecte

3.3.1.1. Cele 4 principii care stau la baza programării oreientate pe obiecte

Moștenirea

Moștenirea poate fi definită ca procesul prin care o clasă achiziționează proprietățile unei alte clase, adică metodele și variabilele acesteia. Cu ajutorul moștenirii, informația poate fi manipulată în mod ierarhic.

Clasa care moștenește proprietățile unei alte clase poartă numele de subclasă, iar clasa ale cărei proprietăți sunt moștenite, poartă numele de superclasă.

Încapsularea

Încapsularea este un mecanism de înfășurare a datelor și a codului care acționează asupra acestor date, ca un întreg. În încapsulare, variabilele unei clase vor fi ascunse de celălalte clase, și sunt accesibile doar prin metode ale clasei curente, de aici venind și termenul de „data hiding”

Polimorfismul

Polimorfismul reprezintă abilitatea unui obiect de a lua mai multe forme. Cea mai comună utilizare a polimorfismului este atunci când o referință a clasei părinte este folosită pentru a referi către un obiect al clasei copil.

Orice obiect care are mai multe relații de tipul IS-A este considerat polimorfic.

Abstractizarea

Abstractizarea se referă la idei în special, în defavoarea concretului. Prin abstractizare se ascund detaliile implementării, de utilizator, oferindu-i doar funcționalitatea. Cu alte cuvinte, utilizatorul va avea informații despre ce face obiectul, dar nu și despre cum face acele lucruri.

3.3.1.2. Principiile SOLID

Single-responsibility Principle

Acest principiu enunță următoarele: O clasă ar trebui să aibă un singur motiv ca să se schimbe, însemnând că o clasă ar trebui să facă un singur lucru.

Open-Closed Principle

Obiectele sau entitățile ar trebui să fie deschise pentru adăugiri, dar închise pentru modificări.

Liskov substitution principle

Acest principiu ne spune că într-un program, orice subclasă trebuie să poată să înlocuiască superclasa, fără a altera corectitudinea programului.

Interface segregation principle

Un client nu ar trebui să fie niciodată forțat să implementeze o interfață pe care nu o folosește, sau să fie forțați să depindă de metode de care n-au nevoie.

Dependency inversion principle

Entitățile trebuie să depindă de abstracțiuni și nu de concret. Acest principiu mai enunță și faptul că modulele de nivel înalt nu trebuie să depindă de modulele de nivel mai jos, ci amândouă trebuie sa depindă de abstracțiuni.

3.4. Funcționalitate

Funcționalitatea este destul de simplu de explicat.

Aplicația Gephi se rulează din mediul de dezvoltare NetBeans, precum în figura 3.4.

Fig. 3.4. Rulare Gephi

În aplicație, utilizatorul are mai multe opțiuni:

generarea unui graf aleator, specificând numărul de noduri;

importarea unui graf;

selectarea unui graf standard oferit de aplicația Gephi la deschiderea acesteia.

După asta, graful va apărea în fereastra din mijloc a programului, în diferite culori, sau doar negru, aceste efecte depinzând de setările făcute, precum în figura 3.5.

Fig. 3.5. Graf în Gephi

Mai departe, pentru a apela pluginul creat de mine, se va căuta ”Gromov Hyperbolicity” în fereastra din dreapta, în tabul ”Statistics” la secțiunea ”Network Overviev”. Mai specific, este chiar ultima metrică din opțiunile de la categoria ”Network Overview”, exemplificat în figura 3.6.

Fig. 3.6. Statistics

Odată găsită această metrică, se poate observa că are un buton ”Run” care îi corespunde, și care face exact ceea ce numele îi spune, rulează metrica. Apăsând pe buton, va apărea pe ecran un mic dialog box, care reprezintă câteva setări pentru rularea metricii. Acest dialog box, din figura 3.7, conține și o scurtă descriere a hiperbolicității, după care utilizatorul are posibilitatea de a selecta cum dorește să fie interpretată rețeaua, orientată sau neorientată. În caz că graful pe care se rulează este neorientat, atunci opțiunea utilizatorului de a trata graful ca orientat este dezactivată, și automat este selectată opțiunea de a trata graful ca unul neorientat.

Fig. 3.7. Dialog Box

Odată realizată treaba asta, pentru a continua și implicit a rula metrica pe rețeaua selectată, se apasă butonul ”OK”. După aceea, programul rulează metrica, adică hiperbolicitatea Gromov, dar și modularitatea rețelei, pentru a putea rula mai apoi hiperbolicitatea Gromov pe fiecare din comunitățile rețelei. După ce programul a terminat de rulat metrica, va genera un raport, cel din figura 3.8, care va conține următoarele informații:

Numele raportului;

Parametrii, în cazul nostru fiind doar afișat modul de interpretare a rețelei, orientat sau neorientatș

Rezultate, la care avem:

Hiperbolicitatea Gromov a întregii rețele;

Numărul de comunități;

Hiperbolicitatea fiecărei comunități a rețelei.

Fig. 3.8. Raport

După ce s-a rulat și s-a închis raportul rezultat, se poate observa că în dreptul butonului de ”Run” apare hiperbolicitatea întregii rețele, iar pe butonul din dreapta celui de rulare, se poate deschide raportul rulării metricei, cum se observă în figura 3.9.

Fig. 3.9. Rezultatul rulării

Toate aceste funcționalități sunt reprezentate prin următoarea figură, 3.10, care este o diagramă de use-caseuri:

Fig. 3.10. Use-cases

Clasele importante ale pluginului meu sunt Gromov și GromovUI, evident aceasta din urmă este pentru interfața cu utilizatorul. Ambele clase implementează câte o interfață, și anume: Gromov implementează interfața Statistics, iar Gromov UI implementează interfața StatisticsUI. Acesta este modul standard prin care se creează pluginuri pentru secțiunea de ”Statistics” din Gephi. Implementând interfațele, este evident că am implementat și metodele conținute de aceste interfețe, și anume: în interfața Statistics, există metodele execute și getReport, iar în StatisticsUI există metodele getSettingsPanel, setup, unsetup, getStatisticsClass, getValue, getDisplayName, getShortDescription, getCategory și getPosition. În figura 3.11, avem reprezentarea UML a implementărilor despre care am discutat:

Fig. 3.11. Diagramă UML

4. Proiectare și implementare

4.1. Proiectarea

Cerințele proiectului sunt simple: creearea unui plugin care să calculeze hiperbolicitatea Gromov pentru un graf sau o rețea dată.

Datele de intrare sunt reprezentate de graf/rețea iar datele de ieșire sunt reprezentate de hiperbolicitatea Gromov a grafului/rețelei.

Inițial, planul a fost simplu, vom avea o clasă pentru calcularea hiperbolicității Gromov, iar alta pentru interfața cu utilizatorul. Apoi, am venit cu ideea de a calcula hiperbolicitatea pentru fiecare comunitate din rețea. Aceste comunități urma să le obțin apelând metrica de modularitate.

Acesta a fost și planul final, adică să calculez hiperbolicitatea întregului graf, apoi să rulez metrica de modularitate din cod, iar pe urmă să calculez hiperbolicitatea fiecărei comunități rezultate din rularea modularității.

4.2. Implementarea

Implementarea acestui plugin s-a bazat extrem de mult pe algoritmul lui Gromov pentru determinarea hiperbolicității.

Astfel, pentru a rezolva problema grupărilor de patru noduri, fără a folosi patru for-uri imbricate, am apelat la metoda combinărilor. Această metodă funcționează în felul următor: pentru calcularea hiperbolicității întregului graf, fac combinări de numărul total al grafurilor luate câte patru, iar eu voi primi un array de array-uri care conțin toate posibilele combinări. Pentru calcularea hiperbolicității unei comunități, fac combinări de numărul de noduri din comunitate luate tot câte 4, logic. De exemplu: dacă am 5 noduri în tot graful, atunci voi calcula combinări de 5 luate câte 4:

(1, 2, 3, 4),

(1, 2, 3, 5),

(1, 2, 4, 5),

(1, 3, 4, 5),

(2, 3, 4, 5).

Acestea sunt toate combinările posibile, iar în program eu le voi avea sub forma:

((1, 2, 3, 4), (1, 2, 3, 5), (1, 2, 4, 5), (1, 3, 4, 5), (2, 3, 4, 5)).

În figura 4.1, putem vedea codul care generează aceste soluții:

Fig. 4.1. Cod sursă

Apoi, eu am apelat la o matrice de adiacență un pic mai complexă. Adică, în loc să am 1 în caz că există legătură directă între cele 2 noduri și 0 în caz contrar, eu voi avea pe poziția [i][j] în matrice numărul de muchii minim care leagă cele 2 noduri, i și j. Cu alte cuvinte, am putea spune că matricea este una de ”shortest paths”, în loc de matrice de adiacență.

În continuare, pentru a obține hiperbolicitatea întregii rețele, am parcurs toate soluțiile de combinări și le-am luat rând pe rând, după care am calculat sumele necesare algoritmului lui Gromov, după cum se observă în figura 4.2.

Fig. 4.2. Cod sursă

În metoda calculateGromovs care este apelată în figura 4.2, selctez din cele 3 sume, cele 2 mai mari, iar în vectorul de rezultate pun diferența dintre cele 2 sume, pe poziția dată de ultimul parametru. Codul sursă este în figura 4.3.

Fig. 4.3. Cod sursă

După aceea, apelez metoda gromovMax, figura 4.4, care îmi returnează valoarea maximă din vectorul de valori rezultate la pasul precedenet, împărțită la 2, conform algoritmului lui Gromov.

Fig. 4.4. Cod sursă

Pentru a calcula hiperbolicitățile tuturor comunităților din rețea, am avut nevoie întâi să rulez metrica de modularitate, figura 4.5, care îmi partiționa rețeaua în aceste comunități. Acest lucru l-am făcut utilizând clasa Modularity deja existentă și prin apelul metodei execute.

Fig. 4.5. Cod sursă

Iterând apoi prin toate nodurile din graf, într-un vector de întregi am asociat fiecărui nod, comunitatea din care face parte, după cum se vede în figura 4.6.

Fig. 4.6. Cod sursă

După aceea, având un întreg cu valoarea 0 inițial, am parcurs toate modularitățile nodurilor într-un while, figura 4.7, iar dacă acestea se aflau în comunitatea pe care o verificam, rețineam indicele lor într-un alt vector. Astfel am creat un vector care conține doar indicele nodurilor care se află într-o anumită comunitate.

Fig. 4.7. Cod sursă

După cum se observă, dacă nu se găsește niciun nod care să fie în comunitatea ”com” atunci se pune ”existClass” pe ”false” iar algoritmul nu va mai intra în acest while.

Dacă numărul de noduri găsite într-o comunitate este mai mic ca 4, atunci am decis să pun valoarea ”-1” corespunzătoare hiperbolicității acelei comunități. Dacă nu, atunci parcurgeam similar soluțiile combinări, ca la calculul întregii rețele, făcând aceleași instrucțiuni cu o singură mențiune, calculul sumelor. Codul sursă corespunzător se află în figura 4.8. De data aceasta, indicii matricei de cele mai scurte căi dintre noduri, nu erau rezultatele combinărilor, ci valorile aflate în vectorul menționat un pic mai sus.

Fig. 4.8. Cod sursă

În metoda getReport am creat un string, figura 4.9, care conține cod html, și după ce am format acest string, l-am returnat.

Fig. 4.9. Cod sursă

Aceasta este metoda de implementare pe care am utilizat-o, și cu care am reușit să îmi îndeplinesc obiectivul.

5. Rezultate

Pentru testarea algoritmului am utilizat mai multe rețele/grafuri.

Primul test l-am făcut pe un graf, așa numita ”căsuță”, figura 5.1, a cărei hiperbolicitate este cunoscută ca fiind 1, iar rezultatele sunt cele așteptate.

Fig. 5.1. Graful ”căsuță”

În continuare trebuie menționat că dacă hiperbolicitatea Gromov este 0, înseamnă că graful poate fi structurat ca un arbore. Astfel, am testat ce se întâmplă dacă dau ca graf de intrare, un arbore, figura 5.2. Puteți să observați că rezultatele sunt corespunzătoare.

Fig. 5.2. Arbore

Pentru următorul caz am generat un graf aleator cu 75 de noduri, în figura 5.3. Probabilitatea ca el să fie ”tree-like” este foarte mică, și asta reiese și din rezultatul obținut.

Fig. 5.3. Graf aleator

În fine, pentru ultimul test, am utilizat un graf oferit de gephi, și anume ”Les Miserables”, figura 5.4, construit pe baza personajelor din celebra carte. Fiind o rețea mai modulară, valoarea hiperbolicității nu este foarte mare, ba chiar unele comunități au proprietatea de ”tree-like”.

Fig. 5.4. Graful ”Les Miserables”

6. Concluzii

Obiectivul acestei lucrări a fost implementarea unui plugin care să ajute la analiza rețelelor complexe. Hiperbolicitatea Gromov este o metrică întâlnită în lumea reală, dar care nu era implementată în foarte cunoscutul Gephi, program de vizualizat și analizat rețele complexe. Am decis atunci că vreau să fac asta, vreau ca produsul pe care eu îl livrez să fie folosit de oameni de pretutindeni, să ajute la analiza rețelelor, și pentru a nu se mai merge pe presupuneri, deoarece cum am menționat în introducere, multe din rețelele analizate astăzi se presupune că sunt ”tree-like” dar nu sunt verificate.

Rezultatele pe care le-am obținut sunt cele pe care le-am așteptat. Ba mai mult, pe lângă calculul hiperbolicității Gromov pentru o rețea complex, am reușit să implementez și calculul aceleiași hiperbolicități pe diferitele comunități ale rețelei. Aceste comunități se obțin prin aplicarea modularității, metrică deja existent, asupra rețelei complexe.

O direcție pentru viitor ar fi să calculez această hiperbolicitate pe grafuri dinamice, și să evidențiez modificările apărute de-a lungul timpului, pe rețeaua complexă studiată. Pentru asta este însă nevoie de încă un pic de analiză, asupra modului în care se poate implementa acest feature.

În concluzie, obiectivul a fost atins, pluginul funcționează corespunzător, și am speranța că va fi utilizat în analiza rețelelor complexe.

Bibliografie

Wang, X. F., & Chen, G. (2003). Complex networks: small-world, scale-free and beyond. IEEE circuits and systems magazine, 3(1), 6-20.

Newman, M. E. (2003). The structure and function of complex networks.SIAM review, 45(2), 167-256.

Boccaletti, S., Latora, V., Moreno, Y., Chavez, M., & Hwang, D. U. (2006). Complex networks: Structure and dynamics. Physics reports, 424(4), 175-308.

Van Steen, M. (2010). Graph theory and complex networks. An introduction,144.

Cohen, N., Coudert, D., & Lancin, A. (2012). Exact and approximate algorithms for computing the hyperbolicity of large-scale graphs (Doctoral dissertation, INRIA).

Adcock, A. B., Sullivan, B. D., & Mahoney, M. W. (2013, December). Tree-like structure in large social and information networks. In 2013 IEEE 13th International Conference on Data Mining (pp. 1-10). IEEE.

Abu‐Ata, M., & Dragan, F. F. (2016). Metric tree‐like structures in real‐world networks: an empirical study. Networks, 67(1), 49-68.

https://github.com/gephi/gephi/wiki

Bastian, M., Heymann, S., & Jacomy, M. (2009). Gephi: an open source software for exploring and manipulating networks. ICWSM, 8, 361-362.

Heymann, S. (2014). Gephi. In Encyclopedia of social network analysis and mining (pp. 612-625). Springer New York.