Introducció a les xarxes

  • Albert Díaz-Guilera

    Llicenciat en Física per la Universitat de Barcelona. Doctor en Ciències per la Universitat Autònoma de Barcelona (1987). Estades postdoctorals en laboratoris Gorlaeus (Leiden, Països Baixos) i “Centre de Physique du Solide” (Sherbrooke, Canadà). La seva recerca se centra actualment en els aspectes generals de la complexitat, sobretot en xarxes complexes. Essent per formació físic estadístic, les seves línies de recerca s’han anat ampliant per abastar els aspectes en diferents camps: biologia, economia, ciències socials, ciències de la computació, la lingüística. Col∙laboracions directes amb científics de diferents orígens han estat possible a través d’estades a diferents centres (Matemàtiques de l’Imperial College de Londres, Enginyeria Química i Biològica de la Universitat Northwestern, Ecologia UNAM, Institut de Potsdam de Climatogy, Potsdam Psicologia, Sociologia de la ETHZ).Autor de prop d’un centenar d’articles en revistes de la física i interdisciplinars. Ha fet més d’un centenar de xerrades en congressos i centres de recerca. Líder del grup de recerca PHYSCOMP2, investigador principal de projectes de governs català i espanyol i de la Unió Europea. Coordinador de la xarxa espanyola “Econosociofisica: Dinàmica i Fenòmens Col∙lectius de Sistemes socioeconòmics”.

PID_00215563_1
Cap part d'aquesta publicació, incloent-hi el disseny general i la coberta, no pot ser copiada, reproduïda, emmagatzemada o transmesa de cap manera ni per cap mitjà, tant si és elèctric com químic, mecànic, òptic, de gravació, de fotocòpia o per altres mètodes, sense l'autorització prèvia per escrit dels titulars del copyright.

1.Introducció a les xarxes

1.1.La importància de les xarxes o “Com Kevin Bacon ha ajudat a curar el càncer”

De tots és conegut aquest fenomen que anomenem demón petit. Quantes vegades no ens hem trobat un desconegut o una desconeguda i després de deu minuts de conversa ens en hem adonat que és cosí d’un amic del nostre germà.
Aquest fenòmen ha estat portat fins i tot al mon de l’espectacle. John Guare al començament de la dècada de 1990 va escriure una obra de teatre tituladaSix degrees of separationque es va representar durant un temps a Broadway i que més endavant es va adaptar al cinema amb actors de prestigi reconegut com ara Donald Sutherland. Per primera vegada es presentava de manera popular un fet que els sociòlegs coneixien des de feia anys, de fet des de principis del segle XX.
Enllaços recomanats
Entrada a la Viquipèdia sobre l’obra de teatre:
http://en.wikipedia.org/wiki/Six_Degrees_of_Separation_(play)
Però va ser un psicòleg social, Milgram, qui, al final de la dècada de 1960, va fer un experiment i va analitzar de manera sistemàtica aquest fenomen. Sense donar-hi un nombre en particular, pensava en la possibilitat que entre qualsevol parell de persones hi hagués un petit nombre d’intermediaris que permetessin fer arribar la informació de l’una a l’altra.
Va buscar una sèrie de persones als Estats Units perquè enviessin una carta personal a un advocat que vivia a prop de Boston, amb la condició que cada carta fos enviada a una persona que coneguessin personalment i, un cop rebuda, aquesta persona l’havia d’enviar a una altra que també conegués personalment, i així successivament. El resultat, sorprenent, és que el valor mitjà del nombre de passos requerits per les cartes (sobre aquelles que realment van arribar) va ser de sis. Així quedava demostrat que tothom als Estats Units podia estar unit a qualsevol altre per un petit nombre de sis passos intermedis. I aquests són els famosos “sis graus de separació”. Una altra de les conclusions sorprenents de l’estudi va ser que la majoria de les cartes que van arribar tenien en comú els tres últims intermediaris. Això demostra, a més, com convergeixen trajectòries socials que, en principi, creiem que són absolutament independents. També permet visualitzar l’estructura social com un entramat de connexions i, per extensió, com un graf o xarxa en què els nodes són les persones i els enllaços, en aquest cas, relacions de coneixença personal.
Enllaços recomanats
La versió traduïda al castellà de l’article original es pot trobar en la revista Araucaria (2003, núm. 10, pàg. 15):
http://www.institucional.us.es/araucaria/nro10/ideas10_2.pdf
El grau màxim de popularització va arribar precisament amb Internet i la facilitat d’accedir a grans bases de dades, una de les quals anomenadaInternet Movie Database<http://www.imdb.com/>. Actualment, conté més d’un milió i mig de pel∙lícules i gairebé dos milions d’actors i actrius. Un informàtic a la Universitat de Virgínia havia estat calculant la cadena mínima de pel∙lícules entre qualsevol parell d’actors. I es va adonar de l’estructura rica de la xarxa d’actors, de tal manera que gairebé el 90% dels actors estan connectats, inclòs en Kevin Bacon. Precisament, va ser aquest nom el que va donar lloc a l’anomenatOracle of Bacon. Si per curiositat entrem en aquest web actualitzat cada dues setmanes a partir de les dades de la IMDB, podem trobar el nombre de pel∙lícules entre qualsevol parell d’actors, i per a qualsevol parell que triem ens adonarem de com de petit és aquest món. I no sols els més coneguts; podem trobar, a més, a quina distància, en mitjana, es troba qualsevol actor de la resta de la base de dades. I els nombres són inesperadament, o potser ja no tant, petits. El nombre de pel∙lícules entre qualsevol parell d’actors es troba per sota de quatre.
Enllaços recomanats
Internet Movie DataBase:
http://www.imdb.com/
Enllaços recomanats
The Oracle of Bacon:
http://oracleofbacon.org/
Però altres comunitats també tenen les seves pròpies interpretacions de com de petit és el món professional. Els matemàtics utilitzen el que s’anomena nombre d’Erdös. Aquest matemàtic hongarès, el més prolífic de la història a l’hora d’escriure articles, va col∙laborar directament amb més de 500 científics. Aquests tenen l’honor de tenir unnombre d’Erdösigual a 1. Els coautors d’aquests tenen el nombre 2, i així successivament. I no cal dir que amb pocs nombres podem descriure completament tota la comunitat de matemàtics del món, llevat, potser, d’algun cas aïllat.
Enllaços recomanats
El nombre d’Erdös:
http://en.wikipedia.org/wiki/Erdös_number
Figura 1.1. Si l’Alícia col∙labora amb el Paul Erdös en un article i amb en Bernat en un altre, però en Bernat no col∙labora mai amb l’Erdös, aleshores en Bernat té un nombre d’Erdös 2, ja que és a dues passes d’Erdös.
Section0032.jpeg
Aquestes proves confirmen, doncs, la sospita que en la nostra societat tots ens trobem molt més a prop del que en principi sospitem. No solament els actors i els matemàtics, ja que elNew York Timesva proposar l’any 1995, en ple escàndol Lewinsky, a quina distància es trobava qualsevol nord-americà de la famosa becària de la Casa Blanca i, novament, el resultat va ser sorprenentment curt.
Però ara hem de fer una mirada més enllà de les relacions professionals i socials. Hi ha altres sistemes que responen també a aquesta arquitectura? A estructures creades per la natura? A estructures creades per l’ésser humà?
L’any 1998, Duncan Watts i Steven Strogatz publiquen un article aNatureque avui en dia tothom considera com el primer de la nova ciència de les xarxes complexes “Collective dynamics of ‘small-world’ networks”. En aquest article analitzen acuradament certes estructures: unes creades per la natura, com ara la xarxa neuronal d’un cuc, anomenatC. Elegans; d’altres creades per l’ésser humà, com la xarxa de distribució d’electricitat als Estats Units, i l’altra ja esmentada, creada per les relacions professionals, dels actors i actrius de cinema. I totes comparteixen els fets que hem comentat amb anterioritat, que la distància mitjana entre qualsevol parell de neurones, d’estacions de generació o distribució o qualsevol parell d’actors és molt més petita que l’esperada.
En aquest article no solament es posen de manifest aquestes característiques del que avui en dia anomenem un món petit, sinó que, a més, es proposa un model matemàtic que les explica, i de les quals tractarem amb més detall més endavant.
Enllaços recomanats
L’article pioner de Watts i Strogatz: doi:10.1038/30918
Així, doncs, a partir d’aquestes proves i del mateix model, i d’altres relacionades, neix un nou camp de recerca, el de les xarxes complexes. Un món nou que descriu estructures a mig camí entre la regularitat i l’aleatorietat, que trenca la simplicitat topològica que tant agrada als matemàtics, i que troba aquesta simplicitat o bé en la regularitat perfecta o en l’aleatorietat total. I allunyat dels dos extrems simples, enmig, en un terreny inexplorat, ens trobem la complexitat estructural o topològica.
I com a demostració immediata i visual d’aquests fets podeu veure el vídeo anomenatConnected-How Kevin Bacon cured cancer. En primer lloc, en aquest documental podem veure com es produiria un experiment semblant al de Milgram en el moment actual. Quina trajectòria seguiria un paquet postal enviat des de qualsevol lloc del món. I seguint amb el documental, com el descobriment inicial de l’entramat de connexions en una xarxa d’actors en què Kevin Bacon tenia un paper important ens ha portat amb el temps a aplicacions en molts camp de recerca, des de les telecomunicacions a l’economia, des de la producció d’energia a la distribució de comerç mundial, i en una d’aquestes aplicacions ens trobem amb la medicina. Com es poden conèixer les interaccions entre proteïnes, els efectes en xarxes genètiques d’expressió han permès començar a dissenyar fàrmacs nous que precisament poden atacar estructures patològiques associades, per exemple, al desenvolupament de cèl∙lules cancerígenes, en els seus punts més febles, i ens poden ajudar en un futur no gaire llunyà a lluitar contra el càncer.
Vídeo recomanat
Connected - How Kevin Bacon cured cancer.
Produït per l’ABC, cadena australiana.

1.2.Un món complex

Aquestes estructures que hem descrit en la secció anterior, que anomenemestructures complexesper distingir-les de la simplicitat de la regularitat o del caos organitzatiu més complet, són només una de les mostres que en el nostre entorn abunden les “complexitats”. No solament pel tipus d’estructura, sinó també pel tipus de comportament.
Vídeo recomanat
Synchronized fireflies
http://youtu.be/a-Vy7NZTGos
Actualment, entenem persistemes complexosels que presenten comportaments emergents en sistemes amb un gran nombre de components o parts. La particularitat dels comportaments col∙lectius que apareixen és que no són fàcilment predictibles a partir de les característiques individuals. Cada unitat individual pot presentar una evolució particular, per exemple, una cuca de llum que emet polsos de llum amb una freqüència determinada. Globalment, podem dir que a les ribes dels rius del Sud-est asiàtic hi ha un fenomen en què al capvespre es pot observar com milers de cuques de llum emeten flaixos de manera sincronitzada. Aquest és un fenomen de comportament emergent, de sistema complex, en què el sistema global podem dir que està sincronitzat, mentre que pels sistemes individuals només podem dir que emeten polsos de llum. Per això diem que el comportament global no és una mera suma dels individuals, una miríada de polsos inconnexos, sinó un conjunt de polsos sincronitzats. Què o qui fa que aquests polsos siguin sincronitzats? La resposta és molt més senzilla del que sembla: són les mateixes cuques de llum que “veuen” els polsos de les seves veïnes i en funció d’això decideixen avançar o endarrerir l’emissió del seu pols. I després d’una estona “comunicant-se” de manera imperceptible entre elles és quan tenen capacitat per a mostrar aquest efecte global. Aquesta mena de comportaments els podem observar a la natura de moltes maneres, com ara el vol de les bandades d’estornells o els bancs de peixos, o fins i tot quan l’audiència d’un concert aplaudeix de manera totalment sincronitzada després de l’espectacle.
Però aquest no és l’únic tipus de comportament emergent que podem trobar a la natura o a la nostra societat. És molt més general del que sembla i apareixen a totes les escales. Les societats són formades per éssers humans, el cervell per neurones, les molècules d’ADN per àtoms, el temps atmosfèric per fluxos d’aire i agua, les estructures galàctiques a l’Univers...
Vídeo recomanat
TEDtalk, de Steven Strogatz, sobre sincronització (subtitulat en castellà).
http://www.ted.com/talks/steven_strogatz_on_sync.html
Aquests sistemes complexos els estudiem dins la ciència de la complexitat. Aquesta és una disciplina que va més enllà de la divisió tradicional de les disciplines i en pot afectar més d’una en una descripció a diferents nivells, com, per exemple, la psicologia i les ciències socials, quan intentem descriure un sistema social format per persones.
Però, com és fàcil d’imaginar, aquesta descripció qualitativa és lluny de poder ser formalitzada matemàticament, amb models senzills. Les dinàmiques individuals poden ser senzilles d’entendre (una cuca de llum es pot veure com un simple oscil∙lador), però sobretot és la interacció entre les parts que normalment es produeix d’una manera no trivial. I, addicionalment, encara ens falta tenir en compte que les interaccions es produeixen mitjançant patrons de connectivitat que no tenen res de trivials, com els descrits en la secció anterior, o que, lligats amb els exemples que hem vist aquí, anirien de la relació visual que s’estableix entre els animals (cuques, estornells o peixos); l’auditiva, entre l’audiència d’un concert, o familiars o d’amistat, entre els individus d’una societat.

