CAPITOLUL 3

Capitolul Conectivitate si interdependenta in sistemele adaptive complexe

CAPITOLUL CONECTIVITATE SI INTERDEPENDENA IN SISTEMELE ADAPTIVE COMPLEXEUna dintre cele mai importante caracteristici ale CAS se refer la conectivitatea i interdependena dintre elementele sale, dar i a ntregului sistem cu celelalte elemente precum i cu alte sisteme din mediul nconjurtor. CAS constau dintr-un numr foarte mare de elemente distincte, capabile s interacioneze unul cu altul i cu mediul nconjurtor (deci cu alte sisteme adaptive complexe), ceea ce face ca sistemul s devin organizat fr s fie aplicat vreun principiu de organizare extern (emergena organizrii). Drept urmare, descompunerea sistemului i studierea prilor sale componente, izolat una de celelalte nu poate s contribuie n nici un fel la nelegerea modului n care acesta funcioneaz.

n Encyclopedia Britannica se arat c Ceea ce face un sistem s fie sistem i nu o simpl colecie de elemente sunt conexiunile i interaciunile dintre componentele sale, ca i efectul pe care aceste legturi l are asupra comportamentului su. De exemplu, relaiile de dependen dintre capital i munc fac o economie; fiecare component luat separat nu ar fi suficient.

O privire mai atent asupra structurii CAS relev cteva caracteristici interesante ale acestora n ceea ce privete proprietile de mai sus. Astfel, CAS: (a) conin un mare numr de elemente interdependente (de exemplu molecule, neuroni, indivizi, piee, organizaii sociale etc.); (b) interaciunile dintre aceste elemente nu sunt deterministe; i (c) topologia interaciunilor este distribuit. Prima caracteristic se refer la faptul c un sistem poate fi analizat la nivel microscopic, mesoscopic sau macroscopic, putnd extinde dimensiunile sale pn la infinit. Faptul c, n raport cu necesitile analizei, ne oprim la un anumit nivel nu epuizeaz nici pe departe informaiile i cunotinele pe care le putem obine referitor la acelai sistem dar abordat la un alt nivel. Din aceast cauz, studierea CAS constituie o surs inepuizabil de cunoatere a lumii reale. Caracterul incert al interdependenelor dintre elemente presupune c, la un moment de timp dat, ntre dou sau mai multe elemente, conexiunile se pot forma cu o anumit probabilitate condiionat de factori extrem de diferii, ceea ce introduce o imens varietate a tipurilor de conexiuni posibile ntre elemente. n sfrit, distribuirea interaciunilor indic faptul c un CAS nu este omogen n ceea ce privete structura interaciunilor precum i distribuirea lor spaial. Aceast distribuire se poate referi pentru unele sisteme doar la un spaiu restrns (ni) n care acesta poate s apar i s existe (anumite specii de plante i animale, firme specializate n extracia unor zcminte etc.), dar pentru alte sisteme distribuirea poate merge pn la ntreaga suprafa a globului pmntesc (companiile transnaionale, pieele globale etc.).

Oamenii de tiin atrag tot mai frecvent atenia c ne aflm ntr-o perioad n care are loc o transformare profund a ntregii viei economice i sociale, transformare n care reeaua de conexiuni devine o form esenial de organizare n toate domeniile. F. Capra arat c Funciile sociale dominante sunt organizate n tot mai mare msur n jurul reelelor, iar participarea la aceste reele este o surs esenial de putere. (F. Capra, op. cit., pag. 214). Unii cercettori merg chiar mai departe afirmnd, cum o face Castells ntr-o analiz sociologic profund a Erei Informaiei, c asistm la dispariia statului-naiune, care este nlocuit cu statul-reea ai crui ceteni sunt interdependeni. ntr-un astfel de stat, luarea deciziilor politice majore trebuie s in seama de efectele pe care acestea le-ar exercita aceste decizii asupra tuturor membrilor societii, fiindc acetia vor afecta cu necesitate ntreaga reea.

4.1 Ce sunt reelele complexe?

O reea reprezint o mulime de noduri sau vrfuri care sunt conectate ntre ele prin arce. Sistemele organizate sub form de reele sunt extrem de frecvente n natur, tehnic, economie sau societate. Exemple de astfel de sisteme care conin reele sunt Internetul, reelele neuronale, reelele metabolice, reelele de comunicaii, reelele de distribuie, reelele de afaceri etc.

Studiul sistematic al reelelor a nceput nc din 1735 cnd Euler a rezolvat prima problem de drumuri ntr-o reea, cunoscut sub numele de problema podurilor de la Knisberg i ntemeind, astfel, teoria modern a grafelor. Conform manuscriptului lui Euler, n oraul Knisberg din Prusia exist o insul A, numit Kneiphoff, cu cele dou brae ale rului Pregel curgnd n jurul ei. Exist apte poduri a, b, c, d, e, f i g traversnd cele dou brae. Problema este dac o persoan poate s planifice un drum n aa fel nct el s traverseze fiecare dintre aceste poduri odat i numai odat. [] Pe baza celor de mai sus am formulat urmtoarea problem general pontru mine nsumi. Dndu-se orice configurae a rului i ramurile n care acesta poate fi separat, ca i numrul de poduri, s se determine dac este posibil s se traverseze fiecare pod doar odat. Soluia lui Euler la aceast problem s-a dezvoltat natural din formularea problemei, artnd nc odat ct de important este formularea problemei, poate chiar mai mult de ct rezolvarea acesteia. Euler a observat c distana fizic nu are importan n aceast problem i a reprezentat-o sub forma unui graf o mulime de noduri i legturi conectnd fiecare pereche de noduri (Figura 4.1)

