Community detection in signed and directed graphs

Ψυλλάκος, Νίκος; Psyllakos, Nikos

Master Thesis

Author

Ψυλλάκος, Νίκος

Psyllakos, Nikos

Date

2021-06-27

Abstract

In recent 2 decades, one of the most popular methods for processing data, is to convert it to a network, where data units are vertices and their relations are the links that connects them. Such Networks in a clustering problem are usually represented as graphs where each element to be clustered is represented as a node and the distance between two elements is modeled by a certain weight on the edge linking the nodes. Graph clustering aims at partitioning a set of nodes into different groups called clusters or communities that share some form of similarity, similarity score can be formulated by using a distance-based criterion, a topology structural criterion or an “attitude” (polarity) criterion. These clusters will help us to explore information hidden in the data , there is a wide area of applications as e.g. Social Network Analysis, Statistical Data Analysis, Machine Learning, Data mining, Consuming Behavior Analysis, VLSI design, Computer graphics and Gene analysis. This particular Thesis is putting under the spotlight Signed and Directed graphs and examines two community detection algorithms that cluster nodes with similar characteristics, the goal of the procedure is to emerge the Similarity score as the main and most important factor of Graph Clustering between nodes based on the connectivity pattern they follow including both directionality and polarity of the links which connects them. The initial step is to work with the negative and positive subgraph of the examined Data Set. For each Subgraph we apply Coupling (Reference) and Cocitation as the Methodologies by which Directionality dominates criteria to reach Similarity and we calculate the appropriate co-citation and co-reference matrices. The Reference or bibliographic coupling Matrix of two nodes in a directed network is the number of nodes to which both these two nodes point on the other hand the Cocitation Matrix of two nodes in a directed network is the number of nodes that point to these both exact nodes. The procedure continues with the similarity Matrix calculation normalized by taking account of the degree of each node and under the influence of Amsler [Amsler, 1972] who pointed out that Co-citation and Bibliography coupling can be combined. And finally we apply two clustering algorithms affinity propagation and spectral clustering, both standalone and combined. In this Thesis, we provide a concluded implementation of these proposed algorithms in Python, and the datasets that were used to evaluate in practice their precision and certainty. We display that these two algorithms have the theoretically expected results for both random Generated signed directed graphs and real networks data sets.

Postgraduate Studies Programme

Τεχνητή Νοημοσύνη - Artificial Intelligence

Department

Σχολή Τεχνολογιών Πληροφορικής και Επικοινωνιών. Τμήμα Ψηφιακών Συστημάτων

Corporate Department

Εθνικό Κέντρο Έρευνας Φυσικών Επιστημών «Δημόκριτος»

Number of pages

Language

English

URI

https://dione.lib.unipi.gr/xmlui/handle/unipi/13613
http://dx.doi.org/10.26267/unipi_dione/1036

Collections

Τμήμα Ψηφιακών Συστημάτων

Show full item record

Except where otherwise noted, this item's license is described as
Αναφορά Δημιουργού-Μη Εμπορική Χρήση-Όχι Παράγωγα Έργα 3.0 Ελλάδα