1.3.Connexions

I aquest és justament el tipus de complexitat que ens comencem a trobar i del qual hem fet un petit esbós en la introducció. Hem de començar, doncs, descrivint la complexitat estructural o topològica inherent a molts dels sistemes naturals, tecnològics o socials que tenim al voltant. Hem de saber si aquestes connexions són fixes o varien amb el temps, si són totes iguals o si són les unes més fortes que les altres, si malgrat veure-les idèntiques localment resulta que el seu paper en l’entramat global és força diferent, i molts d’altres problemes relacionats amb la complexitat, o no-simplicitat, d’un món ple de connexions.
Veurem alguns exemples més endavant en què la xarxa no existeix en realitat, sinó que és una simple representació d’un sistema complex. Vegem un exemple concret difícil de classificar entre els diferents tipus de xarxa, però que al mateix temps és prou aclaridor d’aquesta interpretació visualitzadora de les xarxes.
1.3.1.Un problema d’escacs
En la figura que ve a continuació ens plantegem el problema d’intercanviar les posicions dels dos cavalls blancs i els dos cavalls negres. Per a resoldre’l no cal ser mestre d’escacs, però el problema no és senzill, i com s’indica en la figura calen quaranta moviments.
I ara us deveu preguntar què tenen a veure les xarxes amb un problema d’escacs. Doncs com hem dit abans, les xarxes a vegades no són més que una manera de representar situacions, relacions, problemes.... En aquest cas particular, el que ajuda molt a resoldre el problema és representar-lo com una xarxa, com es pot veure en la figura següent. Cada node és una casella i cada enllaç entre caselles és un possible moviment del cavall entre aquestes dues. Un cop la representem com una xarxa, visualment podem tenir una resposta evident del problema, perquè podem identificar perfectament els moviments en forma de camí al llarg d’una xarxa i evitar els solapaments en una mateixa posició.
Figura 1.2. Problema d’escacs: intercanvieu les posicions dels dos cavalls blancs i els dos cavalls negres (Ajut: la solució més curta té 40 moviments).
Section0033.jpeg
Figura 1.3. Problema d’escacs representat mitjançant una xarxa, en què els nodes són les caselles i els enllaços, els possibles moviments del cavall entre elles.
Section0034.jpeg

2.Xarxes pertot arreu

Així, doncs, ens trobem al nostre voltant o en l’estructura microscòpica dels organismes multitud d’exemples de sistemes interconnectats de tal manera que podem dir que formen una xarxa. La classificació d’aquests exemples és un punt arbitrari, ja que en podem trobar d’alternatius en la bibliografia existent, i fins i tot podríem dir que hi ha exemples de xarxes que podrien estar classificades en més d’un tipus. Malgrat aquests impediments, establirem una classificació temptativa.

2.1.Xarxes tecnològiques

En general, aquestes xarxes tecnològiques tenen un suport físic pel qual flueix alguna magnitud. Entre aquests casos tenim: Internet, com una xarxa d’ordinadors i encaminadors per on es transporten bits d’informació; les xarxes de telefonia, per les quals també es transmeten bits, en aquest cas corresponents a veu o dades per a les noves generacions de xarxes digitals; xarxes de distribució elèctrica, per les quals es transporta energia elèctrica, i, finalment, xarxes de transport en què el que es transporta són passatgers.
2.1.1.Internet
La xarxa d’Internet és avui en dia el que podríem dir la mare de totes les xarxes, la que ha permès que en els darrers 25 anys el món hagi canviat de manera tan radical. Com han canviat les nostres comunicacions, les nostres relacions i les nostres aficions. Però hem de distingir entre Internet, la xarxa física de suport, i les xarxes virtuals que han anat proliferant al seu damunt (començant pel mateix World Wide Web, de què tractarem en una de les properes seccions).
Internet no és, en principi, res més que un conjunt d’ordinadors connectats per cables (encara que recentment aquests cables van desapareixent i donen lloc a multitud de connexions sens fils i en el futur ens portaran al concepte de l’Internet everywhere), en què el que s’intercanvien són paquets d’informació. Qualsevol missatge és descompost en paquets que s’envien de manera separada per la xarxa física (poden seguir camins diferents). La manera de trobar la destinació és gràcies a la identificació (l’adreça IP,Internet protocol address) de cada ordinador o dispositiu. Justament, el creixement exponencial del nombre de dispositius connectats a Internet ha fet que el nombre d’aquestes possibles adreces es col∙lapsi i sigui necessari adoptar nous protocols de comunicació; per això, ara comencem a parlar d’Internet 2.
Aquesta que hem descrit no és res més que l’estructura que com a usuaris veiem d’Internet. Però aquesta és formada, internament, d’una manera bastant més complexa, perquè, com podem entendre, enviar paquets a destinacions diverses requereix equips intermedis que disposin d’informació, encara que parcial, de l’estructura de la xarxa. Aquests són els encaminadors, que tenen taules d’encaminament dinàmic. A part dels encaminadors, ens trobem els proveïdors de servei, que corresponen a les companyies a escala local; després, les xarxes acadèmiques o de recerca a escala nacional, i, finalment, el que podríem anomenar la columna vertebral de banda molt ampla que intercomunica totes les possibles subxarxes.
Una de les característiques més importants i alhora més sorprenents d’Internet és el caràcter autoorganitzat i espontani de la seva estructura. No hi ha cap autoritat central que dicti la seva manera de procedir i, malgrat tot, s’ha convertit en l’eina més imprescindible avui en dia per a la majoria de nosaltres.
Figura 1.4. Aquesta és una representació d’Internet pel que fa a sistemes autònoms, en què es pot veure l’estructura nacional exterior i l’estructura global més interior.
Section0035.jpeg
2.1.2.Xarxa de telefonia
En aquest apartat considerem xarxes de telefonia com les xarxes de cablejat tradicional per les quals es propaguen les nostres converses de veu. Potser ha estat el gran paradigma de les xarxes en el segle XX, poc després de la invenció de la telefonia, fins al començament del segle XXI, quan podríem dir que la telefonia, com a comunicacions de veu, se solapa amb la de dades (Internet). Així, el naixement d’Internet com a gran mitjà de comunicació de masses (a mitjan dècada de 1990) està associat a mòdems de no gaires kilobytes, mentre que en l’actualitat hem passat a encaminadors domèstics amb Internet de banda ampla a alguns megabytes. Però el que ja no podien sospitar les companyies operadores de telefonia fixa és que, amb el temps, moltes de les trucades de veu es fessin utilitzant precisament protocols d’Internet, com ara elsvoice-IP, dels quals potser el més conegut és el programa Skype, adquirit recentment per Microsoft.
Una de les diferències pràctiques entre les xarxes de telefonia i Internet és que mentre que a la segona tot és públic, els protocols, l’emplaçament dels encaminadors, els enllaços físics i lògics, en la primera no, i, en particular al nostre país, hem vist les dificultats dels nous operadors de telefonia per tal de poder accedir a telèfons residencials sense el permís de la companyia que ostentava el monopoli fins no fa gaires anys. Però això és general a gairebé tots els països i així podem dir que no s’han estudiat en absolut les xarxes de telefonia perquè simplement no es disposa de dades.
2.1.3.Xarxa de distribució elèctrica (power grid)
En aquest cas, a diferència de l’anterior, ens trobem amb una xarxa de distribució d’energia elèctrica de la qual sí que es disposa de dades. Són un tipus de xarxes fortament condicionades per l’entorn geogràfic i també demogràfic i social.
Ha estat una de les xarxes més estudiades, ja des dels primers treballs de Watts i Strogatz. En aquest cas, es considera la xarxa formada per les línies d’alt voltatge que connecten plantes generadores i estacions d’intercanvi, sense arribar al detall de l’usuari final.
En l’actualitat, hi ha un interès renovat per aquestes xarxes, a causa de les noves fonts de generació d’energia que s’estan implantant de manera general (eòlica, solar...), cosa que dóna lloc al que s’està anomenant l’smart grid, ja que tant la generació com el consum (pensem, per exemple, en els cotxes elèctrics) formen xarxes que cada cop arriben a més punts geogràfics. A més, en aquest cas no n’hi prou de conèixer la topologia, sinó que és molt important estudiar les propietats dinàmiques de la distribució d’energia, que entenem com una dinàmica complexa que té lloc damunt una topologia complexa.
Figura 1.5. Xarxa de distribució d’electricitat a l’Europa occidental
Section0036.jpeg
2.1.4.Xarxes de transport
Les xarxes de transport les hem d’entendre a totes les escales, tant a escala metropolitana (la xarxa del metro de Barcelona que mostrem en la figura), com a escala nacional (la xarxa ferroviària o de carreteres), fins a escala mundial (les xarxes de transport aeri o de mercaderies per mar, per exemple).
Òbviament, també és molt important conèixer aquestes xarxes perquè en depèn molt bona part de la nostra economia, de la nostra societat i, fins i tot, de la nostra salut, i si no pensem com s’han propagat els dos casos més importants d’epidèmies a escala mundial, la de la grip aviària i la de la grip A, que ho han fet tan ràpidament perquè les comunicacions entre continents són extremament ràpides gràcies al transport aeri.
Figura 1.6. Xarxa de metro de Barcelona
mapa-metro-barcelonaOK_fmt.jpeg

2.2.Xarxes biològiques

A diferència de les xarxes tecnològiques, les xarxes biològiques majoritàriament són xarxes relacionals, en les quals no hi ha un enllaç físic real entre elements, sinó que el que establim són patrons d’interacció entre elements biològics, com poden ser relacions entre elements que participen en una mateixa reacció química a la cèl∙lula o quines espècies es mengen quines altres en una xarxa ecològica. A continuació, considerarem alguns d’aquests exemples.
2.2.1.Xarxes bioquímiques
En general, podem dir que aquestes xarxes representen mecanismes que tenen lloc dins la cèl∙lula. Hi distingim:

  • Xarxes metabòliques: en aquest cas, la xarxa correspon als components químics que participen en una reacció, i es relaciona cada reacció amb un dels processos que tenen lloc dins la cèl∙lula.

  • Xarxes d’interacció entre proteïnes: aquest cas correspon a un grau de complexitat superior, ja que les proteïnes no sols interaccionen químicament entre elles, sinó que també ho fan físicament, ja que poden modificar la seva estructura de plegament.

  • Xarxes de regulació genètica: finalment, en aquest cas es consideren lesinteraccions entre diferents parts que formen l’estructura de l’ADN, és a dir, els gens. Identificant aquests gens el que es pretén amb aquestes xarxes és entendre com l’activació o inhibició d’algun (o alguns) d’ells afecta les consegüents activació o inhibició d’altres.

