Community detection in undirected graphs using a new quality measure (Master thesis)

Κουφός, Νικόλαος


The detection of communities is of great significance in sociology, biology, computer science and other disciplines where complex systems are often represented as graphs or networks. One of the most interesting properties of graphs representing real systems is community structure, i.e. the partitioning of graph nodes into clusters, with many edges joining nodes of the same cluster and comparatively few edges joining nodes of different clusters. This hard but important problem has attracted an increasing scientific interest over the past few years and several techniques have been proposed, especially for the case where the number of communities is not known in advance. The most popular family of community detection methods is based on the optimization of the so called ‘modularity’ criterion using various clustering approaches. The modularity of a community is defined as fraction of the edges that fall within a given group minus the expected fraction if edges were distributed at random. However, it has been shown that modularity has several drawbacks, such as for example the ‘resolution limit’, i.e., it is unable to detect small communities. We introduce a new quality measure to evaluate a partitioning of a graph into communities that is called ‘inclusion’. This quality measure evaluates how well each node is ‘included’ in its community by considering both its existing and its non-existing edges. We have implemented several techniques to optimize the inclusion criterion. A first technique follows the agglomerative principles, as it starts with every node in a separate community and iteratively merges communities so that inclusion is improved. A second technique is similarly initialized, but instead of community merging, it improves the inclusion of the partitioning by moving each time a single node to another community. Another method is based on evaluating the solutions provided by spectral clustering. In the experimental evaluation we conducted, it has been shown that the inclusion measure is very effective in evaluating communities and usually leads to improved community detection results without requiring the a-priori specification of the number of communities.
Institution and School/Department of submitter: Πανεπιστήμιο Ιωαννίνων. Σχολή Θετικών Επιστημών. Τμήμα Μηχανικών Η/Υ & Πληροφορικής
Subject classification: Graphic methods
Keywords: Graphic methods,Quality measures,Datasets & results
URI: http://olympias.lib.uoi.gr/jspui/handle/123456789/28760
Appears in Collections:Διατριβές Μεταπτυχιακής Έρευνας (Masters)

Files in This Item:
File Description SizeFormat 
Μ.Ε. ΚΟΥΦΟΣ ΝΙΚΟΛΑΟΣ 2017.pdf1.15 MBAdobe PDFView/Open



 Please use this identifier to cite or link to this item:
http://olympias.lib.uoi.gr/jspui/handle/123456789/28760
  This item is a favorite for 0 people.

Items in DSpace are protected by copyright, with all rights reserved, unless otherwise indicated.