Ret complexa

Ret complexa

En el context de la ciència de rets, una ret complexa es referix a una ret (modelada com grafo) que posseïx certes propietats estadístiques i topològiques no trivials que no ocorren en rets simples; p.i., distribucions de grau que seguixen lleis de potència, estructures jeràrquiques, estructures comunitàries, llongitut entre qualssevol dos ents del sistema curt, o alta cohesividad local (mida a través del coeficient de agrupamiento). Eixemple de rets en tals característiques en la naturalea són les rets socials, les rets neuronals, les rets de tràfic aéreu i les rets tróficas, entre moltes atres.

Ret de co-aparició dels personages de la novela Els Miserables de Victor Hugo

Definició matemàtica de ret

Una ret o grafo $R=(𝒩,ℰ)$ es definix per un conjunt $𝒩=𝒩(R)$ d'elements cridats nodos o vèrtiços i un atre conjunt, $ℰ=ℰ(R)\subset 𝒩\times 𝒩$ d'elements denominats enllaços o arestes. Cada enllaç correspon a un parell no-ordenat $\{i,j\}$ de nodos. Si considerem els enllaços com a parells ordenats, direm que $R$ és una ret dirigida o grafo dirigit. Si cada enllaç $\{i,j\}$ té assignat un valor numèric $w_{ij}$, direm que la ret és ponderada i el valor $w_{ij}$ serà cridat pes o ponderació de l'enllaç $\{i,j\}$.

Conceptes bàsics en rets

Dos nodos $i,j$ d'una ret es diuen adjacents si estos estan conectats per un enllaç. Es dirà que un enllaç és incident en un nodo $i$ si dit enllaç és de la forma $\{i,j\}$ per a algun $j$ en $𝒩(R)$. El veïnat de $i$, generalment denotat per $V(i)$, es definix com el conjunt dels $j\in 𝒩(R)$ tals que $\{i,j\}\in ℰ(R)$. El conjunt $V^{+}(i)=V(i)\cup \{i\}$ serà cridat veïnat inclusivo de $i$.

Definició de subred

Si ${𝒩}^{\prime }\subseteq 𝒩$ i ${ℰ}^{\prime }\subseteq {𝒩}^{\prime }\times {𝒩}^{\prime }$ tal que ${ℰ}^{\prime }\subseteq ℰ$, es diu que el parell $R^{\prime }=({𝒩}^{\prime },{ℰ}^{\prime })$ és una subred (o subgrafo) de $R=(𝒩,ℰ)$. Si ${ℰ}^{\prime }=({𝒩}^{\prime }\times {𝒩}^{\prime })\cap ℰ$ direm que $R^{\prime }$ és la sub-ret induïda per ${𝒩}^{\prime }$.

k-Clique o k- ret completa

Un $k-${clique} (o $k-${ret completa}), denotada per $K_n$, és una ret en la que tot parell de nodos $i,j\in 𝒩(K_n)$ esta conectat per un enllaç en $ℰ(K_n)$. Un clique $C\subseteq R$ es diu maximal si no pot agregar-se un atre nodo a $R$ sense que este deixe de ser un clique en $R$.

Rets bipartitas

Erro al crear miniatura:

Ret Bipartita. Els colors roig i blau simbolisen les dos classes nodales. Observe's que no hi ha enllaços entre nodos d'un mateix color.

Bàsicament, en este tipo de rets el conjunt de nodos $𝒩$ pot escriure's com l'unió disjunta de dos conjunts ${𝒩}_1$ i ${𝒩}_2$ de manera que en la ret no hi ha enllaços de la forma $\{i,j\}\in ℰ$ en $i\in {𝒩}_1$ i $j\in {𝒩}_2$. En la figura pot vore's un eixemple d'este tipo de rets.

Matriu de adyacencia

La matriu de adyacencia $A$ d'una ret $R$ és una matriu de $n\times n$ tal que

$A_{ij}=\{\begin{array}{cc}1& \text{ si }\{i,j\}\in ℰ(R)\\ 0& \text{ en caso contrario.}\end{array}$

Esta matriu nos permet representar de manera algebraica l'estructura de ret.