Figura 1.7. Exemples dels tres tipus de xarxes bioquímiques (metabòlica, d’interacció entre proteïnes i de regulació genètica)
Section0037.jpeg
2.2.2.Xarxes neuronals
Aquestes són les xarxes que formen les neurones en els sistemes cerebrals dels animals. Que en aquest sistema se l’anomenicervello no ja és una altra història, perquè normalment es parla decervellen animals vertebrats.
Les neurones són les unitats bàsiques per a processar la informació. Aquesta informació arriba a la part central de la neurona –el soma–, és processada i produeix una sèrie de senyals que es propaguen pels axons per a arribar com a input a altres neurones. Aquesta connectivitat és la que forma la xarxa.
Per a una xarxa senzilla, com la del cucC. Elegansque mostrem en la figura, el paper que tenen les diferents neurones és molt clar, i en tenim moltes dades. En aquesta gràfica es representen amb colors diferents les que són dins els mateixos grups funcionals. Quan passem a animals superiors no és tan fàcil determinar aquests papers i aleshores les xarxes neuronals es passen a considerar d’una altra manera. Per exemple, com a resultat de mesures externes al cervell, es poden mesurar correlacions entre diferents zones corticals i això dóna lloc al que anomenaríemxarxes corticals, que ja no són xarxes entre neurones individuals sinó que connecten zones funcionals del cervell. Aquestes relacions de connectivitat s’estableixen analitzant les correlacions entre diferents zones del cervell quan l’individu està sotmès a diferents tipus d’estímuls.
Figura 1.8. Xarxa neuronal del C. Elegans
Section0038.jpeg
2.2.3.Xarxes ecològiques
En aquest apartat, en l’escala més gran, la que correspon a espècies animals, ens trobem amb els ecosistemes. Un ecosistema és un concepte més general quexarxai inclou multitud d’interaccions. Per tal de restringir-nos a les xarxes complexes que apareixen normalment en el món de l’ecologia ens fixem en les anomenadesxarxes tròfiques, de les quals tenim un exemple esquematitzat en la figura.
Una xarxa tròfica és una xarxa formada per les interaccions entre espècies, en què unes són l’aliment d’alguna de les altres. Aquesta relació tan senzilla de descriure ha donat lloc a un conjunt de xarxes molt conegudes i que han estat elaborades amb gran paciència pels ecòlegs de camp. El gran avantatge d’aquestes xarxes és que en ecosistemes ben determinats, com, per exemple, un llac, no hi ha gairebé interaccions amb els sistemes exteriors i es poden anar recollint dades amb molta estabilitat temporal.
D’altra banda, aquestes xarxes ens indiquen el grau de sensibilització dels mateixos ecosistemes. I és possible entendre per què la desaparició d’alguna espècie, pel motiu que sigui, pot donar lloc a una superpoblació de les seves preses i a problemes de subsistència dels seus depredadors. Però això seria una conclusió massa senzilla, ja que una de les coses que hem après de les xarxescomplexes és que la interconnectivitat comporta conseqüències que van més enllà dels simples efectes als nostres veïns. I quan diem que una espècie desapareix no tenim ni idea, en principi, dels possibles efectes devastadors que aquest fet pot tenir en tot l’ecosistema.
Figura 1.9. Exemple de xarxa tròfica, de qui es menja a qui en un ecosistema.
Section0001.jpeg

2.3.Xarxes socials

Quan parlem dexarxes socials, el primer que ens ve al cap és Facebook, sobretot gràcies a la pel∙lícula recent dirigida per David Fincher. Ens creiem, potser, que no som ningú en la nostra societat si no som a Facebook? Però aquesta enorme xarxa amb milers de milions d’usuaris ha desenvolupat certes propietats que fan que de vegades ens la mirem amb força recel. Però ara no discutirem sobre aquesta xarxa tan popular i tan particular, i deixarem per a la segona part d’aquest document la discussió detallada de les xarxes socials.
En un context general, podríem dir que justament les xarxes socials, que han estat tema de recerca en ciències socials durant dècades, mostren la gran evolució que ha sofert aquest camp en els darrers dotze anys. No és difícil imaginar com es feien les anàlisis relacionals fa trenta o quaranta anys, mitjançant qüestionaris. I, òbviament, som conscients de les limitacions que això comportava en termes de temps necessari per a fer-les, de recursos i de biaix, perquè el mateix qüestionari o qüestionant poden influir en les respostes. Què tenim en l’actualitat? Dades, moltes dades, i és tan fàcil accedir-hi que podem construir la nostra xarxa d’amics a Facebook (vegeu la segona part d’aquest document) o conèixer la xarxa que va donar lloc al fenomen dels indignats a tot l’Estat espanyol a partir del 15-M.
Enllaç recomanat
Anàlisi del moviment 15-M o dels indignats fet al BIFI, a partir de piulades geoposicionades.
http://15m.bifi.es/

2.4.Xarxes d’informació

Per acabar amb aquesta classificació parlem ara de xarxes en les quals el que flueix bàsicament és informació, entesa d’una manera bastant general i, fins i tot, d’una manera abstracta. I recordem que aquesta classificació no deixa de tenir un punt d’arbitrarietat, ja que algunes xarxes podrien ser classificades en més d’un dels apartats.
2.4.1.El World Wide Web
Aquesta teranyina d’amplària mundial és possiblement la xarxa que ens va obrir els ulls a Internet a mitjan dècada de 1990. L’arrel la trobem en el desenvolupament d’una sèrie de protocols, principalment per científics del CERN (Organització Europea per a la Recerca Nuclear, un dels principals laboratoris mundials de física d’altes energies) a Ginebra, per a la comunicació interna en el grup d’investigadors. Encara que en aquells temps hi havia idees similars entorn de la comunicació sobre Internet, l’èxit fulgurant del Web (i del protocol que fa servir, l’HTML) es va deure al fet que els creadors van decidir que el programari fos de lliure accés i ús. Aquesta universalització, i d’altres que han succeït posteriorment, és la que ha permès que trenta anys després del naixement d’Internet parlem comunament d’informació i programari d’accés lliure i obert.
El World Wide Web té una estructura que s’anomenadirigidaperquè els enllaços només funcionen en una direcció. Els enllaços (links) són els que ens porten d’una pàgina web a una altra. Es tracta, òbviament, d’una xarxa amb milions i milions de documents en què és difícil navegar, però justament aquesta és una de les característiques del Web: administrar la quantitat ingent d’informació i indexar-la perquè sigui útil. I aquí és on entren possiblement les eines amb més potencial de la Xarxa, com són els cercadors. I els grans negocis que s’han anat desenvolupant al seu voltant, com és el cas de Google.
2.4.2.Xarxes de cites, patents i legals
Aquestes són unes altres xarxes en què el que es propaga és la informació. En el cas de les xarxes de cites, són els articles científics els que se citen els uns als altres. Els articles són els nodes i les cites, els enllaços. Com en el cas del WWW, la xarxa també és dirigida. A més, en aquest cas, hi ha una restricció important que és la de la seqüenciació temporal, ja que hi ha clarament un efecte de la data de publicació, i això fa que quan parlem de xarxes aquesta no presenti cicles tancats.
Mirant en perspectiva, de fet, una de les primeres anàlisis de les xarxes de cites (feta per de Solla Price l’any 1965) descriu una distribució del nombre de cites dels articles que té una forma especial, que s’allunya de la gaussiana o normal tradicional, i que veurem en detall més endavant en aquest mateix document. Mentre que en aquest i altres treballs d’aquella època la recollida es feia eminentment a mà, ens trobem avui en dia amb grans repositoris, com ara les versions electròniques de les revistes de més importància, en què la recollida de dades es pot fer de manera automàtica i constitueix, així, una font important.
Aquest tipus de xarxes, juntament amb altres tipus de xarxes de coneixement científic basades en articles publicats, seran tractades en especial en la tercera part d’aquest document.
Molt semblants en estructura a les xarxes de cites, trobem les xarxes de patents, en què ara els nodes corresponen a patents i els enllaços a com els registres de les patents se citen les unes a les altres. Tenen la característica compartida que són dirigides i que no hi ha cicles tancats.
Finalment, dins d’aquesta categoria podríem incloure les xarxes de cites legals, que serien aquelles en què, per exemple, certes sentències promulgades per un jutge en poden citar d’altres o en què algunes lleis en citen textualment d’altres. En aquests casos també observaríem els efectes descrits anteriorment.

Enllaç recomanat
Alex Arenas; Albert Díaz-Guilera (2009). “Análisis y minería web. Identificación de comunidades analizando el uso del correo electrónico”. El Profesional de la Información (núm. 18).
http://www.elprofesionaldelainformacion.com/contenidos/2009/enero/04.html
Aquesta que descrivim aquí és òbviament un tipus de xarxa que transmet informació entre dos usuaris. Òbviament, considerant tots els servidors de correu d’Internet i tots els usuaris, això forma una xarxa gegantina i indesxifrable. El que es considera, en aquest cas, són xarxes de correu tancades entre usuaris, per exemple, dins una organització.
En podem trobar alguns exemples a la bibliografia, un dels quals és el que en el nostre grup de recerca vam fer sobre la xarxa de correu a la Universitat Rovira i Virgili. Podeu trobar detalls d’aquest treball en l’enllaç següent. En aquest cas, es van recollir tots els missatges intercanviats entre usuaris (anònims) durant els tres primers mesos de l’any 2002. El resultat el podeu veure en la figura que presentem a continuació.
Figura 1.10. Xarxa de correu de la Universitat Rovira i Virgili, recollida durant els tres primers mesos de l’any 2002. Cada node correspon a un usuari (anònim) i hi ha un enllaç si entre dos usuaris s’han intercanviat almenys un missatge durant aquest període. Les tonalitats de grisos corresponen al centre d’adscripció de l’usuari.
Section0002.jpeg
Aquesta recollida de dades ens aporta una informació molt valuosa sobre la mateixa organització, ja que permet establir els patrons de comunicació entre els diferents centres, per exemple. En la part del document en què tractarem d’estructures internes explicarem detalladament els resultats en aquesta xarxa de correu.
En la bibliografia trobem analitzats altres exemples de xarxes de correu. Una alternativa ha estat, per exemple, considerar un conjunt d’usuaris i creuar les dades en les seves llibretes d’adreces. Aquests encreuaments també formen una xarxa, però en aquest cas correspondria més a una xarxa social, de contactes més o menys intensos, que no pas a una xarxa d’informació.
2.4.3.Coautories
En aquest apartat parlem d’un tipus de xarxa bastant diferent de les anteriors, perquè novament és una xarxa que tant la podríem classificar aquí com en les xarxes socials, però entenem que té més a veure amb la informació intercanviada per científics que col∙laboren en un projecte comú que no pas en una xarxa social.
Ja des del principi es van analitzar xarxes de coautories en bases de dades científiques corresponents a diferents disciplines. Més endavant, descriurem aquests resultats, però el que podem dir a hores d’ara és que, independentment de la disciplina, els patrons de la xarxa són comuns.
Aquí presentem els resultats obtinguts en el nostre grup de recerca corresponents a una sèrie de congressos (FisEs) que van tenir lloc cada any i mig en la comunitat de físics estadístics a Espanya. Considerant cada edició del congrés, es van analitzar els conjunts de treballs presentats i es van establir enllaços entre autors si havien participat en la mateixa contribució. La xarxa que presentem és l’acumulada al llarg de totes les edicions.
Figura 1.11. Xarxa de coautoria. Xarxa acumulada al llarg de les diferents edicions del congrés de físics estadístics a Espanya (FisEs). Els nodes marcats corresponen als membres del comitè científic.
Section0003.jpeg
En aquesta xarxa podem veure que s’articula entorn de certes temàtiques (en aquest cas, la xarxa no és anònima ja que les dades són públiques) i també entorn de certs científics que han tingut un paper important en el desenvolupament de la disciplina a escala estatal.
2.4.4.Consells d’administració
Un dels exemples paradigmàtics que des del principi es va anar considerant en les xarxes, sobretot relacionades amb l’economia, és el de les xarxes que es creen considerant els consells d’administració de grans empreses i corporacions. En aquest cas, fem un primer plantejament prenent com a subjectes els membres dels consells d’administració i els considerem connectats si pertanyen al mateix consell. Sorprenentment, aquests consells tenen una gran força en l’economia nord-americana. I com a xarxa d’informació, aquesta la podem entendre com una mesura del que està passant i passarà en l’economia real.
2.4.5.Sistemes de recomanació
Un altre exemple de xarxa d’informació són les xarxes de recomanació. En aquest cas, la informació és valuosa tant per a l’usuari final com per a l’entitat que la genera. Aquestes xarxes es generen dinàmicament i els mateixos actors no en tenen consciència. Per què cada cop que comprem un llibre a Amazon.com ens diu que els usuaris que han comprat aquest llibre també han comprat aquests altres? Doncs simplement perquè es generen patrons de similitud entre usuaris i entre productes, i és justament aquesta similitud la que estableix les relacions entre els objectes recomanats i aquells a qui se’ls recomanen. Per a tenir una idea de la importància d’aquest tipus de xarxa, fa uns anys una companyia de distribució de DVD que es poden llogar en línia, que ja tenia un algorisme de recomanació per als seus usuaris, va obrir un concurs amb un premi d’1 milió de dòlars per a la persona que trobés el millor algorisme de recomanació de les seves pel∙lícules basant-se en les dades acumulades fins aquell moment. I en aquest concurs hi van participar equips de recerca de les millors universitats del món.

