Um estudo de modelagem e computação do índice de frustração em redes sinalizadas

Resumo Calcular o índice de frustração de um grafo sinalizado é um passo chave para resolver problemas em muitos campos, incluindo redes sociais, ciência política, física, química e biologia. O índice de frustração determina a distância de uma rede em relação a um estado de equilíbrio estrutural total. Embora a definição do índice de frustração remonte à década de 1950, sua computação algorítmica exata, que está intimamente relacionada a problemas clássicos de grafo NP-difíceis, tornou-se um foco apenas nos últimos anos. Desenvolvemos três novos modelos de programação linear binária para calcular o índice de frustração de maneira exata e eficiente como a solução para um problema de otimização global. Resolvendo os modelos com ramificação priorizada e desigualdades válidas no Gurobi, podemos calcular o índice de frustração de redes sinalizadas reais com mais de 15.000 arestas em menos de um minuto em hardware de baixo custo. Fornecemos uma extensa análise de desempenho para redes sinalizadas aleatórias e reais e mostramos que nossos modelos superam todas as abordagens existentes por grandes fatores. Com base no tempo de resolução, saída do algoritmo e fator de ramificação efetivo, destacamos a superioridade de nossos modelos em relação a métodos exatos e heurísticos na literatura.