Figura 4.1: Problema lui Euler a celor apte poduri

Euler a mprit nodurile n pare i impare pe baza paritii gradului unui nod, deci a numrului de legturi direct conectate la nod. El a demonstrat c:

1) Suma gradelor nodurilor unui graf este par;

2) Fiecare graf trebuie s aib un numr par de noduri impare.

Aceste constatri l-au condus la urmtorul rezultat:

a) Dac numrul de noduri impare este mai mare dect 2 nu exist un drum Euler (deci un drum ntre dou noduri arbitrare n care fiecare legtur din graf apare exact o dat;

b) Dac numrul de noduri impare este 2, exist drumuri Euler plecnd din fiecare dintre nodurile impare;

c) Dac nu exist noduri impare, drumurile Euler pot ncepe din oricare nod arbitrar.

Deoarece toate cele patru noduri din problema podurilor sunt impare, Euler a demonstrat c nu exist un drum care s traverseze fiecare pod o singur dat. Aceast lucrare a lui Euler a dus, mai trziu, la apariia teoriei grafelor i de aici la teoria actual a reelelor prin contribuia esenial a matematicienilor unguri Erds i Reny.

Reelele sunt studiate astzi extensiv n multe domenii tiinifice (tehnic, ecologie, biologie, economie, tiina calculatoarelor, tiine sociale .a.) deoarece cu ajutorul lor se poate reprezenta destul de uor structura intern a unui sistem complex ct i interaciunile dintre elementele componente (subsistemele) acestuia. n ultima perioad interesul pentru reelele complexe a crescut enorm, mai ales n tiinele economice i sociale. Sistemele studiate de aceste tiine ncorporeaz reele sociale complexe care au, de regul, drept vrfuri indivizi, companii, corporaii, piee, grupuri sociale mici, comuniti umane .a., iar drept arce interaciunile dintre acestea.

n reelele sociale complexe pot fi puse n eviden anumite proprieti care au o influen puternic asupra modului n care se propag influenele reciproce dintre componentele reelei i, mai ales, asupra modului n care evolueaz reeaua n decursul timpului.

Dezvoltarea exploziv a comunicaiilor i rolul jucat de acestea n buna funcionare a sistemelor economice i sociale a dat un impuls puternic cercetrilor din domeniul reelelor sociale complexe. Utiliznd concepte i metode noi, bazate pe analiza statistic a proprietilor vrfurilor i arcelor unei reele complexe, au putut fi abordate reele care conin milioane sau chiar miliarde de noduri i arce. Proprietile grafelor de dimensiuni mici (avnd cteva zeci sau sute de noduri i arce) se dovedesc inoperante n condiiile reelelor complexe de dimensiuni mari. De exemplu, dac n cazul uni graf de dimensiuni mici putem determina ce influen exercit dispariia unui nod sau unui arc, n cazul reelelor complexe acest lucru nu prezint prea mult importan, trecnd pe primul plan probleme cum ar fi: Ce procent dintre vrfuri trebuie s dispar astfel nct acest lucru s afecteze n mod semnificativ conectivitatea reelei?.

Exist i ali factori care au determinat apariia unei schimbri n interesul cercettorilor pentru reelele complexe. Atunci cnd o astfel de reea cuprinde milioane sau miliarde de componente, reprezentarea ei vizual este extrem de dificil. Totui, combinarea metodelor statistice de analiz a reelelor cu mijloacele de reprezentare pe calculator a obiectelor 3D a dus la apariia unei adevrate imagistici a reelelor complexe, care pot fi acum analizate nu numai cu mijloace formate, dar i vizual.

Cercetrile actuale n acest domeniu se orienteaz cu precdere n trei mari direcii. Prima direcie ncearc s determine proprietile statistice ale reelelor complexe, proprieti cu ajutorul crora putem caracteriza structura i comportamentul sistemelor care includ astfel de reele. A doua direcie ncearc creeze modele ale reelelor cu ajutorul crora s nelegem mai bine proprietile reelelor i efectele lor asupra sistemelor complexe. A treia direcie ncearc s gseasc regulile i legitile care guverneaz evoluia reelelor, astfel nct s se poat stabili modul n care aceste reguli i legiti influeneaz vrfurile individuale sau o parte a reelei.

4.2 Tipuri de reele complexe

Existena unui numr mare de noduri i arce ntre acestea nu reprezint singura surs de complexitate n cazul reelelor din lumea real. Frecvent, nodurile i/sau arcele din reele sunt de tipuri diferite. De asemenea, vrfurile i arcele pot avea o serie de proprieti, calitative i cantitative, care sporesc complexitatea reelelor. De exemplu, ntr-o reea complex din economie, nodurile pot s reprezinte ageni economici diferii, productori sau consumatori, instituii financiare sau agenii economice ale statului. Arcele pot reprezenta relaii de cooperare, relaii de competiie, obligaii de plat sau, pur i simplu, proximitatea geografic.

