Measuring the vulnerability in networks: a heuristic approach

BERBERLER M. E., BERBERLER Z. N.

ARS COMBINATORIA, cilt.135, ss.3-15, 2017 (SCI-Expanded) identifier identifier

  • Yayın Türü: Makale / Tam Makale
  • Cilt numarası: 135
  • Basım Tarihi: 2017
  • Dergi Adı: ARS COMBINATORIA
  • Derginin Tarandığı İndeksler: Science Citation Index Expanded (SCI-EXPANDED), Scopus
  • Sayfa Sayıları: ss.3-15
  • Anahtar Kelimeler: Network vulnerability, Integrity, Heuristics, COMPLEX NETWORKS, GRAPHS
  • Dokuz Eylül Üniversitesi Adresli: Evet

Özet

The integrity of a graph G = (V, E) is defined as I(G) = min {vertical bar S vertical bar + m(G - S): S subset of V(G)}, where m(G - X) denotes the order of the largest component in the graph G - X. This is a better parameter to measure the stability of a network, as it takes into account both the amount of work done to damage the network and how badly the network is damaged. Computationally it belongs to the class of intractable problems known as NP - hard. In this paper we develop a heuristic algorithm to determine the integrity of a graph. Extensive computational experience on 88 randomly generated graphs ranging from 20% to 90% densities and from 100 to 200 vertices has shown that the proposed algorithm is very effective.