Agglomeration based network analysis

Networks are used to model different systems such as chemical systems, artificial neural networks, social systems or the internet and the World Wide Web. A communication network is composed of processing nodes and links connecting these nodes. Graph theory is a powerful mathematical tool in the design and analysis of the architecture of a communication network. If the underlying topology of a communication network is modeled by a graph, the node set of the graph corresponds to processors and the edge set of the graph corresponds to communication links in the network. Damage to an important node in the network in most cases results in damage to the entire network. Therefore identifying the important nodes helps to increase the sustainability and robustness of the complex networks by preserving the fundamental nodes. To solve the problem of determining the importance of nodes in complex networks a method of node contraction based on agglomeration is proposed. In this thesis agglomeration of cycle, path and related graphs are evaluated and then importance of nodes of the related graphs is determined by the use of contraction operation. A polinomial time algorithm which determines the importance of the nodes of a graph is proposed.