Punto de referencia Lancichinetti-Fortunato-Radicchi

Algoritmo

El benchmark Lancichinetti–Fortunato–Radicchi es un algoritmo que genera redes de referencia (redes artificiales que se asemejan a las redes del mundo real). Tienen comunidades conocidas a priori y se utilizan para comparar diferentes métodos de detección de comunidades. ^[1] La ventaja del benchmark sobre otros métodos es que tiene en cuenta la heterogeneidad en las distribuciones de los grados de los nodos y de los tamaños de las comunidades. ^[2]

El algoritmo

Los grados de los nodos y los tamaños de las comunidades se distribuyen según una ley de potencia , con diferentes exponentes. El punto de referencia supone que tanto el grado como el tamaño de la comunidad tienen distribuciones de ley de potencia con diferentes exponentes, y , respectivamente. es el número de nodos y el grado medio es . Hay un parámetro de mezcla , que es la fracción media de nodos vecinos de un nodo que no pertenecen a ninguna comunidad a la que pertenece el nodo de referencia. Este parámetro controla la fracción de aristas que se encuentran entre comunidades. ^[2] Por lo tanto, refleja la cantidad de ruido en la red. En los extremos, cuando todos los enlaces están dentro de enlaces comunitarios, si todos los enlaces están entre nodos que pertenecen a diferentes comunidades. ^[3] ${\displaystyle \gamma }$ ${\displaystyle \beta }$ ${\displaystyle N}$ ${\displaystyle \langle k\rangle }$ ${\displaystyle \mu }$ ${\displaystyle \mu =0}$ ${\displaystyle \mu =1}$

Se puede generar la red de referencia utilizando los siguientes pasos.

Paso 1: Generar una red con nodos que sigan una distribución de ley de potencia con exponentey elegir los extremos de la distribuciónypara obtener el grado promedio deseado es. ${\displaystyle \gamma }$ ${\displaystyle k_{\min }}$ ${\displaystyle k_{\max }}$ ${\displaystyle \langle k\rangle }$

Paso 2: la fracción de enlaces de cada nodo es con nodos de la misma comunidad, mientras que la fracciónes con los otros nodos. ${\displaystyle (1-\mu )}$ ${\displaystyle \mu }$

Paso 3: Generar tamaños de comunidad a partir de una distribución de ley de potencia con exponente. La suma de todos los tamaños debe ser igual a. Los tamaños mínimo y máximo de la comunidadydeben satisfacer la definición de comunidad de modo que cada nodo no aislado se encuentre en al menos una comunidad: ${\displaystyle \beta }$ ${\displaystyle N}$ ${\displaystyle s_{\min }}$ ${\displaystyle s_{\max }}$

${\displaystyle s_{\min }>k_{\min }}$

${\displaystyle s_{\max }>k_{\max }}$

Paso 4: Inicialmente, no se asigna ningún nodo a las comunidades. Luego, cada nodo se asigna aleatoriamente a una comunidad. Siempre que el número de nodos vecinos dentro de la comunidad no exceda el tamaño de la misma, se agrega un nuevo nodo a la comunidad; de lo contrario, se queda fuera. En las siguientes iteraciones, el nodo “sin hogar” se asigna aleatoriamente a alguna comunidad. Si esa comunidad está completa, es decir, se agotó el tamaño, se debe desvincular un nodo seleccionado aleatoriamente de esa comunidad. Detenga la iteración cuando todas las comunidades estén completas y todos los nodos pertenezcan al menos a una comunidad.

Paso 5: Implementar el recableado de los nodos manteniendo los mismos grados de nodo pero afectando solo la fracción de enlaces internos y externos de tal manera que el número de enlaces fuera de la comunidad para cada nodo sea aproximadamente igual al parámetro de mezcla. ^[2] ${\displaystyle \mu }$

Pruebas

Considere una partición en comunidades que no se superponen. Las comunidades de nodos elegidos aleatoriamente en cada iteración siguen una distribución que representa la probabilidad de que un nodo elegido aleatoriamente sea de la comunidad . Considere una partición de la misma red que fue predicha por algún algoritmo de búsqueda de comunidad y tiene distribución. La partición de referencia tiene distribución. La distribución conjunta es . La similitud de estas dos particiones se captura mediante la información mutua normalizada . ${\displaystyle p(C)}$ ${\displaystyle C}$ ${\displaystyle p(C_{2})}$ ${\displaystyle p(C_{1})}$ ${\displaystyle p(C_{1},C_{2})}$

${\displaystyle I_{n}={\frac {\sum _{C_{1},C_{2}}p(C_{1},C_{2})\log _{2}{\frac {p(C_{1},C_{2})}{p(C_{1})p(C_{2})}}}{{\frac {1}{2}}H(\{p(C_{1})\})+{\frac {1}{2}}H(\{p(C_{2})\})}}}$

Si el punto de referencia y las particiones detectadas son idénticas y, por lo tanto, son independientes entre sí. ^[4] ${\displaystyle I_{n}=1}$ ${\displaystyle I_{n}=0}$

Referencias

1. Hua-Wei Shen (2013). "Estructura comunitaria de redes complejas". Springer Science & Business Media. 11–12.
2. A. Lancichinetti, S. Fortunato y F. Radicchi. (2008) Gráficos de referencia para probar algoritmos de detección de comunidades. Physical Review E, 78. arXiv :0805.4770
3. Twan van Laarhoven y Elena Marchiori (2013). "Detección de comunidades de redes con clasificadores de aristas entrenados en gráficos LFR". https://www.cs.ru.nl/~elenam/paper-learning-community.pdf Archivado el 3 de noviembre de 2018 en Wayback Machine.
4. Barabasi, A.-L. (2014). "Ciencia de redes". Capítulo 9: Comunidades.