3.Què és una xarxa?

3.1.Nodes i enllaços

Fins ara hem vist alguns exemples del que anomenemxarxes complexes, que podem trobar fàcilment al nostre voltant, com ara les xarxes tecnològiques, o que simplement no són res més que una representació adient per a entendre una certa fenomenologia, com ara alguns exemples de xarxes biològiques.
Però, què tenen en comú totes aquestes xarxes? De la més gran a la més petita, hi ha dos elements imprescindibles:

  • Nodes: són els elements principals de les xarxes. Són les unitats bàsiques de la nostra representació, són els ordinadors d’Internet, les pàgines del WWW o els llibres que comprem a Amazon.com. Depenent de la disciplina, aquests nodes reben diferents noms, però nosaltres mantindrem el denodeal llarg del document.

  • Enllaços: són les relacions entre els nodes. Hem vist abans que aquests enllaços poden ser reals, sobre els quals flueix alguna magnitud física, o virtuals, i els interpretem com una relació entre dos nodes, com pot ser un enllaç entre dues pàgines al WWW. Normalment, però, mai no considerem que els nodes tenen autoenllaços ni que entre dos nodes hi ha més d’un enllaç.

Figura 1.12. Xarxa amb sis nodes i set enllaços. En aquest cas, els enllaços són idèntics i no impliquen direccionalitat.
Section0004.jpeg

3.2.Tipus de xarxes

L’exemple que hem posat anteriorment correspon al tipus més simple de xarxa i és el que anomenem unaxarxa binària, que vol dir que els enllaços entre nodes existeixen o no existeixen, no ens importa quantificar els enllaços ni saber-ne la direccionalitat. Això correspondria al cas, per exemple, d’una xarxa de carreteres sense entrar en detalls de la capacitat de la carretera o al fet que un usuari sigui en la llista d’adreces de correu d’un altre sense entrar en detalls de quants missatges s’han intercanviat.
Però, recentment, s’ha posat més èmfasi en les xarxes en què sí importa la direccionalitat i la intensitat dels enllaços. En els exemples anteriors, correspondria a quina seria la capacitat de la carretera entre dos punts o el nombre missatges enviats en una direcció o en l’altra (perquè aquesta magnitud no cal que sigui simètrica). Aquestes són les xarxes anomenadesxarxes pesades, si tenim en compte el pes o la intensitat, i dirigides, si tenim en compte la direccionalitat.
Figura 1.13. Exemples de xarxes no binàries. Esquerra: xarxa dirigida. Fixem-nos que en aquest cas particular, tot i que la xarxa sigui connexa, no es pot arribar al node 4. Dreta: xarxa pesada.
Section0005.jpeg
Veurem més endavant, en parlar de la caracterització de les xarxes complexes, que ha de ser diferent per a les xarxes binàries respecte de les xarxes dirigides o pesades. Per exemple, queda clar que si una xarxa és dirigida i pretenem descriure els camins possibles sobre una xarxa pot passar que malgrat formar una component connexa no es pugui arribar a tots els nodes, com passa en la figura amb el node 4. D’altra banda, les xarxes pesades també ens indiquen la diferència entre els tipus d’enllaços entre nodes, per exemple, quan quantifiquem el nombre de missatges de correu intercanviats entre usuaris ens indica amb quina facilitat pot arribar la informació que es propaga per la xarxa.
3.2.1.Xarxes bipartides
Dins dels tipus elementals de xarxes, introduirem unes que tenen una rellevància especial perquè són formades per dos tipus de nodes i que es poden reconvertir en xarxes ordinàries amb unes característiques especials.
Són les anomenadesxarxes bipartides, i s’anomenen així perquè són formades per dos tipus de nodes, com podem veure en la figura següent.
Figura 1.14. a) Exemple de xarxa bipartida formada per dos tipus de nodes. Per exemple, els nodes superiors podrien correspondre
a articles i els nodes inferiors, a autors. b) Xarxa ordinària corresponent a la imatge superior.
Section0006.jpeg
Un tipus de nodes (els etiquetats amb lletres de l’alfabet) corresponen al nodes originals i l’altre, als grups als quals pertanyen. Per a posar-ne un exemple aclaridor, els nodes originals poden ser autors i els grups poden correspondre a articles escrits per aquests autors, aleshores es dibuixa un enllaç entre els autors i l’article en el qual han participat. Això correspon a la part superior de la figura. Aquesta seria la xarxa bipartida amb els dos tipus de node. En canvi, en la part inferior de la figura representem el que s’anomenaprojecció de la xarxa bipartida, és a dir, una xarxa ordinària en què els enllaços estan establerts entre nodes que pertanyen al mateix grup; en el nostre cas particular, correspon, doncs, a una relació de coautoria entre autors d’articles. En aquest cas, tenim grups de nodes que estan completament connectats, són els que comparteixen com a mínim un article en comú. Aquests grups de nodes completament connectats s’anomenen en la bibliografia cliques.

3.3.Descripcions

Fins ara hem descrit les xarxes d’una manera totalment qualitativa. Però si en volem fer un tractament matemàtic o gràfic necessitem fer-ne una representació algebraica. Normalment, el que expressarem és l’existència o no d’enllaços entre nodes, com són aquests enllaços o les llistes que existeixen.
Aquestes representacions serien:

  1. Llista d’enllaços: aquesta és la que utilitzen la majoria de paquets de programari, com ara el que s’utilitzarà majoritàriament al llarg d’aquest curs, el GEPHI. Consisteix a fer una llista de tots els enllaços com a parells ordenats de nodes per a les xarxes no pesades. Si la xarxa és no dirigida no cal posar-hi els dos ordres, però si la xarxa és dirigida aleshores sí que cal especificar l’ordre. Per a una xarxa pesada s’escriu una tercera columna amb el pes de l’enllaç.

    Figura 1.15. Llista d’enllaços de les tres xarxes senzilles representades anteriorment. En el primer cas, cal especificar que la xarxa és undirected, ja que qualsevol enllaç es considera en les dues direccions. En el segon, cal dir directed perquè en aquest cas importa la direccionalitat. Finalment, en el tercer cas, hi ha una tercera columna que correspon al pes de cada enllaç.

    Section0007.jpeg

  2. Llista de veïns (edgelist): aquesta representació s’utilitza només per a les no pesades i fem una llista de veïns (siguin dirigits o no) per a cada node. Aquesta manera de considerar les dades és més eficient per a accedir a les posicions de memòria, sempre que s’utilitzin adreces dinàmiques (apuntadors).

    Figura 1.16. Llista de veïns per a les xarxes no pesades anteriors

    Section0009.jpeg

  3. Matriu d’adjacència: aquesta representació és molt útil en tractaments matemàtics, perquè expressa en forma de matriu les llistes anteriors i val també per a les xarxes pesades. En aquest cas, entenem un element de la matriu –i, j– com l’existència (i el pes) de l’enllaç entre el node i i el node j.

    Figura 1.17. Matrius d’adjacència per a les xarxes anteriors

    Section0008.jpeg

4.Caracterització dels nodes d’una xarxa

En aquest apartat, veurem com caracteritzar el paper dels nodes en la xarxa tant des d’una perspectiva local com global, en particular introduint el concepte de centralitat.

4.1.Grau

El grau d’un node és el nombre d’enllaços que el connecten. Normalment, es designa el grau amb la lletrak; així,kicorrespon al grau del nodei. Si tractem amb xarxes no dirigides, parlarem del grau sense cap adjectiu; en canvi, quan parlem de xarxes dirigides hem de distingir entre el grau entrant (incoming degree) i el grau sortint (outgoing degree).
La mesura del grau d’un node és important perquè ens dóna una primera indicació de la seva centralitat; és a dir, com més veïns tingui un node més central serà perquè afecta (o és afectat) més un nombre de nodes al seu voltant. Però aquesta mesura és el que diríem local, perquè ens fixem només en un simple veïnatge del node que considerem. Podem tenir un node, molt connectat, però que el nivell d’influència en la resta de la xarxa del qual sigui molt petit, ja que està “allunyat” de la part més important de la xarxa. Aquests fets són els que ens fan definir altres mesures de centralitat més globals.
En la figura que presentem a continuació tenim una xarxa amb un conjunt de nodes amb diferents nivells de centralitat.
Figura 1.18. Esquerra: xarxa amb setze nodes amb diferent nivell de “centralitat”. Dreta: taula amb centralitats local i global dels nodes. La local correspon al grau i la global, a la distància total entre un node i la resta de nodes de la xarxa.
PID_00215564_1.jpg
En la taula adjunta, trobem el grau de centralitat local que correspon a cada conjunt de nodes (i ens referim aconjuntsperquè són idèntics a tots els efectes). Podem veure, doncs, que els més centrals amb aquesta mesura seran A, B i C,mentre que la resta són poc centrals a causa del grau baix que tenen. Però queda molt clar en l’estructura de la xarxa que el paper del node B quan ens fixem en el conjunt de la xarxa ha de ser més central que no pas A i C, i el mateix podríem dir de G i M (poc centrals localment) respecte de A i C. En la figura 19 hem inclòs representacions de la mateixa xarxa marcant amb un codi de colors en funció dels diferents tipus de centralitat, en particular del grau.
Figura 1.19. Representació de la xarxa amb colors de nodes segons el grau de centralitat: grau, closeness, betweenness, eigenvector, page rank. Els grisos més clars corresponen a valors numèrics més baixos i els més foscos, a valors més alts.
Section0039.jpeg
Per a generalitzar aquest concepte decentralitatnecessitem definir, en primer lloc, el concepte decamí.

4.2.Camins (paths)