Arcele pot fi orientate i pot conine informaii privind intensitatea sau ponderea acestor relaii. De asemenea, ntre reele exist diferene n raport cu sistemele complexe pe care le reprezint. Datorit acestor aspecte, reelele complexe au fost clasificate n funcie de natura sistemelor complexe reprezentate n urmtoarele tipuri:

a) Reele sociale:

Colaborarea actorilor;

Comitete de direcie; Contacte tiinifice; Mesaje e-mail; Contacte sexuale .a.b) Reele informaionale:

World Wide Web;

Reele de citri;c) Reele tehnologice:

Internetul;

Reeaua de calculatoare Grid;

Pachetele software; Circuitele electronice; Reeaua de aeroporturi;

Reeaua de cale ferat;d) Reele biologice:

Reele metabolice;

Reele genetice; Reele neurale; Reele ecologice etc.4.2.1 Reele sociale complexe

O reea social reprezint o mulime de oameni sau grupuri de oameni cu un anumit tip de contacte sau interdependene ntre ei. Tipurile principale de contacte pot fi relaii de prietenie sau de rudenie, relaii de afaceri ntre companii, contactele sociale dintr-o anumit comunitate, contacte tiinifice dintr-o comunitate de oameni de tiin .a. Sociologia i alte tiine sociale au fost, de-a lungul timpului, interesate de astfel de reele. Sociologi precum Jacob Moreno sau Elton Mayo au fost promotorii unor metode cantitative de studiu al grupurilor mici (primul a studiat relaiile de prietenie dintr-un colegiu, iar al doilea reelele sociale create ntre muncitorii din fabricile din Chicago). Anatol Rapaport a fost printre primii matematicieni preocupai de proprietile cantitative ale reelelor.

Figura 4.2 Reeaua legturilor de prietenie ntr-un colegiu american

Figura 4.3 : Reea colaborativ

n ultimii ani, modelele denumite Small-world ale lui Milgram au dus la un concept devenit celebru al celor ase grade de separare.

Datorit problemelor legate de acurateea datelor, subiectivitatea rspunsurilor i numrul mic de eantioane, reelele sociale necesit un efort destul de mare n construcie i studiu. Din aceast cauz, o tot mai mare atenie se acord reelelor colaborative care reprezint reele n care participanii colaboreaz n grupuri diferite, iar legturile dintre perechile de indivizi sunt determinate de apartenena la un grup comun. De exemplu, o reea colaborativ este cea a actorilor de film care apare n Internet Movie Database. n aceast reea, actorii care apar n filme sunt considerai ca fiind conectai dac ei apar n acelai film.

Figura 4.4: Reeaua contactelor sexuale ntr-un campus studenesc

O alt reea colaborativ este cea a directorilor de companii, doi directori fiind legai ntre ei dac aparin aceluiai Consiliu de directori.

Un alt tip de reea social este reeaua comunicaional. n cadrul acesteia, fiecare arc (orientat) ntre doi oameni reprezint un mesaj trensmis prin pot, telefon sau e-mail de la unul la cellalt. De exemplu, ntr-o reea a telefoanelor date, numrul de vrfuri ale grafului care corespunde unui numr de telefon, este enorm, ajungnd la 50 de milioane, cea mai mare reea dup cea a World Wide Web (Aiello .a.). Ebel .a. au reconstruit experimentul lui Milgram n cazul mesajelor e-mail transmise ntre 500 de studeni de la universitatea din Kiel, Germania. n aceast reea, vrfurile sunt adrese de e-mail, iar arcele orientate reprezint mesaje transmise de la un student la altul. S-a observat, n acest caz c regula celor ase grade de separare se menine i n cazul unei astfel de reele.

4.2.2 Reele informaionale

O alt categorie de reele este cea a reelelor informaionale (sau de cunoatere). Exemplul cel mai des ntlnit este cel al reelei citrilor ntre articolele tiinifice. Vrfurile acestei reele sunt articole, iar un arc orientat de la articolul A la articolul B arat c A citeaz pe B. Reelele de acest tip sunt aciclice deoarece o lucrare citat nu poate, la rndul su, s citeze o alt lucrare n care este citat deoarece ea nu este nc scris. Reelele de citri sunt o surs important de date pentru studiile statistice ale reelelor datorit abundenei i acurateei datelor oferite. Astfel de date l-au condus pe Alfred Lotka la descoperirea, n 1926 a aa-numitei Legi a Productivitii tiinifice. Conform acestei legi, distribuia numrului de lucrri tiinifice scrise de un om de tiin urmeaz o lege de tip putere. Deci numrul de oameni de tiin care au scris k lucrri scade cu k- pentru o anumit constant . Aceast lege s-a constatat c se aplic nu numai n acest domeniu, dar i n alte domenii cum ar fi artele sau medicina.

Un alt exemplu de reea inforrmaional o reprezint World Wide Web care este o reea de pagini Web coninnd informaii, legate ntre ele prin hiperlinkuri de la o pagin la alta. WWW nu se confund cu Internetul, care reprezint reeaua fizic de calculatoare legate mpreun prin fibre optice i alte tipuri de conexiuni.

Figura 4.5 : Reeaua WWW

WWW este o reea ciclic; nu exist o relaie de ordine natural ntre site-uri i nici o regul care s previn apariia de bucle nchise. n ultimul timp, WWW este intens studiat, avnd o serie de proprieti interesante.

