Receive a 20% Discount on All Purchases Directly Through IGI Global's Online Bookstore

Vahid Khalilpour Akram (Ege University, Turkey) and Orhan Dagdeviren (Ege University, Turkey)

DOI: 10.4018/978-1-4666-9964-9.ch002

Chapter Preview

TopThe connectivity is one of the key properties in all networks. A network is said to be connected if there is at least one path between every node. Most of the computer networks such as LANs and WANs have communication infrastructures (e.*g*. cables, switches and routers) and provide high reliability from the connectivity perspective. However it is not possible to prepare a communication infrastructure in all environments, whereas using ad hoc or mobile wireless sensor networks is inevitable or affordable in some applications. In this kind of networks there is no communication infrastructure and all nodes communicate with each other using some intermediate nodes. These kinds of networks provide lower connection reliability, because failure in some nodes can cut off the packet flow in the network.

A network is called 1-connected if there is at least one path between every pair of nodes and there exists at least one node, which its removal, divides the network to separated segments. Such a node is called *cut vertex*. Having a 1-connected topology puts the network in high division risk. There are many researches that have been made to find and resolve the cut vertices in a network (Atay & Bayazit, 2010)(Dagdeviren & Akram, 2014)(Tarjan, 1972). In ad hoc and wireless sensor networks, for example, the nodes typically are battery powered and it is possible that some nodes die due to energy consumptions caused by packet transmissions. A *k*-connected network can tolerate and remain connected if *k*-1 arbitrary nodes stop working. Figure 1 shows a network with *k*=2. The nodes that their removal from graph decrease *k* are referred as *MinCut* set. In Figure 1 the red nodes with thick circles belong to *MinCut* set and removing any of them can reduces the disjoint path count while a failure in normal (black) nodes does not affect *k*.

The following symbols and terms have been used to explain and analysis the proposed algorithms in the next sections.

*•*The network is modeled as an undirected graph

*G=(V,E)*where*V*is the set of vertices that represents the nodes and*E*is the set of edges that indicates the links between nodes.*•**d*indicates the number of links connected to_{v}*v*or the degree of*v*in*G*.*•**d*is the minimum degree of*G*. It means that all nodes in*G*have at least*d*neighbors.*•**D*is the network diameter which is the length of the longest short path between two nodes.*•*∆ is the maximum degree in

*G*. So we have ∆=max(*d*:_{v}*v*∈*V*).

Generally most of the networks in real systems do not follow neither a specific topology pattern nor a random graph model such as Erdos and Renyi model (Erdos,1959). These kinds of the networks, which are referred as complex networks, have the most frequency in the biological, social and technological networks (Newman, 2003). Although complex networks have no regular structure or randomness, they have some common properties which are used as metrics to analyze them. These properties provide a global view of the network structure and usually affect each other or network functionality in various ways. In this section some of the key properties of complex networks and their effect on connectivity are presented.

Search this Book:

Reset