En una xarxa binària (sigui dirigida o no, i si ho és tenim en compte el sentit de l’enllaç), definim un camí entre dos nodes com qualsevol seqüència de nodes formada de tal manera que qualsevol parell de nodes consecutius en la seqüència estiguin units per un enllaç de la xarxa. Així, en la xarxa anterior un camí entre M i G seria M, B, G, però també ho seria M, B, L, B, G. I en la xarxa dirigida senzilla introduïda anteriorment entre els nodes 6 i 1 serien 6, 3, 1 o 6, 3, 2, 1, per exemple.
Veiem, doncs, que el concepte decamíés força general i que pot incloure nodes que es creuen més d’una vegada o enllaços també que es travessen més d’una vegada. Des d’un punt de vista pràctic, però, només són interessants els camins que anomenemautoexcloents, que serien els que no repeteixen nodes ni enllaços.
GEPHI
Executem totes les funcions estadístiques. Anem a representació i triem que representi mitjançant colors cadascuna de les magnituds. Com que podem tenir també un format Taula podem tenir els valors de cada mesura a cada node.

4.3.Longitud

Un cop definits els camins sobre una xarxa el concepte que apareix de manera immediata és el delongitud d’un camí, que equival al nombre d’enllaços que travessa un camí. Així, els camins abans esmentats entre 6 i 1 serien de longitud 2 i 3, respectivament.

4.4.Distància entre nodes

Però, tal com ens podem imaginar, no tots els camins (infinits) que es poden definir en una xarxa són igual d’importants. Hi ha un conjunt particular de camins que són els que s’anomenencamins mínims, que són els que corresponen a la longitud mínima. Així, podem definir la distància entre nodes com la longitud del camí mínim que els ajunta, i així generalitzar el concepte deproximitati amb aquest el decentralitat. En el cas particular que estem considerant podem veure quina és la distància total d’un node a la resta i és el que en la taula hem descrit com a centralitat global, en què podem veure que efectivament el node més central és el B perquè es troba a menys distància (33) de la resta de nodes. Aquesta distància ens permet fer una primera definició decentralitat global.

4.5.Closeness centrality

Aquesta magnitud, com el seu nom indica, es refereix a la centralitat per proximitat, que normalment es dóna de manera normalitzada com la distància mitjana del node corresponent a la resta dels nodes. Per al cas del node B, aleshores la sevacloseness centralityés de 2,2, mentre que la dels nodes més allunyats val 3,8. En el segon panell de la figura 19 presentem novament la xarxa ordenant el color dels nodes segons el valor numèric de lacloseness centrality.

4.6.Betweenness centrality

Laclosenessno és l’única mesura de centralitat global disponible. Relacionada també amb els camins mínims ens trobem amb labetweenness centralitydefinida com la centralitat en termes del nombre de camins mínims entre qualsevol parell de nodes de la xarxa que passen per un node determinat.
A diferència de la closeness, per la qual un valor baix indica un alt grau de centralitat global, perquè indica que és a prop de la resta, labetweennesselevada indica un alt grau de centralitat. Vegem-ho amb detall. En el fons els camins mínims entre parells de nodes indiquen quin és el flux d’informació en la xarxa quan pensem en algun tipus de senyal que es propaga al llarg d’aquests camins. Aleshores, els nodes que es troben al llarg d’aquests camins són els que reben informació sobre aquest senyal propagat. Per tant, com més camins mínims passin per un node, més informació rebrà de la resta de la xarxa.
En el tercer panell de la figura 19 presentem novament la xarxa ordenant el color dels nodes pel valor numèric de labetweenness centrality.

4.7.Eigenvector centrality

Aquesta és una mesura generalitzada de centralitat associada al grau, ja que considera no solament el nombre de veïns que té un node, sinó quina és la importància relativa dels veïns, de manera autoconsistent. Des d’un punt de vista matemàtic, equival a resoldre un sistema d’equacions algebràiques lineals, de tal manera que la centralitat d’un node és proporcional a la suma de les centralitats dels seus veïns.
Sense entrar en detalls matemàtics (es pot calcular mitjançant GEPHI), la seva importància la podem veure en les xarxes socials, ja que un individu en una xarxa social pot ser important per la seva mesura, és a dir, per a conèixer molta gent, encara que aquesta gent no sigui tan important en ella mateixa, o per a conèixer poca gent però que sigui força important.
En el quart panell de la figura 19 presentem novament la xarxa ordenant el color dels nodes pel valor numèric de l’eigenvector centrality.

4.8.Page rank

Si en el decurs dels darrers anys una companyia en el món d’Internet ha creat l’admiració de tothom aquesta és, sens dubte, Google. Encara que avui en dia els seus productes es troben en qualsevol dels vessants de la moderna economia en línia (acabant pel recent Google+), el producte estrella de la companyia ha estat i és el seu cercador. I el seu cercador funciona amb una recepta que es considera tan secreta com la de la Coca-Cola, encara que està basada en una mesura de centralitat semblant a les anteriors. Bé, doncs, aquesta mesura de centralitat és la que s’anomenaGoogle page ranko simplementpage rank.
En el fons, quan fem una cerca a Google el que ens torna el cercador és una llista ordenada d’adreces de pàgines web que contenen la combinació requerida. I aquesta ordenació es fa mitjançant elpage rankde la pàgina, que ens n’indica la popularitat.
Però com es mesura elpage rankd’una pàgina? Simplement, considerem com si el web fos un sistema en què tenim un navegador (surfer) que es mou de manera aleatòria per la xarxa entre nodes que estan connectats (compte amb la direccionalitat dels enllaços ohiperlinksdel web). Aleshores, la popularitat de la pàgina és simplement proporcional al nombre de vegades que el surfer hi passa en els camins aleatoris. Un dels problemes, però, que aquest caminant es troba si una xarxa és dirigida, com ara el cas del Web, és que no hi ha manera de sortir d’algunes pàgines que no ens porten a cap lloc. La manera de resoldre-ho és considerar que el caminant té una probabilitatp(presa normalment com a 0,15) de recomençar el procés d’un altre node triat de manera absolutament aleatòria. Aquesta magnitud es pot expressar de manera matemàtica com a
Section0030.jpeg
En aquesta expressió veiem que el valor delpage ranka cada pàgina depèn dels valors als seus veïns. Igual que l’eigenvector centralityaixò s’ha de resoldre de manera iterativa numèricament, però això no és cap problema greu perquè fins i tot per a xarxes tan grans com el WWW el problema computacional convergeix molt ràpidament.
En el cinquè panell de la figura 19 presentem novament la xarxa ordenant el color dels nodes pel valor numèric delpage rank, utilitzant els càlculs fets amb GEPHI.

4.9.Clusteringd’un node

En aquest apartat introduïm una mesura que no té res a veure amb la distància ni tampoc amb la centralitat, però que té una gran rellevància de cara a les xarxes socials. És el que s’anomenaclustering, que per a un node correspon al fet que els veïns d’un node siguin veïns entre ells. Des d’una perspectiva social, per exemple en una xarxa d’amistats, vol dir que és molt probable que els meus amics també siguin amics entre ells. Des d’una perspectiva més matemàtica, elclusteringté a veure amb el nombre de triangles que es formen en una xarxa. En el cas de la xarxa que hem considerat, elclusteringde tots els nodes és zero, justament perquè no hi ha triangles. De totes maneres, aquest concepte serà estudiat amb més detall en la segona part d’aquest document.
Encara que sigui per a entendre de manera intuïtiva el que significa elclusteringconsiderem una xarxa molt senzilla, formada només per quatre nodes (ABCD) amb enllaços AB, BC, CD, AD. En la figura podem veure clarament que només hi ha un triangle.
Figura 1.20. Esquerra: xarxa molt senzilla per a veure un exemple de com calcular la clusterització. Dreta: valors de la clusterització per a cada node.
Section0031.jpeg
Aleshores, veiem que l’existència d’aquest triangle produeix els valors de la clusterització als nodes indicats a la dreta de la figura. El node B té només dos veïns (A i C) que estan connectats entre ells; per tant, hi ha un triangle en què només n’hi podria haver un, així que la clusterització de B (i també la de C) és igual a 1. En canvi, D no participa de cap triangle però només té un veí; en aquest cas, encara que sigui una indeterminació, s’estableix que la clusterització és 0. Finalment, el node A té tres possibles combinacions de parells de veïns (BC, BD i CD) perquè tots ells són veïns de A. De totes aquestes tres combinacions només en un cas (BC) estan connectats entre ells, cosa que ens dóna una possibilitat sobre tres, així que la clusterització del node A serà d’1/3.

5.L’estructura de les xarxes

5.1.Grandària d’una xarxa

La mesura que hem estat definint en els paràgrafs anteriors es refereixen a caracterització dels nodes individuals, és a dir, que en el fons el que ens interessa és esbrinar quin és el paper de cada node. En l’apartat que obrim ara i en altres de posteriors el que mirarem és la caracterització global de la xarxa.
En primer lloc, ens fixarem en les distàncies. Si abans hem definit la distància a altres nodes com la caracterització del node, ara utilitzarem la distància entre nodes de manera estadística per a caracteritzar la xarxa. Així, definim:

  1. Distància mitjana: aquesta mesura és simplement la distància mitjana entre tots els parells de distàncies entre nodes. Per al cas de la xarxa que estem considerant aquesta és de 3,29.

  2. Diàmetre: aquesta mesura ens planteja l’analogia amb un cercle i, com que el diàmetre d’un cercle correspon a la distància màxima entre dos dels seus punts, en el cas de la xarxa també es defineix com la distància màxima entre dos nodes. La xarxa que hem estudiat té un diàmetre de 6.

    GEPHI
    Executant l’opció “Network diameter”.

  3. Radi: aquest correspon a la mesura de la distància entre el node més central i el més exterior, que en el nostre cas particular és de 3.

5.2.Clusteringde la xarxa

Així com hem introduït una distància com a resultat mitjà dels valors individuals dels nodes, també es pot introduir un valor mitjà per a l’altra magnitud, que és la clusterització. De fet, hi ha dues possibles interpretacions del que hauria de ser el paràmetre declusteringde la xarxa:

  1. Clustering mitjana: en aquest cas, es defineix la clusterització simplement com la mitjana dels valors en els nodes individuals.

  2. Clustering global: per a distingir-la de l’anterior, es pot definir també l’efecte global directament, sense fer mitjanes. Així, el que miraríem és el nombre total de triangles en la xarxa respecte al nombre total de triangles que hi podria haver, tenint en compte els enllaços existents.

Val a dir que, en els dos casos, elclusteringglobal de la xarxa que estem analitzant és zero perquè no hi ha triangles. En canvi, per a la xarxa dibuixada en la figura 20, aquesta clusterització mitjana és 0,583.
GEPHI
Amb referència a la clusterització, ens calcula els valors individuals i la clusterització de la xarxa està calculada com la mitjana sobre tots els nodes.

5.3.Components

En la descripció que hem seguit fins aquest moment ens hem fixat en dues escales d’una xarxa que podríem anomenarextremes.Hem mirat quin és el paper de cada node (sia de manera local, com ara mesurant-ne el grau o elclustering, sia de manera global, mesurant les diferents caracteritzacions de centralitat) o quines són les característiques de la xarxa en la seva escala total, com ara quina és la seva grandària o quin és el seu coeficient declusteringmitjà.
Però en aquests darrers anys hem comprovat que les xarxes complexes tenen estructures a totes les escales que són molt importants, primer perquè ens ajuden en la seva caracterització i segona perquè aquestes estructures són importants per la seva robustesa, la seva flexibilitat o pels efectes sobre la dinàmica que comporten.
Pel seu ordre de més petit a més gran, aquestes estructures que descriurem aquí són:motifs, cliques, cores, i comunitats o mòduls.

5.4.Motifs

