Εξελικτικοί αλγόριθμοι σε πολύπλοκα δίκτυα

Abstract

This doctoral thesis is a research on the fields of complex networks and genetic algorithms. Open problems were studied in the section of epidemiology, network analysis and the combination of complex networks with evolutionary processes. An algorithmic library was created that provided the material for the exploration of various aspects of the fields described above.More specifically, in the section of epidemic spreading (or information diffusion) in complex networks, various techniques of immunization and vaccination were explored, in order to control the disease or the information flow in them. Also, in the same spectrum, a genetic algorithm was created for the establishment of the optimal immunization technique in different types of networks.As part of the complex network analysis, correlations between the nodes' degrees were explored, with the use of a general equation, as well as with the use of the concept of roles in complex networks. This concept constitutes a radical approach in explaining certain phenomena that the bibliography can only cover partially, if so. In an other approach of exploring the field of complex networks, certain evolutionary models were created, that constitute an innovative proposal for the creation of networks, are based in random walks and encapsulate two separate optimal stopping strategies. Here as well, the networks that are generated show interesting results.Finally, the procedure of locating extrema is analyzed, with the use of evolutionary processes in spatially structured populations on complex networks. The results that emerge from the application of the algorithm in problems such as spin - glass systems and the comparisons with simple genetic algorithms, indicate the possibility of achievement of a better exploration - exploitation tradeoff.

Η διδακτορική διατριβή με τίτλο "Εξελικτικοί Αλγόριθμοι σε Πολύπλοκα Δίκτυα" αποτελεί έργο της έρευνας πάνω στους τομείς των πολύπλοκων δικτύων και των γενετικών αλγορίθμων. Μελετήθηκαν ανοιχτά προβλήματα στο κομμάτι της επιδημιολογίας, της ανάλυσης πολύπλοκων δικτύων και του συνδυασμού των με εξελικτικές διαδικασίες. Δημιουργήθηκε μια αλγοριθμική βιβλιοθήκη η οποία παρείχε το υλικό για την εξερεύνηση διαφόρων πτυχών των παραπάνω πεδίων.Πιο συγκεκριμένα, στο κομμάτι της εξάπλωσης επιδημίας (ή διάδοσης πληροφορίας) σε πολύπλοκα δίκτυα, εξερευνήθηκαν διάφορες τεχνικές ανοσοποίησης και εμβολιασμού, με σκοπό τον έλεγχο της διάδοσης της ασθένειας ή της πληροφορίας σε αυτά. Επίσης, στο ίδιο φάσμα, δημιουργήθηκε ένας γενετικός αλγόριθμος για την εύρεση της βέλτιστης τεχνικής ανοσοποίησης σε διάφορα είδη δικτύων.Στα πλαίσια της ανάλυσης πολύπλοκων δικτύων, ερευνήθηκαν οι συσχετίσεις μεταξύ των βαθμών των κόμβων σε ένα δίκτυο, με τη χρήση μίας γενικής εξίσωσης, καθώς και με τη χρήση της έννοιας των ρόλων σε πολύπλοκα δίκτυα.Η έννοια των ρόλων των κόμβων, αποτελεί μια ριζοσπαστική προσέγγιση ερμηνείας ορισμένων φαινομένων που η μέχρι τώρα βιβλιογραφία αδυνατεί να καλύψει μερικώς ή ολικώς. Σε μία άλλη οπτική εξερεύνησης του πεδίου των πολύπλοκων δικτύων, δημιουργήθηκαν κάποια μοντέλα ανάπτυξης που αποτελούν μία καινούργια πρόταση για τη δημιουργία δικτύων, βασίζονται στους τυχαίους περιπάτους και ενσωματώνουν δύο ξεχωριστές στρατηγικές βέλτιστης στάσης. Και εδώ, τα δίκτυα που δημιουργούνται παρουσιάζουν έντονο ενδιαφέρον.Τέλος, αναλύεται η διαδικασία εύρεσης ακρότατων με τη χρήση εξελικτικών διαδικασιών με τοπολογικά δομημένους πληθυσμούς σε πολύπλοκα δίκτυα. Τα αποτελέσματα που προκύπτουν από την εφαρμογή του αλγορίθμου σε προβλήματα όπως συστήματα spin - glass και η σύγκριση που γίνεται με απλούς γενετικούς αλγόριθμους, δείχνουν την πιθανότητα επίτευξης βέλτιστου ισοζυγίου εξερεύνησης - αξιοποίησης.