El filtro de disparidad [1] es un algoritmo de reducción de red (también conocido como algoritmo de dispersión de gráficos [2] ) para extraer la estructura principal de una red ponderada no dirigida . Muchas redes del mundo real, como las redes de citas , la red alimentaria y las redes de aeropuertos, muestran una distribución estadística de colas pesadas del peso y la fuerza de los nodos . El filtro de disparidad puede reducir suficientemente la red sin destruir la naturaleza de múltiples escalas de la red. El algoritmo es desarrollado por M. Angeles Serrano, Marian Boguna y Alessandro Vespignani .
k -core descomposición es un algoritmo que reduce un gráfico en un máximo conectado subgrafo de vértices con al menos grado k . Este algoritmo solo se puede aplicar a gráficos no ponderados.
Un árbol de expansión mínimo es un subgrafo en forma de árbol de un gráfico G dado , en el que mantiene todos los nodos del gráfico G pero minimiza el peso total del subgrafo. Un árbol de expansión mínimo es la forma menos costosa de mantener el tamaño de un componente conectado . La limitación significativa de este algoritmo es que simplifica demasiado la estructura de la red ( gráfico ). El árbol de expansión mínimo destruye los ciclos locales, coeficientes de agrupamiento que suelen estar presentes en redes reales y se consideran importantes en la medición de redes.
Un gráfico ponderado se puede reducir fácilmente a un subgráfico en el que el peso de cualquiera de los bordes es mayor que un umbral determinado w c . Esta técnica se ha aplicado para estudiar la resistencia de las redes tróficas [3] y las redes funcionales que conectan los sitios correlacionados del cerebro humano. [4] El inconveniente de este método es que ignora los nodos con poca fuerza. En redes reales, tanto la distribución de fuerza como de peso en general siguen distribuciones de colas pesadas que abarcan varios grados de magnitud. La aplicación de un límite de peso simple eliminará toda la información debajo del límite.
En la ciencia de redes , la fuerza notada como s i de un nodo i se define como s i = Σ j w ij , donde w ij es el peso del vínculo entre i y j .
Para aplicar el algoritmo de filtro de disparidad sin pasar por alto los nodos con baja intensidad, un peso normalizado p ij se define como p ij = w ij / s i . En el modelo nulo, los pesos normalizados de un cierto nodo con grado k se generan así: k - 1 pines se asignan aleatoriamente entre el intervalo 0 y 1. El intervalo luego se divide en k subintervalos. La longitud del subintervalo representa el peso normalizado de cada enlace en el modelo nulo.