En análisis de redes sociales, el índice de frustración o índice de línea es el menor número de aristas o conexiones que se deben quitar de una red signada para que esta quede estructuralmente equilibrada, entendiendo por equilibrada a una red cuyos ciclos son todos positivos (en el sentido de la multiplicación de los signos de las aristas que los conforman).

Definición Formalmente, dado un grafo signado , donde es el conjunto de vértices, el conjunto de aristas, y una función que a cada arista le asigna un peso positivo o negativo. Sea un conjunto de aristas tales que al eliminarlas, para a estar equilibrado, entonces el índice de frustración es:

Además, si , entonces el índice se puede normalizar como:

Historia Esta medida fue definida originalmente por bajo el nombre de complejidad de desequilibrio (en inglés, complexity of imbalance), como el «mínimo número de cambios de relaciones necesarias para alcanzar un equilibrio», entendiendo por «cambio de relación» al cambio de signo de una arista. Su finalidad fue evaluar el nivel de desequilibrio en una red signada de una manera más simple que el grado de equilibrio de , correspondiente a la proporción de ciclos positivos en relación al total de ciclos de la red. En paralelo, se desarrolló el equivalente índice de línea (line index), definido por como el mínimo número de aristas cuya negación (cambio de signo) o eliminación permite equilibrar la red.

Años más tarde, la medida fue rebautizada como índice de frustración por ; según , inspirado a partir del concepto de frustración de , referido a la energía mínima de un modelo de vidrio de espín de Ising.

Complejidad computacional

Desde el punto de vista de la complejidad computacional, si bien decidir si un grafo signado está equilibrado se puede hacer en tiempo polinomial, calcular el índice de frustración es en general un problema NP-hard. Sin embargo, para algunas clases de grafos específicos, el problema sí resulta polinomial; por ejemplo, para los grafos planares.

Para computar el índice de frustración de una red signada, en 1977 se diseñó un algoritmo de aproximación basado en un modelo de optimización cuadrática binaria sin restricciones, el cual ha servido de base para modelos más eficientes. Al año siguiente se propuso un algoritmo iterativo, que mediante la eliminación sucesiva de aristas para ir eliminando ciclos negativos del grafo, permite encontrar una cota superior para el índice de frustración. También existen algoritmos iterativos para calcular el índice exacto, aunque con complejidad exponencial en el número de vértices, lo que impide su ejecución práctica para redes con incluso menos de 40 vértices.

Aplicaciones

Más allá de sus aplicaciones iniciales para estudiar el equilibrio estructural en redes sociales o modelos de física de la materia condensada, el índice de frustración incide en varios otros campos.

En biología, permite determinar una descomposición óptima de redes biológicas en subsistemas monótonos. En finanzas, los portafolios se pueden representar como grafos signados, de tal modo que si poseen aristas negativas y un índice de frustración cero, se consideran de bajo riesgo. En física, corresponde al estado de energía mínimo de los imanes atómicos. En relaciones internacionales, se utiliza para analizar alianzas y antagonismos entre países. En química, se ha utilizado para evaluar la estabilidad del fullereno.

Referencias

Bibliografía

Categoría:Análisis de redes sociales Categoría:Teoría algebraica de grafos