Tot n categoria reelelor informaionale se includ i reelele peer-to-peer care sunt reele virtuale de calculatoare ce mpart ntre ele fiiere apelate de utilizatori plasai ntr-o reea local. Reeaua relaiilor ntre clasele de cuvinte dintr-un tezaur este utilizat n definirea de ontologii i gsirea sensului celui mai potrivit al unui concept care reprezint o idee. Reelele semantice (Semantic Web) sunt astzi intens studiate deoarece ele permit reprezentarea structurii unui limbaj i, prin aceasta, ajut la realizarea corespondenelor dintre limbaje n traducerea automat.

Reelele prefereniale reprezint reele informaionale bipartite. O reea preferenial este reeaua care are dou tipuri de vrfuri reprezentnd indivizi i obiecte preferate, cum ar fi cri, filme etc., cu o latur conectnd fiecare individ cu crile sau filmele preferate. Laturile acestor reele prefereniale sunt ponderate n funcie de intensitatea acestor preferine. Prin intermediul algoritmilor de filtrare colaborativ i a sistemelor de recomandare se pot determina liste de obiecte preferate de doi sau mai muli indivizi n acelai timp. Astfel de reele au multiple aplicaii n comerul electronic.

4.2.3 Reele tehnologiceA treia clas de reele sunt cele tehnologice care sunt realizate de om i utilizate, n general, pentru distribuia unor produse sau resurse, cum ar fi electricitatea, apa sau informaia. Reelele electrice se pot ntinde pe tot cuprinsul unei ri sau chiar continent. Astfel de reele tehnologice sunt reeaua de drumuri, ci ferate sau chiar a strzilor dintr-un ora. Reeaua de ruri poate fi considerat o reea natural, dar dac ea este folosit pentru transportul de mrfuri, devine o reea tehnologic.

O reea tehnologic mult studiat este Internetul care reprezint reeaua de conexiuni fizice ntre calculatoare. Deoarece exist un numr extrem de mare de calculatoare conectate la Internet, numr care este n continu cretere, structura acestei reele este, de obicei, studiat la nivelul ruterelor, calculatoarelor cu scopuri speciale (providere) sau al controlului fluxurilor de date.

O reea autonom (Intranet) este cea care conecteaz un grup de calculatoare locale ntre care fluxurile de date sunt transmise cu ajutorul Internetului. Calculatoarele unei universiti pot forma un sistem autonom (Intranet) care poate avea conexiuni interne dar i externe.Figura 4.6 Reeaua Internet

4.2.4 Reele biologiceUn mare numr de sisteme biologice pot fi reprezentate ca reele complexe. Un exemplu l reprezint reeaua metabolic, n care vrfurile sunt diferite substane, iar arcele unesc acele vrfuri ntre care exist o reacie metabolic ce duce la apariia unui produs. Individul este alctuit dintr-o reea gigantic de tip metabolic.

O alt reea este cea genetic. O gen, care conine un cod genetic dat de ordinea proteinelor coninute, poate fi controlat de prezena altor proteine, care sunt activatori sau inhibitori, astfel nct genomul nsui formeaz o reea ale crei vrfuri sunt reprezentate de proteine i arce reprezint dependena de producia de proteine din celelalte vrfuri. Reelele genetice reprezint nc un domeniu de studiu i cercetare pentru viitor, deoarece nc nu sunt clarificate toate dependenele dintre proteinele ce alctuiesc codul genetic.

Un alt tip de reea biologic este reprezentat de ecosisteme n care vrfurile sunt speciile din cadrul ecosistemului iar arcele orientate de la specia A la specia B indic faptul c A l hrnete pe B.

Figura 4.7 Reeaua uni ecosistem

Reelele neurale reprezint un alt tip de reea biologic de o importan foarte mare. Structura acestei reele a creierului uman este nc un subiect intens de studiu n tiinele creierului.

4.3 Proprietile reelelor complexe

Studiul reelelor complexe necesit o varietate de tehnici i metode cu ajutorul crora s nelegem i s putem face previziuni privind comportamentul sistemelor complexe care le conin. n continuare vom introduce cteva dintre proprietile reelelor complexe sub forma unor msuri cu ajutorul crora putem exprima formele interconexiunilor dintre diferitele elemente componente ale sistemelor complexe. Dup aceea, ne vom referi la modalitile de utilizare ale acestor proprieti cantitative n studiul teoretic i empiric al reelelor complexe.

Pentru a fixa lucrurile, n termeni matematici, o reea este un graf n care vrfurile (nodurile) i laturile (arcele) au valori asociate lor. Un graf G este definit de o pereche de mulimi G={V, E}, unde V este mulimea vrfurilor, notate cu v1, v2, , vn i E este o mulime de laturi care conecteaz perechile de vrfuri vi, vj aparinnd lui V. O mulime de vrfuri unite de laturi este cel mai simplu tip de reea.

Figura 4.8 Un graf cu opt vrfuri

Reelele pot fi ns mult mai complicate. De exemplu, pot exista mai multe tipuri de vrfuri sau mai multe tipuri de laturi. De asemenea, vrfurile pot avea anumite proprieti. De asemenea, laturile pot fi orientate (caz n care se numesc arce) iar grafele cu astfel de arce se numesc digrafe sau grafe direcionate. Arcele sau chiar i laturile pot avea ponderi nscrise pe ele, ponderi care pot indica diferite lucruri ce caracterizeaz legtura dintre vrfuri (mrimea unui flux, intensitatea unei relaii, probabilitatea de realizare a conexiunii etc.).

