Network repair based on community structure

School of Electronic and Information Engineering, Beihang University - 100191 Beijing, China and Beijing Key Laboratory for Network-based Cooperative ATM - 100191 Beijing, China

Received: 27 February 2017
Accepted: 1 August 2017

Abstract

Real-world complex systems are often fragile under disruptions. Accordingly, research on network repair has been studied intensively. Recently proposed efficient strategies for network disruption, based on collective influence, call for more research on efficient network repair strategies. Existing strategies are often designed to repair networks with local information only. However, the absence of global information impedes the creation of efficient repairs. Motivated by this limitation, we propose a concept of community-level repair, which leverages the community structure of the network during the repair process. Moreover, we devise a general framework of network repair, with in total six instances. Evaluations on real-world and random networks show the effectiveness and efficiency of the community-level repair approaches, compared to local and random repairs. Our study contributes to a better understanding of repair processes, and reveals that exploitation of the community structure improves the repair process on a disrupted network significantly.