Univerza v Ljubljani, Fakulteta za matematiko in fiziko

Notes

Several well known algorithms for network analysis are too slow to be used on large networks. Therefore we often decompose the network to smaller parts that are easier to handle. In doctoral disswrtation we study efficient (subquadratic) algorithms for large networks decompositions. The preamble contains some basic definitions and notations used in continuation. Algorithms for determining the partition of a given network, a greedy algorithm for improvement of a given partition, and some other types of decompositions are described. Third, fourth and the fifth chapter contain original contributions of the dissertation. In the third chapter the vertex and edge islands of networks are defined. Vertex islands is connected set of vertices having values greater then the vertices in their neighborhood. Similarly the edge islands for networks with weights on edges are defined. Efficient algorithms for determining the islands were developed and some properties of islands are proved. In the next two chapters examples of efficiently computable vertex and edge functions are developed. In the fourth chapter we study cores. The core of order ?$k$? is the maximal subgraph in which every vertex has at least ?$k$? neighbors. The cores forms nested layers of a graph, while the set of connected components of these layers is hierarchy on the set of vertices. Efficient algorithms for determining the cores are presented. The concept of cores is also generalized for networks, where we observe some other vertex functions instead of degree. It is shown that there exist an efficient algorithm for the whole class of vertex functions. In the fifth chapter the concept of graph connectivity is generalized. We define several different connectivity relations on the set of vertices (vertex and edge short cycles connectivity in undirect and direct graphs). We notice, that some of them are equivalence relations on the set of vertices, while the other determine equivalence relations on the set of lines, which give us another decomposition of a given graph.