University of Ioannina
Ανάλυση, μοντελοποίηση και προσομοίωση αναζήτησης σε σύνθετα δυναμικά δίκτυα
Abstract
dc:descriptionComplex networks are present everywhere in the real world, coming from different fields (science, nature, technology, society), in various scales and with a variety of forms. These systems arise and evolve by following simple rules defined through the interactions between the participating entities. They are considered complex because of the complicated mechanics of their creation and evolution, because of the dynamic processes that take place within them and because of the huge amount of information required to identify them. Tools from network science are used to describe, reproduce and quantify them and also, to help us to understand and predict their behavior as well as the behavior of the dynamic processes that occur within them.Search is one of the fundamental issues in complex networks with practical application in various contexts, such as finding a target or locating a person in a social network or discovering a desired resource. Search is a dynamic process that unfolds by transmitting messages from node to node. When there is global knowledge of the network, search is focused on finding the most appropriate route based on some criterion (eg. transition costs). In the absence of information about the network structure, search in these systems is a blind procedure, possibly using only local information. The aim of this dissertation is to design and develop models and techniques that will contribute in two directions: a) towards the study of the search process both analytically and experimentally, and b) towards investigating their applicability in complex networks. We focus on static or dynamic unstructured networks where connections between nodes are governed by random rules, and on search mechanisms based on flooding. We start by studying and analyzing the behavior of flooding with respect to unnecessarily produced traffic (duplicate messages) and provide simple bounds and approximate models to assess the associated overheads and network coverage. Our primary objective is the elimination of overheads that emanate from the overlay network topology itself and the multiplicity of paths among nodes. We then propose novel probabilistic search algorithms that exploit network features and metrics, such as the nodes degrees. The decision of a node to propagate a message (or not) is based on both the popularity of resources and an estimation of network coverage. Based on these parameters we adjust the forwarding probability at the time a node receives the query message so as to reduce the duplicate message overhead while maintaining a high probability of query success. To study the search problem experimentally, we consider a comprehensive framework which includes the network topology, the resources and the searching strategies. We design and develop a novel, general-purpose simulator, called Armonia. It provides implementations for a wide suite of models and algorithms found in the literature related to network topology generation, search strategies and resources allocation and placement policies. Finally, we use our simulation framework to evaluate our proposed algorithms. We apply our strategies in static and dynamic networks using well-known network models and data sets coming from real networks. The observed results confirm the effectiveness of our mechanisms and their superiority with respect to the other known strategies.
Degree
thesis:*- Grantor dc:publisher
- University of Ioannina
- Year dc:date
- 2017
Author and committee
dc:creator, dc:contributor.*- Authors dc:creator
-
- Margariti, Spiridoula
- Μαργαρίτη, Σπυριδούλα
Subjects
dc:subject × 32- Αναζήτηση
- Σύνθετα δίκτυα
- Κατανεμημένα συστήματα
- διπλότυπα μηνύματα
- Πλημμύρα
- πιθανοτική πλημμύρα
- Δίκτυα άνευ κλίμακας
- αδόμητα δίκτυα p2p
- τυχαία δίκτυα
- Δυναμικά δίκτυα
- πρωτόκολλα αναζήτησης
- Προσομοίωση
- Search
- Complex networks
- Distributed systems
- duplicate messages
- Flooding
- Probabilistic flooding
- unstructured p2p networks;
- random networks
- power-law networks
- Dynamic networks
- search protocols
- Simulation
- Φυσικές Επιστήμες
- Επιστήμη Ηλεκτρονικών Υπολογιστών και Πληροφορική
- Επιστήμες Μηχανικού και Τεχνολογία
- Επιστήμη Ηλεκτρολόγου Μηχανικού, Ηλεκτρονικού Μηχανικού, Μηχανικού Η/Υ
- Natural Sciences
- Computer and Information Sciences
- Engineering and Technology
- Electrical Engineering, Electronic Engineering, Information Engineering
Rights
- Language dc:language
- gre
Identifiers
dc:identifier.*- Identifier
- 10.12681/eadd/43263