In the last decade, network analysis attracted the interest of analysts in exploring topological shapes, properties and features of real-world netowrks. Knowledge of the network properties allows to analyse the characteristics of the network function. For instance, the topology of a social network affects the spread of information and its stability. A point of interest is the assessment of robustness and resistance of networks after nodes deletion. Suitable metrics can be used to characterize global network sensitivity and vulnerability to local changes. In our study we use the Bienenstock & Bonacich (2004) network robustness measure as a fitness function and look for subsets of the original network whose deletion most affects the network connectivity. The problem can be described as to find the smallest set of nodes whose deletion has the highest impact on the efficiency criterion. Genetic Algorithms (GA) are powerful heuristics for attacking NP-hard problems. In a very general way, a GA mimics the principles of natural selection (crossover, mutation, selective pressure) to solve problems. Because GA implements other optimization methods to help finding good starting points, we can then use traditional optimization techniques to refine solution. An application to innovative networks is provided.
A genetic algorithm to evaluate the effect of topology on network resilience
GIORDANO, Giuseppe;
2011-01-01
Abstract
In the last decade, network analysis attracted the interest of analysts in exploring topological shapes, properties and features of real-world netowrks. Knowledge of the network properties allows to analyse the characteristics of the network function. For instance, the topology of a social network affects the spread of information and its stability. A point of interest is the assessment of robustness and resistance of networks after nodes deletion. Suitable metrics can be used to characterize global network sensitivity and vulnerability to local changes. In our study we use the Bienenstock & Bonacich (2004) network robustness measure as a fitness function and look for subsets of the original network whose deletion most affects the network connectivity. The problem can be described as to find the smallest set of nodes whose deletion has the highest impact on the efficiency criterion. Genetic Algorithms (GA) are powerful heuristics for attacking NP-hard problems. In a very general way, a GA mimics the principles of natural selection (crossover, mutation, selective pressure) to solve problems. Because GA implements other optimization methods to help finding good starting points, we can then use traditional optimization techniques to refine solution. An application to innovative networks is provided.I documenti in IRIS sono protetti da copyright e tutti i diritti sono riservati, salvo diversa indicazione.