Quan hem començat a parlar de les xarxes hem dit que són nodes connectats per enllaços. I a partir d’aquesta propietat hem desenvolupat tota una sèrie de mesures; en particular, el grau d’un node que equival al nombre d’enllaços que té. En el fons, podem reinterpretar una xarxa com una col∙lecció d’“estrelles” amb un nombre de braços igual que el grau de cada node, en què les estrelles estan unides entre elles.
Aquesta descripció anterior seria en termes de l’estructura local al voltant de cada node, però aquest concepte es pot generalitzar. Si ens fixem en qualsevol parell de nodes, ens adonem que estan connectats (direccionalment si la xarxa és dirigida) o no, és a dir, només hi ha dues possibilitats si no és dirigida (existència o no de l’enllaç) i quatre si és dirigida (existència o no de cada enllaç dirigit). Per tant, aquesta seria l’estructura en el segon nivell a la xarxa.
I aquest concepte es pot generalitzar a qualsevol nombre de nodes, encara que fins ara el que més èxit ha tingut és el dels grups de tres nodes, que presentem en la figura següent.
Figura 1.21. Tots els possibles motifs de tres nodes
Section0011.jpeg
En aquesta figura podem veure totes les possibles combinacions de grafs de tres nodes, tenint en compte la direccionalitat de l’enllaç. Aleshores, qualsevol conjunt de tres nodes de la xarxa es pot identificar amb un d’aquestsmotifs. Fixem-nos en la xarxa dirigida de l’esquerra de la figura 13. Com que tenim sis nodes, el nombre de triangles que podem formar serà el nombre de combinacions de sis elements agafats de tres en tres, és a dir, vint. D’aquests vint possibles triangles no tots tenen un mínim de dos enllaços perquè puguem dir que formen un triangle; per exemple, els nodes 1, 2 i 6 no el formen. Dels que sí que en formen un, per exemple, tenim els nodes 1, 2 i 3 que formen unmotif, segons la figura 21, del tipus 5; els nodes 1, 2 i 4, del tipus 2, i aixísuccessivament (tots enumerats a la dreta). Resumint: el tipus demotifque observem seria un del tipus 2, 4, 5, 7, 8 i 13, mentre que el tipus 3 ens apareix tres vegades.
De fet, el que importa és aquesta estadística demotifs, saber quantes vegades apareix cadascun. I es va veure que en moltes xarxes reals aquestsmotifsapareixen més sovint del que s’esperaria.
Aquesta definició es podria generalitzar a qualsevol nombre, però és fàcil adonar-se que el nombre demotifscreix molt de pressa amb el nombre de nodes. Per exemple, en el cas de sis nodes és ja de centenars, cosa que fa que sigui totalment impracticable.
Motifs
Llista de triangles i motif:
1, 2, 3: 5
1, 2, 4: 2
1, 2, 5: 7
1, 3, 5: 12
1, 3, 6: 3
2, 3, 4: 4
2, 3, 5: 3
2, 3, 6: 3
3, 5, 6: 8

5.5.Cliques

Aquest és un nou tipus d’estructura a l’escala més petita, que d’alguna manera complementa l’anterior. En aquest cas es parla dek-clique, en general, com un subgraf deknodes completament connectat. En particular, els triangles, que analitzem en el context de la clusterització, són3-cliques. De fet, des d’un punt de vista pràctic, la clusterització és un nombre baix que indica que el nombre de triangles en una xarxa és relativament baix. I si consideremcliquesd’ordre superior, la probabilitat de trobar-los encara és més baixa.

5.6.Comunitats

A una escala superior, el que s’anomena normalment lamesoescala, ens trobem amb estructures que tenen una interpretació fàcil dins de cada disciplina.
Per exemple, en el camp de les ciències de la vida (en què s’anomenenmòdulsogrups funcionals) o en les ciències socials (en què s’anomenen comunitats).
Les estructures anteriors són més importants des d’un punt de vista més matemàtic o formal.
Les comunitats (aquest serà el nom que adoptarem en la resta d’aquest text) tenen un paper important dins la mateixa estructura general de la xarxa perquè en el fons estan associades al mateix procés ordenat de creixement de la xarxa (estudiarem més endavant alguns models de creixement).
En principi, una comunitat es pot definir com un subconjunt de nodes que estan més densament relacionats internament, en comparació de la resta de la xarxa. Però això és una definició molt simple que no pot assegurar la identificació correcta dels grups que formen la xarxa complexa.
El problema de detecció de comunitats és força complicat i ha estat objecte de discussió en diverses disciplines. Es tractaria, bàsicament, d’identificar una partició en què els nodes estiguin agrupats seguint criteris de connectivitat interna. És a dir, atesa una xarxa, com es particiona (proposa una partició) de manera que s’optimitzi una magnitud determinada. En principi, no tenim ni idea de quantes comunitats conté la millor partició i, fins i tot, ens podem trobar organitzacions jerarquitzades o amb solapaments. Encara que en una primera aproximació ens podem oblidar d’aquests efectes.
En els darrers anys (sempre tenint en compte que quan parlem d’una disciplina tan jove, vol dir en els darrers cinc anys), hi ha hagut força intents de fer front al problema computacional d’identificar les comunitats en una xarxa complexa. Aquests mètodes varien molt en termes d’enfocament i aplicació, i això els fa difícil de comparar entre ells. De totes maneres, els lectors interessats en aquestes tècniques (comparar-ne la fiabilitat i el cost computacional) poden trobar referències bibliogràfiques en la bibliografia recent.
La identificació de les comunitats no és simplement un problema qualitatiu, en realitat, la comparació entre els diferents algoritmes es fa en termes d’una quantitat que mesura com de bona és una partició determinada. Com que les comunitats de vegades no estan perfectament definides amb una frontera de separació clara entre elles, diferents algoritmes poden donar lloc a particions una mica diferents. Així, una mesura que quantifica aquesta exactitud en la partició és molt útil. En l’actualitat, la mesura més comunament acceptada és la que s’anomenamodularitat. Es basa en la idea intuïtiva que les xarxes aleatòries no mostren estructura de comunitats.
Imaginem-nos que tenim una xarxa arbitrària i una partició arbitrària de la xarxa en un nombre de comunitatsNC. Aleshores, és possible definir una matriu de dimensions
Equacio_1_fmt.jpeg
en què els elementseijrepresenten la fracció del total d’enllaços a partir d’un node a la partició i acaba en un node de particiój. Llavors, la suma de qualsevol fila (o columna) dei,ai= ∑jeij correspon a la fracció d’enllaços connectats ai.
Si la xarxa no presenta estructura de comunitat, o si les particions s’assignen sense tenir-ne en compte l’estructura subjacent, es pot estimar el valor esperat de la fracció d’enllaços dins de les particions. És simplement la probabilitat que un enllaç comenci en un node dei, ai, multiplicat per la fracció d’enllaços que acaben en un nodei,ai. Així, el nombre esperat dels vincles intracomunitat és simplementaiai. D’altra banda, sabem que la fracció real dels enllaços exclusivament dins d’una partició éseii. Així, els podem comparar els dos directament i sumar sobre totes les particions en la xarxa:
Equacio_3_fmt.jpeg
Aquesta és la mesura coneguda com lamodularitat,que per a una partició molt bona, i tenint en compte que la xarxa sigui clarament modular, s’acosta a 1. És a dir, que el valor de la modularitat depèn tant de la xarxa com de la partició que estiguem considerant.
Considerem ara novament la xarxa de la figura 18, que la tenim carregada en el programari GEPHI.
Figura 1.22. Partició en comunitats de la xarxa
Section0012.jpeg
GEPHI
Hem d’executar l’estadística modularitat i ens presenta la millor partició. A l’hora de representar-la, triem modularity class i en diferents colors podem veure les comunitats.
Utilitzant els diferents algorismes el que intentem és maximitzar la funció modularitat. En la figura podem veure una partició que té tot el sentit, però podem pensar en particions molt semblants. Ens podem preguntar per què el node G és en la comunitat de baix i no en la intermèdia? O per què el node M és en la intermèdia en lloc de la superior? La resposta a aquestes dues preguntes és molt senzilla, perquè en ambdós casos la modularitat és lleugerament més gran. Però, en canvi, sí que podríem fer els dos canvis alhora, i ens quedaria una distribució equivalent amb exactament el mateix valor de la modularitat, i per tant seria igualment bona.
Parlant de particions, de vegades, no solament estem interessats en la millor, sinó en l’organització jeràrquica de la xarxa en comunitats niades. A continuació, veurem un exemple pràctic d’aquesta mena de particions.
Un dels primers mètodes de detecció de comunitats, proposat per Girvan i Newman, consisteix a dividir la xarxa tallant els enllaços amb els valors més alts de labetweenness, justament perquè aquests enllaços són entre zones ben connectades internament. En aquest cas, aquest procediment es pot repetir fins al nivell dels nodes individuals i dóna lloc, llavors, a una jerarquia de les comunitats niades. Com es pot veure en la figura que presentem a continuació.
Figura 1.23. Identificació de comunitats.
Section0013.jpeg
a) Una xarxa amb dues comunitats perfectament identificables. L’enllaç BE és el que divideix les dues comunitats, i és el que té una betweenness més gran perquè per anar d’una comunitat a una altra cal passar per aquest enllaç. Per tant, aquest serà el primer enllaç que trencarem. b) Arbre binari que representa la divisió en comunitats. La comunitat global 1 s’ha dividit en dues comunitats (2 i 3). Encara que el procés es fa de manera iterativa, els nodes després de la primera subdivisió hi tenen un paper similar; només el node E té un paper més central en la comunitat 3, i per aquest motiu apareix al final de la ramificació.
L’aplicació d’aquest procediment és molt útil per a la comprensió dels diferents nivells d’organització en una xarxa. En el nostre grup, hem aplicat aquest procediment a la xarxa de correu electrònic de la Universitat Rovira i Virgili.
I el que comprovem és que es manté bona part de l’estructura formal de l’organització però que, al mateix temps, hi ha alguns nodes que no es troben a la comunitat que esperem. Això, sens dubte, és molt valuós com a eina per a la gestió d’una organització.
També com una eina d’identificació de les comunitats de treball i dels líders respectius i, per això, es va aplicar el procediment per a la reunions de física estadística. La xarxa que posem a continuació és el resultat de la partició d’aquest grup de científics, en què podem veure que els nodes foscos, identificats com els membres dels comitès científics, es distribueixen per igual entre les diferents branques i apareixen sobretot a les puntes. Això significa que els membres han estat elegits de manera homogènia entre els participants.
Figura 1.24. Representació mitjançant un arbre binari de comunitats de la xarxa de correu electrònic de la Universitat Rovira i Virgili. Cada branca correspon a una comunitat real i els individus més centrals de cada comunitat són els que apareixen als extrems de les branques.
Section0014.jpeg

Figura 1.25. Estructura de comunitats de la xarxa de col∙laboració de física estadística a Espanya.
Section0015.jpeg
Les branques petites corresponen als grups de recerca que s’agrupen a les universitats que, alhora, estan estretament agrupades d’acord amb la proximitat geogràfica. Els nodes ressaltats, que corresponen als membres dels comitès científics es presenten principalment a les puntes de les branques, cosa que mostra el seu lideratge en els grups respectius. La distribució homogènia de nodes verds també mostra que han estat escollits de manera uniforme entre els diferents grups que formen la comunitat de física estadística i que aquests membres són els líders dels equips respectius.

6.Universalitat

En el camp de les xarxes complexes, a causa de l’interès en la disciplina de la física estadística des del començament, hi ha un concepte que ha acabat tenint un ús força generalitzat. Aquest concepte és el de launiversalitat. Amb aquesta idea, a la física estadística s’entén que hi ha diferents sistemes físics que, malgrat tenir fenomenologies diferents, es poden caracteritzar mitjançant un conjunt petit de paràmetres equivalents. L’exemple paradigmàtic és el d’un sistema que experimenta una transició de fase, de manera que el que caracteritza aquesta transició és un únic paràmetre. En aquest sentit, quan sistemes físicament diferents són descrits pel mateix valor numèric del paràmetre diem que pertanyen a la mateixa “classe d’universalitat”. Veurem en aquest capítol que aquest concepte d’universalitats’estén a les xarxes complexes.

6.1.Shortest pathsismall worlds

