Advanced search options

You searched for `subject:(Critical node detection)`

. One record found.

▼ Search Limiters

1.
Edalatmanesh, Mahmood.
Heuristics for the *Critical* *Node* *Detection* Problem in Large Complex Networks
.

Degree: Department of Computer Science, 2013, Brock University

URL: http://hdl.handle.net/10464/4984

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

…heuristics for the *critical* *node*
*detection* problem (CNDP) with specific application to… …regular graphs [16]. However,
many *critical* *node* *detection* problems have been defined… …and the diameter [2]).
Although variants of the *critical* *node* *detection*… …defined by Aruleslvan et al.
[4] and it was called the *critical* *node* *detection* problem… …79].
CHAPTER 2. BACKGROUND
9
2.2 The *Critical* *Node* *Detection* Problem
The *critical*…

Record Details Similar Records

❌

APA · Chicago · MLA · Vancouver · CSE | Export to Zotero / EndNote / Reference Manager

APA (6^{th} Edition):

Edalatmanesh, M. (2013). Heuristics for the Critical Node Detection Problem in Large Complex Networks . (Thesis). Brock University. Retrieved from http://hdl.handle.net/10464/4984

Note: this citation may be lacking information needed for this citation format:

Not specified: Masters Thesis or Doctoral Dissertation

Chicago Manual of Style (16^{th} Edition):

Edalatmanesh, Mahmood. “Heuristics for the Critical Node Detection Problem in Large Complex Networks .” 2013. Thesis, Brock University. Accessed March 07, 2021. http://hdl.handle.net/10464/4984.

Note: this citation may be lacking information needed for this citation format:

Not specified: Masters Thesis or Doctoral Dissertation

MLA Handbook (7^{th} Edition):

Edalatmanesh, Mahmood. “Heuristics for the Critical Node Detection Problem in Large Complex Networks .” 2013. Web. 07 Mar 2021.

Vancouver:

Edalatmanesh M. Heuristics for the Critical Node Detection Problem in Large Complex Networks . [Internet] [Thesis]. Brock University; 2013. [cited 2021 Mar 07]. Available from: http://hdl.handle.net/10464/4984.

Note: this citation may be lacking information needed for this citation format:

Not specified: Masters Thesis or Doctoral Dissertation

Council of Science Editors:

Edalatmanesh M. Heuristics for the Critical Node Detection Problem in Large Complex Networks . [Thesis]. Brock University; 2013. Available from: http://hdl.handle.net/10464/4984

Not specified: Masters Thesis or Doctoral Dissertation