Computing rupture degree parameters based on agglomeration operation for network security

Network security is an important issue in computing. The vulnerability is a in case the devices or connections in the network are damaged, it refers to the endurance they show until their communication is broken. In order to make this vulnerability measurement, the network must first be modeled as graphs, with devices expressed as vertices and connections as edges. The rupture degree is one the most important vulnerability parameter in networks which are modelled by graphs. Let G(V(G), E(G)) be a simple undirected graph. The rupture degree is defined by r(G) = max{W(G − S) − |S| − m(G − S): S ⊂ V(G) ve w(G − S) > 1}, where m(G − S) is the order of a largest connected component in G − S and w(G-S) is the number of components of G − S, respectively. In this thesis, we consider the vertex contraction method based on the network agglomeration operation for each vertex of graph G. Then, we have presented two graph vulnerability parameters called by agglomeration rupture degree and average lower agglomeration rupture degree. Furthermore, the exact values of them for some graph families are given. Finally, we proposed a polynomial time heuristic algorithm to obtain the values of agglomeration rupture degree and average lower agglomeration rupture degree.