Μελέτη Τοποθέτησης Υπηρεσιών σε Δικτυοκεντρικά Περιβάλλοντα με Αλγεβρική Θεωρία Γράφων
Date Issued
June 21, 2019
Type
Πτυχιακή Εργασία
Abstract
Ιn the 21st century we are in the Ιnformation Αge. An important role in shaping it has been computer networks. Changing the way we share information and services. In our everyday life we enjoy and use several services.
An important problem that we encounter is the Fasility Location and more specifically the case of 1-median. The 1-median problem is a special category of the p-median problem. The problem is NP-hard on general graphs and networks for an arbitrary p (where p is a variable). Polynomial time algorithms exist for arbitrary p when the network is a tree. The aim of the thesis is to study where to place the service on the network and how close we are to the optimal solution using Algebraic Graph Theory. The optimal solution for the 1-median is given by Closeness centrality however there are other centrality measures such as Degree and Εigenvector centrality which provide approaches for optimal solution. For the comparison of the measures, we constructed networks consisting of geometric random with 1000 nodes. For the evaluation of the measures we have defined the concept of total cost for the network and and compared the computation time of each measure. Τhe results of Εigenvector centrality
with use of Power Method is interesting because it has a very good approach to the placement of the service with a small computation time.
Subjects