Determinação empírica do ponto ótimo de fragmentação para redes modulares

Abstract

Muitas redes reais tendem a se organizar em estruturas de comunidades, neste trabalho é explorada a relação entre a existência dessas estruturas e a fragilidade das redes frente a remoções de nodos, também chamado de ataque. Para tanto, realizou-se todas as possíveis remoções de n nodos de redes de tamanho N, então, para cada rede, foi medido o tamanho da maior componente conectada restante depois de cada remoção. Dentre essas medidas, o menor tamanho de componente obtido representa o dano máximo possível à rede, limitado à remoção de n nodos. O conjunto de n nodos que produz tal dano é chamado de conjunto ótimo. Aplicou-se o procedimento em uma série de redes com modularidade controlada e variada, sendo a modularidade uma medida do quão bem um rede pode ser dividida em comunidades. Estes resultados foram comparados com resultados de métodos heurísticos de fragmentação de rede, em i.e., ataque Adaptativo de Alta Intermediação (HBA), Influência Coletiva (IC) e Ataque Baseado em Módulos (MBA). Por questões práticas, foram escolhidos principalmente ataques de tamanho n = 5 em redes de tamanho N = 100, devido aos limites computacionais para remoção dos nodos, aproximadamente 7.5 × 107 combinações para esse caso. Os resultados mostram que a robustez das redes, tanto para o ataque ótimo quanto para direcionados, tem uma relação inversa com a modularidade. Para modularidades inferiores a um valor crítico, todas as estratégias heurísticas estudadas são muito semelhantes a remoções aleatórias de nodos. Por outro lado, as redes são altamente vulneráveis a ataques heurísticos para modularidades superiores ao valor crítico.

Many real networks present community structure, this work explores the relationship between the existence of these structures and the fragility of networks in relation to node removals, also called attacks. All possible removals of n nodes from networks of size N were performed, and for each network the size of the largest connected component remaining after each removal was measured. Among these measures, the smallest component size obtained represents the maximum possible network damage, limited to the removal of n nodes. The set of n nodes that produces such damage is called the optimal set. The procedure was applied to a series of networks with controlled and varied modularity, which is a measure of how well defined are the communities within a network. These results were compared with results from heuristic network fragmentation methods, i.e., high betweenness adaptive attack (HBA), Collective Influence (CI), and Module Based Attack (MBA). For practical reasons, attacks of size n = 5 on networks of size N = 100 were chosen, mainly due to the computational limits for node removals, approximately 7.5 × 107 combinations in this case. The results show that network robustness under the optimal and the heurístic attacks has an inverse relation with the modularity, and that all the analised heuristic strategies are very similar to random removals for modularities below a critical value. On the other hand, networks are highly vulnerable to heuristic attacks for modularities greater than the critical value