n figura 4.9 se reprezint diferite tipuri de reele.

Figura 4.9 Diferite tipuri de reele

4.3.1 Microscara i macroscara

Atunci cnd abordm reelele complexe, putem s o facem la microscar sau macroscar. Din punct de vedere microscopic, interesul se va ndrepta ctre rolul jucat de vrfuri n contextul general al reelei. Din aceast perspectiv, au fost introduse o serie de msuri ale centralitii vrfurilor i ale rolurilor jucate de ctre acestea. De exemplu, gradul unui vrf corespunde cu numrul de legturi care ajung la acesta, iar distana medie este o msur a distanei msurat ca cel mai mic numr de arce necesare pentru a trece de la un vrf la altul. Un alt indicator, coeficientul de clusterizare al unui vrf, msoar numrul de legturi dintre vecinii unui vrf dat. n sfrit, o alt msur interesant o reprezint betweenness-ul unui vrf care corespunde numrului de drumuri de lungime minim dintre fiecare pereche de vrfuri dintr-o reea care merg la un nod de referin.

Pe de alt parte, la nivel macroscopic, atuci cnd avem de-a face cu reele foarte mari, rolul jucat de vrfurile individuale nu mai prezint interes, astfel c se prefer o caracterizare statistic a reelei. La nivel de macroscar sunt studiate cantiti medii, cum ar fi gradul mediu al vrfurilor, distana medie dintre vrfuri, coeficientul mediu de clusterizare, diametrul reelei, msurat ca distana maxim dintre vrfuri. O alt caracterizare statistic a reelelor complexe se poate face cu ajutorul distribuiei gradelor, al ncrcrii acestora sau al corelaiilor.

4.3.2 Conectivitatea

Gradul n care vrfurile unei reele sunt conectate direct se numete conectivitate. O reea cu o conectivitate nalt are un numr mare de laturi n raport cu numrul de vrfuri. Pentru a calcula conectivitatea unei reele cu N vrfuri i k laturi, avem:

4.3.3 Distribuia gradelor

Gradul unui vrf ntr-o reea este dat de numrul de laturi sau conexiuni ale unui nod. Funcia de distribuie P(k) d probabilitatea ca un vrf ales aleatoriu s aib exact k laturi. Reprezentarea lui P(k) pentru o reea complex formeaz o histogram a gradelor asociate vrfurilor, aceasta reprezentnd distribuia gradelor sau numrul de vrfuri care au acelai numr de laturi din reea.

4.3.4 Drumul mediu de lungime minim

Lungimea drumului mediu, l , reprezint numrul mediu de laturi sau conexiuni dintre vrfuri, care trebuie s fie strbtute pe drumul cel mai scurt dintre dou vrfuri dintr-o reea.

Acest numr se calculeaz cu ajutorul relaiei:

unde lmin(i,j) este distana minim dintre vrfurile vi i vj.

4.3.5 Diametrul reelei

Diametrul unei reele, D este cel mai lung drum minim din reea. Diametrul este definit ca:

EMBED Equation.3 4.3.6 Coeficientul de clusterizareO proprietate comun multor reele sociale este clica. Aceasta reprezint un grup de prieteni n care fiecare membru al grupului i cunoate pe ceilali membri.

Pentru un vrf dat, vi dintr-o reea cu ki vecini, gradul de clusterizare n jurul vrfului vi este definit ca raportul dintre numrul de legturi existente n realitate cu cei ki vecini i numrul de legturi poteniale. Fie Ei numrul de legturi existente ntre cei ki vecini. Coeficientul de clusterizare este atunci dat de:

4.3.7 SubgrafeUneori n studiul reelelor complexe apare necesitatea separrii din cadrul acesteia a unor pri care sunt definite prin anumite proprieti comune ale vrfurilor i/sau laturilor. Aceste pri reprezint subgrafe. Un graf Gi constnd dintr-o mulime de vrfuri Vi i o mulime de laturi Ei se numete subgraf al lui G={V, E} dac ViV i Ei E. cele mai simple exemple de subgrafe sunt ciclurile, arborii i subgrafele complete.

Un ciclu este o bucl nchis de k laturi, astfel nct diecare dou laturi consecutive au doar un vrf comun.

Un arbore este de ordin k dac are k vrfuri i k-1 laturi i nici un subgraf al su nu este un ciclu. Gradul mediu al unui arbore de ordin k este dat de:

care tinde ctre 2 cu ct arborele are dimensiuni mai mari.

Un subgraf complet de ordin k conine k vrfuri i toate cele laturi posibile ntre acestea; cu alte cuvinte, toate vrfurile din subgraful complet sunt conectate la celelalte vrfuri.

4.3.8 Mrimea componentei gigant

n general, o reea complex poate conine pri care pot fi deconectate (separate) de reea atunci cnd analiza o impune. Considernd un cluster de vrfuri din care se poate atinge oricare vrf al acestui cluster, acesta se numete component puternic conectat. Dac cea mai mare component puternic conectat conine o parte finit a mulimii vrfurilor dintr-o reea, aceasta se numete component puternic conectat gigant.

