Maximizing Algebraic Connectivity of Constrained Graphs in Adversarial Environments

摘要: This paper aims to maximize algebraic connectivity of networks via topology design under the presence constraints and an adversary. We are concerned with three problems. First, we formulate concave maximization problem adding edges initial graph, which introduces a nonconvex binary decision variable, in addition subjugation general convex on feasible edge set. Unlike previous methods, our method is justifiably not greedy capable accommodating these additional constraints. also study scenario coordinator must selectively protect network from chance failure due physical disturbance or adversarial attack. The needs strategically respond adversary's action without presupposed knowledge attack actions. propose heuristic algorithms for accomplish objective identify worst-case preventive solutions. Each algorithm shown be effective simulation provide some discussion their compared performance.