Full Record

New Search | Similar Records

Title Heuristics for the Critical Node Detection Problem in Large Complex Networks
Publication Date
Date Accessioned
Discipline/Department Department of Computer Science
University/Publisher Brock University
Abstract Complex networks have recently attracted a significant amount of research attention due to their ability to model real world phenomena. One important problem often encountered is to limit diffusive processes spread over the network, for example mitigating pandemic disease or computer virus spread. A number of problem formulations have been proposed that aim to solve such problems based on desired network characteristics, such as maintaining the largest network component after node removal. The recently formulated critical node detection problem aims to remove a small subset of vertices from the network such that the residual network has minimum pairwise connectivity. Unfortunately, the problem is NP-hard and also the number of constraints is cubic in number of vertices, making very large scale problems impossible to solve with traditional mathematical programming techniques. Even many approximation algorithm strategies such as dynamic programming, evolutionary algorithms, etc. all are unusable for networks that contain thousands to millions of vertices. A computationally efficient and simple approach is required in such circumstances, but none currently exist. In this thesis, such an algorithm is proposed. The methodology is based on a depth-first search traversal of the network, and a specially designed ranking function that considers information local to each vertex. Due to the variety of network structures, a number of characteristics must be taken into consideration and combined into a single rank that measures the utility of removing each vertex. Since removing a vertex in sequential fashion impacts the network structure, an efficient post-processing algorithm is also proposed to quickly re-rank vertices. Experiments on a range of common complex network models with varying number of vertices are considered, in addition to real world networks. The proposed algorithm, DFSH, is shown to be highly competitive and often outperforms existing strategies such as Google PageRank for minimizing pairwise connectivity.
Subjects/Keywords Complex networks, Heuristic, Critical node detection, Network model
Language en
Country of Publication ca
Record ID handle:10464/4984
Repository brock
Date Retrieved
Date Indexed 2020-05-01
Issued Date 2013-09-12 00:00:00

Sample Search Hits | Sample Images

…Gene Disease, and Bipartite Disease networks when k = 50% . . . . . . . . . . . . . . . . . . . . . 129 Chapter 1 Introduction The main objective of this thesis is to develop efficient heuristics for the critical node detection problem (CNDP…

…size needs to be taken into consideration. Removing nodes randomly from a graph and studying effects of such removals on connectivity of graph has been studied extensively for regular graphs [16]. However, many critical node detection problems…

…x5B;23, 24], and the diameter [2]). Although variants of the critical node detection problem have been studied before, this thesis focuses on a recently proposed CNDP [4]. Borgatti [17] proposed a new definition…

…of critical node based on pairwise connectivity after removing a certain number of nodes from a network. This problem was later formally defined by Aruleslvan et al. [4] and it was called the critical node detection problem (CNDP)…

critical node" definition are given. 2.1 Graphs A graph G = (V, E ) is a pair (V ,E ) such that V is the set of vertices and E is the set of edges, where each edge is an unordered pair of vertices from set V . The number of…

…BACKGROUND 9 2.2 The Critical Node Detection Problem The critical node detection problem was formally defined by Aruleslvan et al. [4] in 2009. This definition was derived from the work done by Borgatti who studied critical node detection based on…

…x28;2.4) So the critical node detection problem can be defined as: Mi ni mi ze ui j (2.5) i , j ∈V sub j ect t o u i j + v i + v j ≥ 1, ∀(i , j ) ∈ E , (2.6) u i j + u j w − u kw ≤ 1, ∀i , j , w ∈ V, (2.7…

…was aimed to find the most suitable properties that help to indicate the critical nodes of a graph in the context of the CNDP. 2.4.1 Cut vertices, Bridges, and Biconnected-components A node v of a graph G is a cut vertex if removing node v and its…