Modelo de red jerárquica

Los modelos de red jerárquica son algoritmos iterativos para crear redes que pueden reproducir las propiedades únicas de la topología sin escala y la alta agrupación de nodos al mismo tiempo. Estas características se observan ampliamente en la naturaleza, desde la biología hasta el lenguaje y algunas redes sociales.

Concepto

El modelo de red jerárquica es parte de la familia de modelos sin escala y comparte su propiedad principal de tener proporcionalmente más centros entre los nodos que por generación aleatoria; sin embargo, difiere significativamente de otros modelos similares (Barabási–Albert, Watts–Strogatz) en la distribución de los coeficientes de agrupamiento de los nodos: como otros modelos predecirían un coeficiente de agrupamiento constante en función del grado del nodo, en orden jerárquico Se espera que los nodos de los modelos con más enlaces tengan un coeficiente de agrupamiento más bajo. Además, mientras que el modelo de Barabási-Albert predice un coeficiente de agrupamiento medio decreciente a medida que aumenta el número de nodos, en el caso de los modelos jerárquicos no existe una relación entre el tamaño de la red y su coeficiente de agrupamiento medio.

El desarrollo de modelos de red jerárquica estuvo motivado principalmente por el fracaso de los otros modelos sin escala al incorporar la topología sin escala y la alta agrupación en un solo modelo. Dado que varias redes de la vida real (redes metabólicas, la red de interacción de proteínas, la World Wide Web o algunas redes sociales) exhiben tales propiedades, se introdujeron diferentes topologías jerárquicas para dar cuenta de estas diversas características.

Algoritmo

Los modelos de red jerárquica generalmente se derivan de forma iterativa al replicar el grupo inicial de la red de acuerdo con una determinada regla. Por ejemplo, considere una red inicial de cinco nodos totalmente interconectados (N=5). Como siguiente paso, cree cuatro réplicas de este clúster y conecte los nodos periféricos de cada réplica al nodo central del clúster original (N=25). Este paso se puede repetir indefinidamente, por lo tanto, para cualquier paso k, el número de nodos en el sistema se puede derivar por N=5.

Por supuesto, ha habido varias formas diferentes de crear sistemas jerárquicos propuestos en la literatura. Estos sistemas generalmente difieren en la estructura del grupo inicial, así como en el grado de expansión que a menudo se denomina factor de replicación del modelo.

Propiedades

Distribución de grados

Al ser parte de la familia de modelos sin escala, la distribución de grados del modelo de red jerárquica sigue la ley de potencia, lo que significa que un nodo seleccionado al azar en la red tiene k aristas con una probabilidad

donde c es una constante y γ es el exponente de grado. En la mayoría de las redes del mundo real que exhiben propiedades libres de escala, γ se encuentra en el intervalo [2,3].

Como resultado específico para modelos jerárquicos, se ha demostrado que el exponente de grado de la función de distribución se puede calcular como

donde M representa el factor de replicación del modelo.

Coeficiente de agrupamiento

A diferencia de los otros modelos libres de escala (Erdős–Rényi, Barabási–Albert, Watts–Strogatz) donde el coeficiente de agrupamiento es independiente del grado de un nodo específico, en las redes jerárquicas el coeficiente de agrupamiento se puede expresar como una función del grado de la siguiente manera:

Se ha demostrado analíticamente que en redes deterministas libres de escala el exponente β toma el valor de 1.

Ejemplos

Red de actores

Según la base de datos de actores disponible en www.IMDB.com, la red está definida por actores de Hollywood que están conectados entre sí si ambos aparecen en la misma película, lo que da como resultado un conjunto de datos de 392 340 nodos y 15 347 957 aristas. Como han demostrado estudios anteriores, esta red exhibe propiedades libres de escala al menos para valores altos de k. Además, los coeficientes de agrupamiento parecen seguir la ley de escala requerida con el parámetro -1 proporcionando evidencia de la topología jerárquica de la red. Intuitivamente, los actores de una actuación tienen, por definición, un coeficiente de agrupación de uno, mientras que es muy poco probable que los actores que protagonizan varias películas trabajen con el mismo equipo, lo que en general da como resultado un coeficiente de agrupación decreciente a medida que aumenta el número de coprotagonistas.

Red de idiomas

Las palabras pueden ser consideradas como red si se especifican los criterios de vinculación entre ellas. Definiendo enlaces como apariencia como sinónimo en el diccionario Merriam-Webster se construyó una web semántica de 182.853 nodos con 317.658 aristas. Resultó que la red de palabras obtenida sigue una ley de potencia en su distribución de grados, mientras que la distribución del coeficiente de agrupación indica que la red subyacente sigue una estructura jerárquica con γ =3,25 y β =1.

Red de paginas web

Mapeando el dominio www.nd.edu se obtuvo una red de 325.729 nodos y 1.497.135 aristas cuya distribución de grados seguía una ley de potencias con γ _out =2,45 y γ _in =2,1 para los grados de entrada y salida, respectivamente. La evidencia de la distribución de la ley de escala de los coeficientes de agrupamiento es significativamente más débil que en los casos anteriores, aunque hay un patrón decreciente claramente visible en la distribución de C(k), lo que indica que cuantos más enlaces tiene un dominio, menos interconectado está el enlace. las páginas web son.

Red de dominio

Se encontró que la red de dominio, es decir, Internet a nivel de sistema autónomo (AS) donde se dice que los dominios administrativos están conectados en caso de que haya un enrutador que los conecte, comprende 65.520 nodos y 24.412 enlaces entre ellos y exhibe las propiedades de una red sin escala. La distribución muestral de los coeficientes de agrupamiento se ajustó mediante la función de escala C(k)~k cuyo exponente es (en términos absolutos) algo menor que el parámetro teórico para redes deterministas sin escala.