Distributed local community detection in dynamic networks
Creators: name: Τζωρτζίδης, Γεώργιος Γεωργίου
Publisher: name: Aristotle University of Thessaloniki
Year: 2020
Subjects: Κατανεμημένοι υπολογισμοί
Εύρεση τοπικών κοινοτήτων
Δυναμικά δίκτυα
Distributed computations
Local community detection
Dynamic networks

description: Undeniably, the last few years’ data has evolved dramatically in type, volume and velocity - with its rapid evolution attributed to the widespread digitization of business processes at global level. Since data has become the new business currency and its further rapid increase will be key to the transformation and growth of enterprises globally, its analysis has a far-reaching impact and meaning. But how do we understand it and its benefits, along with analytics on the journey to Digital transformation? Understanding the value of Data is key to the successful implementation of operational strategies that facilitate agile and effective business growth. For many people big data means better business. Data enables future strategies and immediate change, thanks to the power of predictive analytics and advanced data science. Correctly utilizing data can improve decision making processes as well as overall customer experience. By using big data technologies, organizations and businesses can answer questions in a few seconds rather than a couple of days. This acceleration helps businesses to be more competitive, improve their performance and provide answers for complex problems or questions that have resisted analysis. In modern data analysis and specifically in graph mining, trying to detect communities is a common problem that is crucial to be tackled. Most community detection algorithms need global information of the network, which is expensive and often infeasible to obtain in large and dynamic networks. Therefore, local community detection is of great importance. This work attempts to identify local communities over periods of high internal and low external interactions and the optimal time interval in which they are actively interacting by modifying an existing algorithm called PHASR (Prune HASh and Refine) to run in an open source framework specially designed for distributed computing in clusters, Apache Spark using Scala programming language. After the application of the PHASR algorithm in various dynamic networks in Spark, local communities were discovered faster than by applying the same algorithm in a single computer - machine. As expected, by increasing the computational power we observe that the run time of the algorithm decreases. In the future, more prominence should be given in designing graph mining algorithms to run in distributed systems while we are rapidly approaching the era of dynamicity and of the highly unpredictable events.
description: Αδιαμφισβήτητα, τα τελευταία χρόνια τα δεδομένα έχουν εξελιχθεί δραματικά ως προς τον τύπο τους, τον όγκο και την ταχύτητα που παράγονται, με τη ραγδαία αυτή εξέλιξη να οφείλεται στην διάχυτη ψηφιοποίηση των επιχειρηματικών διαδικασιών σε παγκόσμιο επίπεδο. Εφόσον τα δεδομένα πλέον είναι το νέο συνάλλαγμα για τις επιχειρήσεις και η ραγδαία αύξηση τους θα αποτελέσει κλειδί για την μεταμόρφωση και την ανάπτυξη τους παγκοσμίως, η ανάλυση τους έχει εκτεταμένο αντίκτυπο και σημασία. Το ερώτημα είναι : πως αντιλαμβανόμαστε τα οφέλη από την ανάλυση τους κατα τη ψηφιακή αυτή μετάλλαξη; Η κατανόηση της αξίας των δεδομένων είναι το κλειδί για την επιτυχημένη υλοποίηση επιχειρησιακών στρατηγικών που διευκολύνουν την εύστροφη και αποτελεσματική άνθιση των επιχειρήσεων. Για πολλούς, πολλά δεδομένα σημαίνουν και καλύτερη επιχείρηση. Τα δεδομένα επιτρέπουν μελλοντικές στρατηγικές και άμεσες αλλαγές χάρη στη δύναμη των προβλέψεων και της προχωρημένης επιστήμης των δεδομένων. Η σωστή αξιοποίηση τους επιτρέπει την βελτίωση των διαδικασιών λήψης αποφάσεων και απο την άλλη την συνολική εμπειρία των πελατών. Χρησιμοποιώντας τεχνολογίες για αξιοποίηση δεδομένων μεγάλου όγκου, οι επιχειρήσεις μπορούν να απαντήσουν ερωτήματα μέσα σε λίγα δευτερόλεπτα αντι για μέρες. Αυτή η επιτάχυνση οδηγεί τις επιχειρήσεις στο να είναι πιο ανταγωνιστικές, να αυξάνουν τις επιδόσεις τους και να απαντούν περίπλοκα ερωτήματα δύσκολα στο να αναλυθούν. Στη μοντέρνα ανάλυση των δεδομένων και ιδιαίτερα στην εξόρυξη των γράφων, η ανίχνευση γειτονιών είναι ένα συχνό πρόβλημα που είναι σημαντικό να αντιμετωπιστεί. Οι περισσότεροι αλγόριθμοι ανίχνευσης γειτονιών χρειάζονται καθολικές πληροφορίες για το δίκτυο οι οποίες είναι ακριβό και πολλές φορές αδύνατο να ληφθούν σε μεγάλα και δυναμικά δίκτυα. Για το λόγο αυτό η εύρεση τοπικών γειτονιών καθίσταται απαραίτητη. Αυτή η εργασία επιχειρεί να αναγνωρίσει τοπικές κοινότητες σε περιόδους πολλών εσωτερικών και λίγων εξωτερικών αλληλεπιδράσεων καθώς και τον βέλτιστο χρονικό διάστημα για το οποίο αλληλεπιδρούν τροποποιώντας έναν υπάρχων αλγόριθμο που ονομάζεται PHASR ώστε να τρέξει σε ενα open source framework ειδικά σχεδιασμένο για κατανεμημένους υπολογισμούς σε clusters, το Apache Spark χρησιμοποιώντας τη γλώσσα προγραμματισμού Scala. Αφού εφαρμόστηκε ο αλγόριθμος σε κάποια δυναμικά δίκτυα στο Spark, ανακαλύφθηκαν τοπικές γειτονιές πιο γρήγορα από όταν έτρεξε ο αλγόριθμος σε έναν υπολογιστή. Όπως ήταν αναμενόμενο, καθώς αυξήθηκε η υπολογιστική ισχύς, παρατηρήθηκε πως ο χρόνος εκτέλεσης μειώθηκε. Μελλοντικά, κρίνεται αναγκαίο να δοθεί περισσότερη έμφαση στο σχεδιασμό αλγορίθμων εξόρυξης γράφων ώστε να μπορούν να εκτελεστούν σε κατανεμημένο περιβάλλον καθώς πλησιάζει μια δυναμική και εξαιρετικά απρόβλεπτη εποχή.