Digitala Vetenskapliga Arkivet

Change search
CiteExportLink to record
Permanent link

Direct link
Cite
Citation style
  • apa
  • ieee
  • modern-language-association-8th-edition
  • vancouver
  • Other style
More styles
Language
  • de-DE
  • en-GB
  • en-US
  • fi-FI
  • nn-NO
  • nn-NB
  • sv-SE
  • Other locale
More languages
Output format
  • html
  • text
  • asciidoc
  • rtf
Multi-scale clustering in graphs using modularity
KTH, School of Electrical Engineering and Computer Science (EECS).
2019 (English)Independent thesis Advanced level (degree of Master (Two Years)), 20 credits / 30 HE creditsStudent thesisAlternative title
Multiskal-klustring i grafer med moduläritet (Swedish)
Abstract [en]

This thesis provides a new hierarchical clustering algorithm for graphs, named Paris, which can be interpreted through the modularity score and its resolution parameter. The algorithm is agglomerative and based on a simple distance between clusters induced by the probability of sampling node pairs. It tries to approximate the optimal partitions with respect to the modularity score at any resolution in one run.

In addition to the Paris hierarchical algorithm, this thesis proposes four algorithms that compute rankings of the sharpest clusters, clusterings and resolutions by processing the hierarchy output by Paris. These algorithms are based on a new measure of stability for clusterings, named sharp-score. Key outcomes of these four algorithms are the possibility to rank clusters, detect sharpest clusterings scale, go beyond the resolution limit and detect relevant resolutions.

All these algorithms have been tested on both synthetic and real datasets to illustrate the efficiency of their approaches.

Abstract [sv]

Denna avhandling ger en ny hierarkisk klusteralgoritm för grafer, som heter Paris, vilket kan tolkas av modularitetsresultatet och dess upplösningsparameter. Algoritmen är agglomerativ och är baserad på ett enda avstånd mellan kluster som induceras av sannolikheten för sampling av nodpar. Det försöker att approximera de optimala partitionerna vid vilken upplösning som helst i en körning.

Förutom en hierarkisk algoritm föreslår denna avhandling fyra algoritmer som beräknar rankningar av de bästa grupperna, kluster och resolutioner genom att bearbeta hierarkiproduktionen i Paris. Dessa algoritmer bygger på ett nytt koncept av klusterstabilitet, kallad sharpscore. Viktiga resultat av dessa fyra algoritmer är förmågan att rangordna kluster, upptäcka bästa klusterskala, gå utöver upplösningsgränsen och upptäcka de mest relevanta resolutionerna.

Alla dessa algoritmer har testats på både syntetiska och verkliga datamängder för att illustrera effektiviteten i deras metoder.

Place, publisher, year, edition, pages
2019.
Series
TRITA-EECS-EX ; 2019:11
Keywords [en]
Hierarchical clustering, Multi-scale clustering, Graph, Modularity, Resolution, Dendrogram
National Category
Computer Sciences
Identifiers
URN: urn:nbn:se:kth:diva-244847OAI: oai:DiVA.org:kth-244847DiVA, id: diva2:1292782
External cooperation
Télécom Paris Tech
Educational program
Master of Science in Engineering - Computer Science and Technology
Supervisors
Examiners
Available from: 2019-03-05 Created: 2019-03-01 Last updated: 2019-03-05Bibliographically approved

Open Access in DiVA

fulltext(19311 kB)115 downloads
File information
File name FULLTEXT01.pdfFile size 19311 kBChecksum SHA-512
0d83341757916de0f5b8702fde5d4ee666a23a2632771b79d4493f6e13d49a2e1881ddc1866f514e0958601857ea1e392243643edac03233938d9ca093422fb5
Type fulltextMimetype application/pdf

By organisation
School of Electrical Engineering and Computer Science (EECS)
Computer Sciences

Search outside of DiVA

GoogleGoogle Scholar
Total: 115 downloads
The number of downloads is the sum of all downloads of full texts. It may include eg previous versions that are now no longer available

urn-nbn

Altmetric score

urn-nbn
Total: 417 hits
CiteExportLink to record
Permanent link

Direct link
Cite
Citation style
  • apa
  • ieee
  • modern-language-association-8th-edition
  • vancouver
  • Other style
More styles
Language
  • de-DE
  • en-GB
  • en-US
  • fi-FI
  • nn-NO
  • nn-NB
  • sv-SE
  • Other locale
More languages
Output format
  • html
  • text
  • asciidoc
  • rtf