En les seccions anteriors hem definit el concepte de longitud en una trajectòria en una xarxa complexa. Entre qualsevol parell de nodes tenim definida una distància que és al llarg del que s’anomenen elscamins mínims(shortest paths, en anglès). Aquesta és una mesura, doncs, característica de cada parell de punts.
També com hem dit abans, a partir d’aquestes mesures es pot definir una distància característica del conjunt de la xarxa, sigui una distància mitjana, un radi o un diàmetre. Si aquesta distància característica de la xarxa és un nombre petit en aquesta xarxa l’anomenarem demón petit.
Aquí el conceptepetités relatiu, perquè en el fons hem de comparar. Comparem-lo, per exemple, amb el cas d’una xarxa plana en la qual cada node està connectat només als seus quatre propers veïns. En aquestes circumstàncies, no calen fórmules matemàtiques gaire complicades per a veure que si tenimNnodes la distància característica serà de l’ordre de l’arrel quadrada deN. En aquest cas, la frase clau és “serà de l’ordre de...”. No pretenem donar-ne un valor exacte, sinó una estimació. Vegem-ho amb un exemple: si tenim 100 nodes en una xarxa 10 × 10 esperem que la distància mitjana sigui de l’ordre de 10 (es podria trobar entre 8 i 12, però mai ser propera a 50). Estem fent un raonament purament qualitatiu que ens ofereix un ordre de magnitud, encara que no sigui un valor exacte.
Però el fet que en una xarxa de 100 nodes la distància característica sigui de l’ordre de 10 no vol dir que sigui “petita”, ja que acabem de demostrar enaquest cas que correspon a una xarxa reticular. Si aquesta xarxa, doncs, esperem que sigui un món petit, la seva distància característica haurà de ser bastant més petita que la que acabem de descriure.
Pensem en l’altre extrem. La mateixa xarxa de 100 nodes connectats de tal manera que en tenim un de central i tota la resta són perifèrics i formen una gran estrella. Quina és ara la distància característica? Tampoc no cal fer grans matemàtiques per a veure que serà de l’ordre de 2, i ara aquest valor de 2 sí que és molt més petit que 10, i podrem dir que es tracta d’una xarxa veritablement “petita”.
Però les xarxes reals no són d’una manera ni de l’altra, sempre ens movem entre els dos llindars descrits en els paràgrafs anteriors. Aleshores, si tenim una xarxa de 100 nodes i una distància característica de menys de 5 podem dir que es tracta d’una xarxa “petita”.
Com ho generalitzem això a qualsevol tipus de xarxa? Doncs prenent sempre com a referència models reticulars, com l’anterior de dues dimensions, la distància característica és de l’ordre d’una potència (més petita o igual a 1) del nombre de nodes. Per a una xarxa en forma d’estrella i molt centralitzada, la distància mitjana és de l’ordre d’1 (no és funció del nombre de nodes).
D’una manera més rigorosa direm que una xarxa és un “món petit” si la seva distància característica és de l’ordre del logaritme del nombre de nodes. A continuació, presentem un conjunt de xarxes empíriques en què podem veure que efectivament es compleix aquesta llei de dependència en el logaritme del nombre de nodes de la xarxa.
Figura 1.26. Distàncies mitjanes per a un conjunt de xarxes empíriques en funció del nombre de nodes. La línia de punts és log(N). El factor log<k> és corrector i és el que mostra l’altra dependència, és a dir, com més alt sigui el grau mitjà, més curta és la distància mitjana, tal com lògicament es pot esperar.
Section0016.jpeg
Aquesta descripció matemàtica del que és un “món petit” va ser determinant en l’explosió de l’interès de la comunitat dels físics i matemàtics en el camp de les xarxes. Ara no entenem només un món petit com aquell que intuïtivament ens permet reconèixer que som molt a prop en un món connectat, sinó que, atesa l’estructura de la xarxa, el seu patró de connectivitats ens permet dir que veritablement és un món petit. Per tant, ara tornem al nostre exemple inicial de la IMDB amb més d’un milió d’actors i que la distància màxima entre qualsevol parell d’actors, en termes de pel∙lícules, és quatre. Matemàticament, el logaritme decimal de 106 és 6 i, per tant, això ja no ens ha de sorprendre.

6.2.Distribució de grau

En la secció dedicada a la caracterització a escala individual hem començat definint què és el grau d’un node. I aquest grau, que correspon al nombre de connexions d’un node, ens caracteritza la centralitat del node de manera local.
Si ara, en canvi, volem una descripció estadística de la xarxa i dels graus dels seus nodes, el que farem és un histograma d’aquests graus, és a dir, representar gràficament el nombre de nodes que tenen un grau concret. Si la xarxa és petita, considerarem el grau k com una variable discreta. A continuació, presentem l’histograma de graus de la xarxa de la figura 1.18.
Figura 1.27. Histograma de graus per a la xarxa de la figura 1.18. Efectivament, tenim onze nodes amb grau 1, dos amb grau 2 i, finalment, tres amb grau 5.
Section0017.jpeg
Figura 1.28. Distribució de graus (nombre de col∙laboradors) en la xarxa de col∙laboració de FisEs. L’escala és log-log, és a dir, representació logarítmica en els dos eixos.
Section0018.jpeg
En aquest tipus de figura podem veure, doncs, l’existència de nodes que tenen un grau més elevat que la resta. Ens dóna una idea estadística de la centralitat relativa d’alguns nodes, encara que no ens permeti identificar quins són, però sí conèixer-ne l’existència. En particular, en la segona gràfica podem veure que hi ha un petit nombre de nodes amb moltes col∙laboracions i un gran nombre de nodes amb poques col∙laboracions.

6.3.Lleis de potència i xarxes lliures d’escala

Pocs mesos després del treball pioner de Watts i Strogatz, en què posaven l’èmfasi en la característica de món petit de moltes de les xarxes observades, Albert i Barabási publiquen un article que complementa perfectament l’anterior. Efectivament, les dades sobre les xarxes que es van recollint de manera incessant a partir d’aquell moment són de món petit, però, a més, descobreixen que la distribució de graus no és del tipus que s’esperaria a partir de les “estadístiques” normals.
Què és unaestadística normal? En els estudis estadístics hi ha una distribució de probabilitat que és tan “normal” que fins i tot té aquest nom. Es tracta d’una distribució que matemàticament té la forma següent:
Figura 1.29. Exemples de distribucions “normals”
Section0019.jpeg
en què m és el valor mitjà, al voltant del qual se centra la distribució, i s és la desviació estàndard, que dóna una idea de l’amplària. I és tan normal que és la que permet explicar molta de la fenomenologia estadística que tenim al nostre voltant, des de la distribució d’alçades en una població fins a la distribució de notes en un examen. La característica principal d’aquesta distribució és que és molt picada al voltant del valor mitjà i decau molt ràpidament quan ens n’allunyem.
En canvi, les distribucions de grau que van trobar Albert i Barabási resulta que no s’ajustaven gens a la distribució normal, com podem veure en les figures que trobareu a continuació i com hem vist també en la distribució de graus en la xarxa de col∙laboracions del FisEs.
Figura 1.30. Distribucions de grau (normalitzades) per a algunes xarxes reals: a) Internet a nivell d’encaminadors;
b) xarxa d’actors; c) xarxa de coautors en la comunitat de física de les altes energies; d)xarxa de coautors en neurociència.
Section0020.jpeg
Així, doncs, igual que la xarxa de FisEs, el que podem veure aquí és que en una gràfica log-log les distribucions són properes a una recta, mentre que si fossin una distribució normal decaurien molt més ràpidament, com demostrem en la figura 31.
En aquestes gràfiques hem representat tant una distribució normal com una distribució potencial (de les del tipus observat per Albert i Barabási). Aquí podem veure, sobretot en la gràfica de la dreta, en l’escala log-log, que la distribució normal decau molt més ràpidament que la potencial. De fet, per exemple, amb relació a la distribució d’alçades en una població el que esperem és una distribució picada al voltant d’un valor mitjà, una certa dispersió i un decaïment molt ràpid, perquè, simplement, no esperem en la nostra població la presència d’un individu de més de 2 metres i mig d’alçada.
Figura 1.31. Distribucions normal (fosc) i potencial (clar), en escales lin-lin (esquerra) i log-log (dreta)
Section0021.jpeg
En canvi, en una llei de distribució potencial aquest decaïment és molt lent i, en termes dels graus, el que podem veure és que en aquestes distribucions hi ha molts nodes amb un grau molt baix, però hi ha un nombre considerable de nodes amb un grau que és d’un ordre de magnitud més gran que el valor mitjà. Què són aquests nodes? Òbviament són nodes amb una centralitat (local) molt elevada i que, per tant, esperem que tinguin un paper molt important en la xarxa; és el que en anglès anomenemhubs.I en les distribucions que presentem en la figura 30, en una escala log-log, aquestes s’apropen a una línia recta, i això vol dir que es tracta de distribucions que tenen forma de potència. De fet, si canvia la potència canvia el pendent.
Aquesta va ser una de les grans contribucions d’aquest article d’Albert i Barabási: descobrir que a les xarxes que trobem normalment al nostre voltant tenen una sèrie de nodes molt més connectats del que podríem esperar. Ens ha d’estranyar això en les nostres xarxes? Per què alguns proveïdors d’Internet tenen moltes més connexions? Per què tantes i tantes pàgines del Web apunten a Google, alNew York Timeso a la Viquipèdia? Per què hi ha individus molt ben connectats en la nostra societat? Doncs no ens ha d’estranyar que la distribució de graus presenti una llei de distribució en forma de llei potencial amb la presència dehubs.
El fet que aquesta llei de distribució tingui forma potencial tampoc no ens ha de sorprendre des del punt de vista de la física estadística, ja que hi ha molts fenòmens en la física que estan relacionats amb distribucions potencials, com ara les distribucions de terratrèmols a la Terra o d’allaus en un sistema magnètic. En una escala log-log, les distribucions d’aquests esdeveniments són rectes d’una manera molt aproximada.
Reprenent la discussió del començament d’aquesta secció, quan hem parlat del concepte d’universalitat, aquí cal dir que, en termes de les distribucions degrau, universalitat vol dir que la recta té el mateix pendent, ja que és l’únic paràmetre que la caracteritza. Sense importar l’origen físic de la xarxa en qüestió, podem dir que el mecanisme que la genera és el mateix (en veurem més detalls en la part de modelització) i que una xarxa com la de coparticipants en una pel∙lícula o la d’encaminadors a Internet es generen amb principis microscòpics molt similars. En aquest llenguatge direm que pertanyen a la mateixa classe d’universalitat.
Normalment, les xarxes que presenten una llei de distribució de grau potencial com aquestes se les anomenalliures d’escala(scale-free networks, en anglès). Aquest nom prové del fet que les distribucions són rectes i no hi observem cap pic en un valor determinat que correspondria a un valor característic. En una distribució normal, tant el valor mitjà com la desviació estàndard tenen dimensions de la mateixa variable i, per tant, són dimensions característiques. En canvi, en una distribució potencial no apareix cap altra dimensió que no sigui la mida del sistema, i per això diem, doncs, que no hi ha escales característiques i que per tant és lliure d’escala.

7.Modelització de les xarxes

Per acabar aquesta part del text, presentarem els models que històricament considerem com a claus en el desenvolupament de la disciplina de les xarxes complexes i que expliquen cadascun dels aspectes observats empíricament. Aquesta modelització prové de la necessitat de proposar casos senzills que permetin explicar trets genèrics. No es pretén explicar amb un model matemàtic senzill la xarxa d’actors ni la d’un ecosistema, sinó per quina raó aquestes xarxes presenten característiques comunes, com ara ser de món petit o el fet que la seva distribució de grau presenti una forma potencial.

7.1.Erdös-Rényi (ER)