Figura 4.10 Componenta puternic conectat gigant

Clusterele conectate obinute dintr-o reea complex orientat prin ignorarea direciei arcelor acesteia se numesc componente slab conectate i se poate defini componenta slab conectat gigant ca acea component slab conectat care are vrfurile cele mai multe.

4.3.9 Criticalitatea

Poate cea mai interesant proprietate a reelelor complexe o constituie criticalitatea acestora. Aceasta presupune existena unui prag critic ncepnd de la care se formeaz componentele gigant. Sub acest prag, reeaua exist sub forma unor subgrafe deconectate. Peste acest prag, graful se transform ntr-un cluster complet conectat.

Figura 4.11 Fenomene critice n reele complexe

n figura 4.11 (a) este reprezentat creterea numrului de componente ale reelei iar n figura 4.11 (b) si 4.11 (c) sunt date caracterizari statistice ale reelei respective (Abaterea standard i, respectiv, Timpul de traversare)4.4 Modelarea evoluiei reelelor complexe

Realizarea reelelor complexe reale necesit un efort deosebit deoarece sunt, de cele mai multe ori, necesare foarte multe date i informaii care sunt culese n condiiile n care nsi reeaua poate evolua. Din aceast cauz, s=a pus problema obinerii de reele complexe cu anumite proprieti fr s fie necesar culegerea i prelucrarea datelor. Astfel au aprut modelele reelelor sociale, instrumente cu ajutorul crora putem studia proprietile reelelor existente n realitate fr a face efortul implicat de culegerea de date.

Vom prezenta n continuare cteva astfel de modele mai bine cunoscute din domeniul reelelor sociale complexe.

4.4.1 Modelul grafelor aleatoare (Erds i Renyi)

Modelul minimal al grafelor aleatoare are N noduri (vrfuri) legate ntre ele prin arce sau laturi plasate ntre perechi de vrfuri alese aleator.

Fie GN,p graful n care ntre dou vrfuri exist un arc cu o probabilitate egal cu p. De fapt, GN,p reprezint o mulime de grafe cu N vrfuri, n care fiecare graf are o anumit probabilitate de apariie a laturilor.

Vom exprima proprietile lui GN,p n funcie de p, care este gradul mediu al unui vrf, adic numrul mediu de laturi incidente acelui vrf.

Numrul de arce dintr-un graf aleator este dat de iar numrul de terminaii ale laturilor este 2, deoarece fiecare latur are dou puncte terminale (dou vrfuri n care incepe i se termin). Astfel, vom avea un numr de N/2 astfel de terminaii.

Atunci gradul mediu al unui vrf oarecare se scrie:

deoarece N este foarte mare.

Deci, dac cunoatem numrul de vrfuri N, atunci orice proprietate care poate fi exprimat n funcie de acesta poate fi exprimat i n funcie de gradul mediu al unui vrf, z. z se mai numete i numr de coordonare al reelei.

Probabilitatea pk ca un vrf dintr-o reea aleatoare s aib gradul egal exact cu k este dat de distribuia de probabilitate binomial:

unde reprezint simbolul pentru .

Atunci cnd numrul de vrfuri din reea, N este mult mai mare dect kz, distribuia de probabilitate a gradelor medii ale vrfurilor devine:

care este distribuia de probabilitate Poisson.

Se poate arta c grafele aleatoare au anumite proprieti interesante. De exemplu, dac o persoan A dintr-un astfel de graf are z vecini i fiecare vecin al su are, de asemenea, z vecini, atunci A are z2 vecini de ordinul doi. Extinznd argumentaia, A are z3 vecini de ordinul trei, z4 vecini de ordinul patru .a.m.d. Deoarece multe persoane au ntre 100 i 1000 de cunotine, rezult c z4 este ntre 108 i 1012 (dac z = 100 = 102 atunci z4 = 108 i dac z = 1000 = 103 atunci z4 = 1012) mrimi care sunt comparabile cu ntreaga populaie a omenirii.

Notnd cu S gradul de separare care constituie puterea lui z pentru care se poate atinge ntreaga populaie, atunci , de unde obinem prin logaritmare Creterea logaritmic a numrului de grade de separare odat cu creterea mrimii reelei complexe se numete efect de lume mic (small-world effect) i este una dintre cele mai interesante proprieti ale unor astfel de reele. Deoarece log N crete lent odat cu creterea lui N, rezult c numrul de grade de separare rmne mic chiar i n condiiile n care N devine foarte mare.

De exemplu, Albert .a. (1999) studiaz proprietile reelei de hiperlinkuri dintre site-urile WWW. Ei estimeaz c dei numrul de documente este N 8x108, distana medie dintre documente (numrul mediu de arce care unesc oricare dintre site-uri) este n jur de 19, iar gradul de separare este ntre 4 i 5.

O alt proprietate a grafelor aleatoare ca modele ale reelelor sociale complexe se refer la faptul c cercurile de cunotine ale persoanelor tind s se suprapun n mare parte. Prietenii prietenilor ti pot fi i prietenii ti. Acest lucru face ca n reelele sociale reale s nu fie adevrat c o persoan are z2 vecini de ordinul doi, deoarece multe dintre aceste persoane se regsesc i printre vecinii de ordinul unu ai lui A. o astfel de proprietate se numete clusterizarea reelelor. Un graf aleatoriu nu are proprietatea de clusterizare deoarece probabilitatea ca doi dintre prietenii lui A s fie prieteni unul cu cellalt nu este mai mare dect probabilitatea ca dou persoane alese aleatoriu s fie prieteni. Pe de alt parte, clusterizare apare n mod clar ntr-un numr de reele complexe reale.

