Lancichinetti-Fortunato-Radicchi de referencia es un algoritmo que genera referencia redes (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 punto de referencia sobre otros métodos es que da cuenta de la heterogeneidad en las distribuciones de los grados de los nodos y del tamaño 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 asume 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 promedio de nodos vecinos de un nodo que no pertenecen a ninguna comunidad a la que pertenezca el nodo de referencia. Este parámetro controla la fracción de bordes que hay 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 los enlaces de la comunidad, si todos los enlaces son entre nodos que pertenecen a diferentes comunidades. [3]
Se puede generar la red de referencia mediante los siguientes pasos.
Paso 1: Genere una red con nodos siguiendo una distribución de ley de potencia con exponente y elige los extremos de la distribución y obtener el grado promedio deseado es .
Paso 2: fracción de enlaces de cada nodo es con nodos de la misma comunidad, mientras que la fracción está con los otros nodos.
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ínimos y máximos de la comunidad y debe satisfacer la definición de comunidad para que cada nodo no aislado esté en al menos una comunidad:
Paso 4: Inicialmente, no se asignan nodos a las comunidades. Luego, cada nodo se asigna aleatoriamente a una comunidad. Siempre que la cantidad de nodos vecinos dentro de la comunidad no exceda el tamaño de la comunidad, se agregará un nuevo nodo a la comunidad; de lo contrario, permanecerá fuera. En las siguientes iteraciones, el nodo "sin hogar" se asigna aleatoriamente a alguna comunidad. Si esa comunidad está completa, es decir, se agota el tamaño, se debe desvincular un nodo seleccionado al azar 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 nodos manteniendo los mismos grados de nodo pero solo afectando la fracción de enlaces internos y externos de modo que el número de enlaces fuera de la comunidad para cada nodo sea aproximadamente igual al parámetro de mezcla. [2]
Pruebas
Considere una partición en comunidades que no se superpongan. Las comunidades de nodos elegidos al azar en cada iteración siguen un distribución que representa la probabilidad de que un nodo elegido al azar sea de la comunidad . Considere una partición de la misma red que fue predicha por algún algoritmo de búsqueda de la comunidad y tienedistribución. La partición de referencia tienedistribución. La distribución conjunta es. La similitud de estas dos particiones se captura mediante la información mutua normalizada .
Si el punto de referencia y las particiones detectadas son idénticas, y si entonces son independientes entre sí. [4]
Referencias
- ^ Hua-Wei Shen (2013). "Estructura comunitaria de redes complejas". Springer Science & Business Media. 11-12.
- ^ a b c A. Lancichinetti, S. Fortunato y F. Radicchi. (2008) Gráficos de referencia para probar algoritmos de detección de comunidades. Revisión física E, 78. arXiv : 0805.4770
- ^ Twan van Laarhoven y Elena Marchiori (2013). "Detección de comunidad de red con clasificadores de bordes entrenados en gráficos LFR". https://www.cs.ru.nl/~elenam/paper-learning-community.pdf
- ^ Barabasi, A.-L. (2014). "Ciencia de la red". Capítulo 9: Comunidades.