Aquests dos matemàtics hongaresos van fer nombroses contribucions, a mitjan segle passat, al que en aquell moment s’anomenava teoria de grafs (bé, actualment en entorns més matemàtics es continua anomenant d’aquesta manera, malgrat que aquí utilitzem la variant més interdisciplinària de xarxa complexa). La qüestió que més ens interessa en aquest text és la del model senzill que van proposar, que és el que normalment anomenemrandom graph d’Erdös-Rényi.
En general, podem dir que unrandom graphés una xarxa (o graf) aleatoris, com el seu nom indica. El que distingeix un model particular són les seves caracteritzacions estadístiques que són, òbviament, una conseqüència de la mateixa construcció del graf.
Com es construeix una xarxa aleatòria deNnodes iMenllaços? Tenim els nombres,NiM, però clar ara el que cal és determinar quins són els nodes connectats pels enllaços i de quina manera es fa això determina les característiques estadístiques de la xarxa.
A partir d’aquesta idea el primer que podem pensar és, simplement, a assignar elsMenllaços de manera totalment aleatòria, i sense cap altra restricció, alsNnodes existents. El resultat seria un graf, que anomenaremG(N,M). Però ens ha de quedar clar que el graf resultant no és res més que una de les possibles realitzacions de graf aleatori deNnodes iMenllaços. En tractar-se, doncs, d’un model hem de tenir en compte que hem de generar un conjunt de grafs amb les mateixes característiques perquè tingui sentit estadístic. En la figura que presentem a continuació hi ha tots els possibles grafs amb quatre nodes i quatre enllaços.
Figura 1.32. Tots els possibles grafs de quatre nodes i quatre enllaços. Els tres de la part superior corresponen als grafs en què tots els nodes tenen exactament un enllaç. I els dotze de la part inferior, als casos en què hi ha un node amb tres enllaços, dos amb dos, i un amb un. Combinatòriament, podem dir que de tots els possibles enllaços entre quatre nodes (4 × 3/2 = 6, perquè el graf no és dirigit) els agafem de quatre en quatre; així, els possibles grafs seran
55A_fmt.jpeg
Section0022.jpeg
Així, doncs, en cas que vulguem analitzar qualsevol característica, per exemple el diàmetre, el que haurem de fer és calcular la mitjana de tots els possibles grafs compatibles amb el nombre de nodes i enllaços. En el cas que hem representat, però, no cal comptar tots els casos perquè, d’independents, només n’hi ha dos. Podríem dir que els tres de la filera superior pertanyen a una classe (A formada per tres elements), ja que són topològicament equivalents, i la resta a una altra classe (B formada per dotze elements). El diàmetre mitjà seria, doncs:
55_fmt.jpeg
encara que en aquesta cas la resposta és trivial. Però generalitzar-ho a un nombre arbitrari de nodes i enllaços no és gens trivial.
Aquest model que hem anomenat d’Erdös-Rényiadmet el que podríem dir una segona representació. Una representació alternativa, que s’expressa com aG(N,p), en què ara el que fixem és també el nombre de nodes, però l’altre paràmetre p és la probabilitat que existeixi cada enllaç i és la mateixa per a tots els enllaços.
GEPHI
Amb aquest programari podem generar grafs aleatoris d’Erdös-Rényi en qualsevol de les dues representacions.
Figura 1.33. Model de graf aleatori d’Erdös-Rényi G(N, p). En una xarxa de deu nodes tenim en principi 10 * 9/2 = 45 enllaços i cadascun d’aquest existeix, de manera independent, amb una probabilitat p.
Section0023.jpeg
En aquest cas, no fixem el nombre d’enllaços i novament haurem de fer una mitjana sobre els possibles casos. La diferència respecte de l’anterior és que ara no tenim un nombre fixat i tancat d’elements de la mostra estadística, sinó que només tenim una probabilitat que existeixi cadascun dels enllaços. Així, la probabilitat que aparegui un graf del tipus anterior determinat és:
56A_fmt.jpeg
Aquesta segona representació dels grafs aleatoris és útil perquè molts dels resultats exactes que es coneixen per a aquest tipus de xarxes s’ha obtingut a partir d’aquesta representació. En particular, atesosNipés fàcil calcular-ne la distribució de grau, ja que es tracta d’una distribució binomial:
56_fmt.jpeg
i que en el cas d’un nombre de nodes gran, es redueix a la distribució de Poisson:
57A_fmt.jpeg
que, per a valors grans del grau, decau de manera exponencial i, per tant, molt més ràpidament del que hem observat abans en moltes xarxes complexes.
D’altra banda, també es pot demostrar analíticament que el diàmetre de la xarxa escala com el logaritme del nombre de nodes, i mostrar, així, doncs, la característica de món petit.
Figura 1.34. Xarxa construïda amb GEPHI seguint el model d’ER amb 100 nodes i 300 enllaços. A la dreta: histograma de la distribució de graus.
Section0024.jpeg
Figura 1.35. Distribució de graus en el model d’Erdös-Rényi. La línia contínua representa la distribució de Poisson.
Section0025.jpeg

7.2.Watts-Strogatz (WS)

En les seves observacions de les xarxes complexes discutides en apartats anteriors Watts i Strogatz van veure que aquestes xarxes tenien dues característiques comunes: primera, que eren de món petit, és a dir, que les distàncies mitjanes creixen amb el logaritme del nombre de nodes, i segona, que el coeficient declusteringera més gran de l’esperat.
Aquestes dues propietat en el fons són relatives. I ens ho hem de mirar en la perspectiva de l’època. Al final del segle XX només es parlava de dos tipus d’estructures topològiques discretes (anomenades xarxes només en entorns de les ciències socials). D’una banda, estructures reticulars, com ara un anell en dimensió 1 o una malla quadrada en dues dimensions. De l’altra, estructures totalment aleatòries, com ara el model de graf aleatori d’ER.
I aquests dos models presenten característiques ben diferents. D’una banda, els models reticulars, com hem vist abans, tenen distancies mitjanes que creixen amb una potència del nombre de nodes i, en canvi, el seu coeficient de clusterització és força elevat perquè per construcció la densitat local és elevada. D’una altra banda, el model ER és un model de món petit perquè el diàmetre creix com el logaritme del nombre de nodes i la clusterització és molt baixa, de fet exactament igual a p.
Aleshores, Watts i Strogatz es troben amb la paradoxa que les seves observacions de petites distàncies i clusteritzacions altes no es pot explicar amb cap de les dues estructures que acabem de relatar. El model reticular té distàncies grans iclusteringelevada, mentre que el model d’ER és justament el contrari, distàncies petites iclusteringbaixa.
La seva proposta va ser la d’un model que podia explicar els dos fets empírics simultàniament. D’una banda, era prou aleatori perquè les distàncies fossin petites i, de l’altra, perquè mantingués certa estructura regular per tal de mantenir unaclusteringelevada. Gràficament, el representem en la gràfica següent.
Figura 1.36. Model de Watts i Strogatz. Es parteix d’un anell amb connexions a veïns propers i també als veïns dels veïns. Aleshores, amb probabilitat p es canvia un enllaç de la xarxa reticular original per un enllaç aleatori. Per a valors petits de p el graf és pràcticament regular, mentre que per a p molt propera a 1 el graf és un graf d’ER.
Section0026.jpeg
I què guanyem amb aquest nou model de xarxa? La resposta és clara en la gràfica següent.
Figura 1.37. Coeficient de clustering i distància mitjana entre nodes per al model de WS. Sempre es pren com a referència el valor en p = 0. El que hem de destacar és que petits increments de p a partir del 0 fan que decreixi ràpidament la distància, mentre que el clustering resta invariant.
Section0027.jpeg
Podem veure, doncs, que per a valor depde l’ordre de 0,01 tenim distàncies petites, mentre que la clusterització continua sent elevada i aquesta és, doncs, la regió en què cauen bona part de les xarxes descrites en la primera part d’aquesta part del text.
Aquest model va ser el punt de partida de l’estudi i modelització de les xarxes complexes. La simplicitat rau en els dos extrems, tant en la topologia regular, reticular, ordenada, com en la totalment desordenada. Aquesta simplicitat que permet càlculs matemàtics relativament senzills. Però el nostre món no és simple. I les xarxes que observem al nostre voltant tampoc. Són complexes i aquesta complexitat la podem entendre a partir d’aquest model com aquest estat intermedi entre el que està ordenat i el desordenat. I els càlculs, malauradament, ja no són tan senzills.

7.3.Barabási-Albert (BA)

Hem dit en apartats anteriors que la segona contribució que és considerada com la llavor de l’estudi de les xarxes complexes és el treball de Barabási i Albert que bàsicament descobreixen que xarxes provinents d’orígens tan diferents tenen comportaments semblants, en particular ells es van fixar en la distribució de grau, que era potencial.
Bé, aquestes xarxes que analitzen Barabási i Albert són efectivament xarxes de món petit perquè compleixen la propietat que les distàncies són petites i, a més, lesclusteritzacions són elevades. Per tant, podríem pensar que es podrien explicar amb el model de WS. Però el model de WS, tot i que explica bé les distàncies i elclustering, com hem vist abans, té encara una distribució de graus que és la de Poisson. Per tant, aquest model no serveix per a explicar les distribucions potencials de grau.
La seva proposta rau en el fet que les xarxes apareixen per un procés de creixement. Les xarxes no són productes que existeixen simplement com a agregats, sinó que són el resultat d’una evolució que va afegint nodes a la xarxa, com pot ser qualsevol de les xarxes que hem analitzat prèviament, per exemple, les de coautors, Internet o el WWW. Però la manera d’afegir nous nodes a la xarxa és el que no és aleatori, sinó que compleix una regla, senzilla però que podem dir que té a veure amb la popularitat, entesa de manera molt general. Per exemple, si nosaltres creem una pàgina web, molt probablement afegirem enllaços a altres pàgines perquè són populars, com ara cercadors, el nostre diari favorit o la institució a la qual pertanyem.
Aleshores, Barabási i Albert consideren que la xarxa creix en el sentit que els nodes que s’hi afegeixen tendiran a enllaçar-se amb nodes ja existents a la xarxa però que ho faran amb els nodes que ja tenen un grau elevat (en aquest cas, el grau seria una mesura de la popularitat del node). I aquesta regla és la que anomenen depreferential attachment(és a dir, d’afegiment preferencial) i la quantifiquen de manera purament lineal, és a dir, que la probabilitat que un nou node estableixi un enllaç a un node existent és directament proporcional al grau del node ja present a la xarxa.
Figura 1.38. Regla del model de Barabási-Albert. El node que arriba es connectarà amb més probabilitat als nodes que ja tenen més connexions. Així, els nous enllaços són els que corresponen a les línies discontínues.
Section0028.jpeg
Seguint, doncs, aquesta regla es poden construir xarxes complexes que siguin a la vegada de món petit, d’alta clusterització i amb distribució de grau potencial, com la que tenim en la figura següent.
Figura 1.39. Xarxa construïda amb GEPHI seguint el model de BA amb 100 nodes i 294 enllaços. A la dreta: histograma de la distribució de graus.
Section0029.jpeg
Podem veure en la construcció de la xarxa que, comparada amb l’ER anterior amb el mateix nombre de nodes i pràcticament el mateix nombre d’enllaços, ara aquesta xarxa té una densitat d’enllaços més elevada a la part central. Aquests serien elshubs,els nodes amb una connectivitat més elevada, com podem veure en l’histograma de la part dreta de la figura.
Des d’un punt de vista matemàtic, es pot demostrar de manera relativament simple que la distribució de grau associada al model de BA és potencial amb exponent –3, que la fa de valor molt proper al de les observades empíricament.

7.4.Altres models

Com és fàcil d’imaginar, en aquests anys des dels primers models de WS i de BA hi ha hagut multitud de models que han permès explicar bona part de la fenomenologia associada a les xarxes complexes.
Des de models que donen exponents molt més propers als observats, o fins i tot amb un exponent ajustable, que admeten estructures de comunitats, que presenten correlacions entre els graus d’un node i els dels seus veïns.
Aquests models es troben, però, allunyats de l’objectiu d’iniciar els lectors en el món de les xarxes complexes, que és el d’aquest text.