tim c coeficientul de clusterizare, C a fost definit ca fracia medie a perechilor de vecini ai unui vrf care sunt, de asemenea, vecini unul cu cellalt. ntr-o reea complet conectat, deci n care fiecare vrf este conectat cu toate celelalte, C = 1; ntr-un graf aleator ns C = z/N , care este foarte mic pentru reele de dimensiuni mari.

O alt diferen dintre grafele aleatoare i reelele reale este n ceea ce privete distribuia gradelor care, n cazul reelelor foarte mari este de tip Poisson n cazul primelor i o distribuie de tip putere n cazul al doilea. O distribuie a gradelor de tip putere este de forma:

unde este un numr real mai mare ca zero.

n tabelul 4.1 se dau cteva valori msurate i reale ce arat diferenele care exist ntre reelele aleatoare i cele reale.

Tabelul 4.1: Numrul de vrfuri, N, gradul mediu z i coeficientul de clusterizare C pentru un numr de reele.REEAUANzCoeficient de clusterizare C

MsuratGraf aleator

Internet63743.80.240.00060

WWW15312735.20.110.00023

Reea electric49412.70.0800.00054

Reea ecologic152025115.50.0810.000010

Colaborare matematic 2533393.90.150.000015

Colaborare ntre actori449913113.40.200.00025

Directori de companii767314.40.590.0019

Co-apariia cuvintelor46090270.10.440.00015

Reea neuronal28214.00.28 0.049

Reea metabolic31528.30.590.090

Reea de hran1348.70.220.065

Reelele aleatoare se pot realiza i cu ajutorul calculatorului, plecnd de la o latice (o mulime de puncte uniform distribuite, de exemplu sub form de cerc) ntre care se duc arce prin alegerea aleatoare a dou puncte ale laticei. n figura 4.12 se reprezint un astfel de graf aleator obinut dintr-o latice cu probabilitile de conectare pk egale cu 0.0, 0.05, 0.10 i, respectiv, 0.15.

Figura 4.12

Se observ c cu ct pk este ales mai mare graful i pierde caracterul de latice i se apropie tot mai mult de forma unui graf aleator. De fapt, pentru o valoare relativ mic a lui pk, graful are o distan medie scurt ntre vrfuri fr o schimbare apreciabil a gradului de clusterizare.

Acest lucru explic efectul de lume mic despre care am mai vorbit i care a dus la apariia unei alte clase de modele ale reelelor.

4.4.2 Modelul reelelor lumii mici

Ctre sfritul anilor 60 ai secolului trecut, Milgram (1967) a efectuat un experiment devenit faimos. Dei nu exista o reea fizic n spatele acestui experiment, rezultatele arat fora deosebit a structurii reelelor sociale complexe. n esen, experimentul examineaz lungimea drumurilor dintre vrfurile unei reele sociale, cerndu-se participanilor la acest experiment s trimit o scrisoare unuia dintre cunoscuii si direci, cu rugmintea ca aceasta s fie transmis mai departe n acelai mod, pn cnd i atinge inta, reprezentat de un destinatar final. Dei multe scrisori s-au pierdut pe drum i nu au mai ajuns la destinaie, aproape un sfert dintre ele i-au atins inta n medie, o scrisoare a trebuit s treac prin minile a cinci sau ase persoane pn cnd a ajuns la destinaie. Acest experiment a reprezentat sursa popularului concept de ase grade de separare.

Existena efectului de lume mic, demonstrat de experimentul de mai sus, era cunoscut nc nainte ca acesta s fie efectuat. Ideea apare ntr-o povestire scurt Chains a scriitorului maghiar Frigyes Korinthy, publicat n 1929, iar manuscrisul matematicienilor Pool i Kochen care a circulat ca un preprint cu un deceniu nainte de efectuarea experimentului lui Milgram fcea referire la acest efect fr ns a-i da nu nume.

Dac considerm o reea neorientat i l este distana medie geodezic (cea mai scurt) dintre perechile de vrfuri ale reelei, atunci:

unde dij reprezint distana geodezic de la vrful i la vrful j. Se observ c n aceast medie se include i distanta la un vrf la al nsui (care este zero).

n tabelul 4.2 sunt date distanele medii geodezice pentru cteva tipuri de reele complexe.

Tabelul 4.2

TIPUL DE REEAN

\(Numrul de vrfuri)M

(Numrul de arce)L

(Distana medie geodezic)

Reeaua actorilor de film449913253164823.48

Directori de companii7673553924.60

Mesaje e-mail59912863004.95

Internet10697319923.31

Reea de ci ferate587196032.16

Reea metabolic76536862.56

Reea neuronal30723593.97

Reea ecologic submarin1355982.56

Relaii interstudeni57347716.01

Studiile fcute pe diferite tipuri de reele reale au artat c efectul de lume mic este aproape general. n tabelul 4.2 se prezint cteva valori calculate ale lui L i se observ c pot exista i reele n care efectul de lume mic s nu apar. Chiar dac el nu apare la nivelul ntregii reele, ca n cazul reelei de relaii dintre studeni, acest efect este prezent la nivelul componentei gigant a reelei respective. Aceast component gigant reprezint subreeaua format de cel mai numeros grup de prieteni care poate fi extras din mulimea total a studenilor.

