Ciència de xarxes

La ciència de xarxes és un camp acadèmic que estudia xarxes complexes com ara xarxes de telecomunicacions, xarxes d'ordinadors, xarxes biològiques, xarxes cognitives i semàntiques i xarxes socials, considerant diferents elements o actors representats per nodes (o vèrtexs ) i les connexions entre els elements o actors. com a enllaços (o vores). El camp es basa en teories i mètodes, com ara la teoria de grafs de les matemàtiques, la mecànica estadística de la física, la mineria de dades i la visualització d'informació des de la informàtica, el modelatge inferencial a partir de l'estadística i l'estructura social de la sociologia. El Consell Nacional d'Investigació dels Estats Units defineix la ciència de xarxes com "l'estudi de representacions en xarxa de fenòmens físics, biològics i socials que

Sociograma de Moreno d'una classe de 1r.

condueixen a models predictius d'aquests fenòmens".

Antecedents i història

L'estudi de les xarxes ha sorgit en diverses disciplines com a mitjà per analitzar dades relacionals complexes. El primer article conegut en aquest camp és el famós Seven Bridges of Königsberg escrit per Leonhard Euler el 1736. La descripció matemàtica d'Euler de vèrtexs i arestes va ser la base de la teoria de grafs, una branca de les matemàtiques que estudia les propietats de les relacions per parelles en una estructura de xarxa. El camp de la teoria de grafs va continuar desenvolupant-se i va trobar aplicacions en química (Sylvester, 1878).

Dénes Kőnig, matemàtic i professor hongarès, va escriure el primer llibre de Teoria de grafs, titulat "Teoria dels grafs finits i infinits", l'any 1936.

A la dècada de 1930 va arribar als Estats Units Jacob Moreno, psicòleg de tradició Gestalt. Va desenvolupar el sociograma i el va presentar al públic l'abril de 1933 en una convenció de metges. Moreno afirmava que "abans de l'arribada de la sociometria ningú sabia com era "precisament" l'estructura interpersonal d'un grup" (Moreno, 1953). El sociograma era una representació de l'estructura social d'un grup d'alumnes de primària. Els nois eren amics de nois i les noies eren amics de noies amb l'excepció d'un noi que va dir que li agradava una noia soltera. El sentiment no va ser correspost. Aquesta representació en xarxa de l'estructura social es va trobar tan intrigant que es va publicar a The New York Times (3 d'abril de 1933, pàgina 17). El sociograma ha trobat moltes aplicacions i ha crescut fins al camp de l'anàlisi de xarxes socials.

La teoria probabilística en la ciència de xarxes es va desenvolupar com una branca de la teoria de grafs amb els vuit articles famosos de Paul Erdős i Alfréd Rényi sobre gràfics aleatoris. Per a les xarxes socials, el model de gràfics aleatoris exponencials o p* és un marc de notació utilitzat per representar l'espai de probabilitat d'un empat en una xarxa social. Un enfocament alternatiu de les estructures de probabilitat de xarxa és la matriu de probabilitat de xarxa, que modela la probabilitat que es produeixin arestes en una xarxa, basant-se en la presència o absència històrica de la vora en una mostra de xarxes.

Models de xarxa

Els models de xarxa serveixen com a base per entendre les interaccions dins de xarxes empíriques complexes. Diversos models de generació de gràfics aleatoris produeixen estructures de xarxa que es poden utilitzar en comparació amb xarxes complexes del món real.

Model de gràfic aleatori Erdős–Rényi

Aquest model Erdős–Rényi es genera amb N = 4 nodes. Per a cada aresta del gràfic complet format per tots N nodes, es genera un nombre aleatori i es compara amb una probabilitat donada. Si el nombre aleatori és menor que p, es forma una aresta al model.

El model Erdős–Rényi, anomenat així per Paul Erdős i Alfréd Rényi, s'utilitza per generar gràfics aleatoris en què les arestes s'estableixen entre nodes amb probabilitats iguals. Es pot utilitzar en el mètode probabilístic per demostrar l'existència de gràfics que satisfan diverses propietats, o per proporcionar una definició rigorosa del que significa que una propietat es compleixi per a gairebé tots els gràfics.

Model de configuració

El model de configuració pren com a entrada una seqüència de graus o una distribució de graus (que posteriorment s'utilitza per generar una seqüència de graus) i produeix gràfics connectats aleatòriament en tots els aspectes que no siguin la seqüència de graus. Això vol dir que per a una determinada elecció de la seqüència de graus, el gràfic s'escull uniformement a l'atzar del conjunt de tots els gràfics que compleixen aquesta seqüència de graus. El grau $k$ d'un vèrtex escollit aleatòriament és una variable aleatòria independent i idèntica distribuïda amb valors enters. Quan ${\textstyle \mathbb {E} [k^{2}]-2\mathbb {E} [k]>0}$, el gràfic de configuració conté el component connectat gegant, que té una mida infinita. La resta de components tenen mides finites, que es poden quantificar amb la noció de distribució de mida.

Model de món petit de Watts–Stregatz

El model de Watts i Strogatz és un model de generació de gràfics aleatori que produeix gràfics amb propietats de món petit.

S'utilitza una estructura de gelosia inicial per generar un model de Watts-Stregatz. Cada node de la xarxa està inicialment vinculat al seu $\langle k\rangle$ veïns més propers. Un altre paràmetre s'especifica com la probabilitat de recablejat. Cada aresta té una probabilitat $p$ que es reconnectarà al gràfic com una vora aleatòria. El nombre esperat d'enllaços reconnectats al model és $pE=pN\langle k\rangle /2$.

Model d'adhesió preferent Barabási–Albert (BA)

El model Barabási–Albert és un model de xarxa aleatori que s'utilitza per demostrar una vinculació preferent o un efecte "ric-enriquir-se". En aquest model, és més probable que una vora s'uneixi als nodes amb graus més alts. La xarxa comença amb una xarxa inicial de m ₀ nodes. m ₀ ≥ 2 i el grau de cada node a la xarxa inicial hauria de ser com a mínim 1, en cas contrari sempre romandrà desconnectat de la resta de la xarxa.

Model de fitness

Un altre model on l'ingredient clau és la naturalesa del vèrtex ha estat introduït per Caldarelli et al. Aquí es crea un enllaç entre dos vèrtexs $i,j$ amb una probabilitat donada per una funció d'enllaç $f(\eta _{i},\eta _{j})$ de les aptituds dels vèrtexs implicats.