Efectul de lume mic are implicaii mari asupra dinamicii proceselor care se petrec ntr-o reea. De exemplu, dace consider procesul de difuzare a informaiei sau al oricrui lucru din cadrul reelei, efecul de lume mic implic faptul c acest proces se desfoar cu o vitez mare n cadrul ntregii reele. Vor fi necesari maximum ase pai pentru ca informaia s ajung la orice vrf din cadrul reelei. Acest efect se aplic nu numai informaiei, dar i reelelor Internet, n care sunt necesare maximum ase calculatoare provider prin care un pachet de informaii trebuie s treac pentru a ajunge la orice destinatar din reea, numrului de pai necesari pentru a strbate lumea utiliznd reeaua de aeroporturi, de exemplu, timpului necesar unei boli molipsitoare pentru a se rspndi n ntreaga populaie a unei regiuni etc.

4.4.3 Modelul reelelor libere de scal

Am artat mai sus c n cazul reelelor reale de dimensiuni mari, distribuia gradelor este de tip putere, , unde reprezint un coeficient pozitiv adimensional. Cel mai vechi exemplu de reea n care avem o astfel de distribuie este cea construit de Price plecnd de la citrile ntre lucrrile tiinifice menionate n revistele ISI. El a gsit o valoare a lui egal cu 2.5 pn la 3 i a reprezentat distribuia de tip putere a numrului de citri bibliografice din fiecare lucrare aprut n reviste ISI ntr-un interval de zece ani.

Mai recent, distribuia gradelor de tip lege a puterii a fost observat i n alte reele, cum ar fi WWW, Internetul, reelele metabolice, reeaua apelurilor telefonice etc.

O alt form funcional gsit pentru distribuia gradelor este cea exponenial, , care a fost descoperit, de exemplu, n cazul reelelor electrice, reelelor de ci ferate, reeaua actorilor, reele colaborative .a.

i n acest caz se poate observa c dac distribuia gradelor are o form particular, de tip putere sau exponenial, pentru o reea n ansamblul ei, subreele specifice ale acesteia pot avea alte forme funcionale. De exemplu, WWW are o distribuie a gradelor de tip putere n general, dar o distribuie uniform n cazul subdomeniilor.

n figura 4.13 sunt reprezentate distribuii ale gradelor cumulative pentru ase reele diferite. Pe axa orizontal a fiecrei figuri se reprezint gradul vrfului k, iar pe axa vertical este reprezentat probabilitatea cumulativ a gradelor, deci acel numr de vrfuri care au gradul mai mare sau egal cu k.

Figura 4.13 (a) reprezint reeaua colaborativ a matematicienilor; (b) reeaua citrilor ntre 1981 i 1997 a tuturor lucrrilor catalogate ISI; (c) o submulime de 300 milioane de vrfuri ale WWW din 1999; (d) Internetul ca sistem autonom, n aprilie 1999; (e) reeaua electric din vestul SUA; (f) reeaua interaciunilor dintre proteine ntr-o reea metabolic.

Cel mai cunoscut model al unei reele libere de scal este modelul Barabasi Albert n care se introduc dou elemente dinamice eseniale: creterea i conectarea preferenial. Pe de o parte, reteaua este supus permanent unui proces de cretere, ncepnd cu un mic numr de vrfuri complet conectate (C = 1). Pe de alt parte, creterea are loc n aa fel nct vrfurile nou introduse n reea sunt legate preferenial de acele rfuri care au cele mai multe conexiuni. n figura 4.14 se reprezint acest proces de cretere prin conexiuni prefereniale.

O implicaie major a acestui fapt este c apare un numr mic de vrfuri puternic conectate (hub-uri), n timp ce marea majoritate a vrfurilor are o conectivitate foarte mic. Aceste huburi joac un rol crucial n multe reele deoarece reeaua este foarte sensibil la atacuri intenionate dac intele sunt aceste huburi, dar este foarte robust la atacuri aleatoare, n care vrfurile int sunt alese aleatoriu.

Faptul c reelele sociale sunt libere de scal, ca i multe alte reele informaionale, tehnologice sau biologice demonstreaz existena unei similitudini uimitoare ntre sistemele adaptive complexe din natur, tehnic sau societate.

Figura 4.14

.5 Aplicaii ale reelelor complexe n economie i finane

Apariia i dezvoltarea studiului reelelor complexe a dus la multiple aplicaii ale proprietilor acestora n analiza economiilor sau ale unor pri ale acestora ca sisteme avnd o structur de reea social complex.

_1234570357.unknown

_1235170564.unknown

_1235171494.unknown

_1235184667.unknown

_1235184677.unknown

_1235173804.unknown

_1235180975.unknown

_1235181446.unknown

_1235179260.unknown

_1235172691.unknown

_1235171232.unknown

_1235171273.unknown

_1235170990.unknown

_1234574301.unknown

_1235170386.unknown

_1234570483.unknown

_1234569363.unknown

_1234570004.unknown

_1234570073.unknown

_1234569652.unknown

_1234568667.unknown

_1234568936.unknown

_1234568044.unknown