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
Decentralized Diffusion-Controlled Algorithm for Community Detection: Initialization and Resolution Study
KTH, School of Information and Communication Technology (ICT).
2017 (English)Independent thesis Advanced level (degree of Master (Two Years)), 20 credits / 30 HE creditsStudent thesis
Abstract [en]

Community detection in graphs has been an important research topic for many fields. The aim of community detection is to extract from graphs those groups of nodes that present more connections between them than with the rest of the network. Detecting such groups at different scales can help understanding the global behaviour of the system. However, recent studies have shown that realworld graphs follow power-law distributions for degree and community sizes. Specifically, these graphs present many small communities but just a few large ones. This unbalanced community size distribution poses a great challenge for community detection algorithms.Most of the existing methods are based on global approaches that require information about the network to be processed as a whole. Thus, those techniques can not be applied when the graph is too big to fit into one single machine, or in distributed setting when the graph is partitioned among multiple machines. To solve this limitations, a completely decentralized community detection algorithm is presented. It is based on diffusion, following a vertex-centric approach that allows each node to decide the diffusion rates based on local information. It adds as well a mechanism for controlling the diffusion speed through a customizable function.We evaluate the algorithm with a variety of graphs with different levels of imbalance and community structures. Our algorithm is able to detect (almost) perfectly the communities when the imbalance between community sizes is not extreme. We show as well how the sizes of the detected communities can be controlled by the diffusion strategy, allowing for better detection of finer or coarser resolutions in hierarchical graphs. The algorithm is also compared to other two well-known existing methods, achieving similar results in most of the cases though with a higher computation time.

Abstract [sv]

Gemenskap detektering i grafer har varit ett viktigt forsknings ämne förmånga områden. Gemenskapsdetekterings syftet är att extrahera ur grafernade grupper av noder som har mer kopplingar mellan varandra än med restenav nätverket. Att upptäcka sådana grupper i olika skaler kan hjälpa till att förstå systemets globala beteende. Däremot har nyliga studier visat att verkliga grafers grad och gemenskap storlek följer en potenslagen fördelning. Specifikt,dessa grafer uppvisar många små gemenskaper men bara några stora. Denhär obalanserade gemenskaps storleks fördelningen utgör en stor utmaning för gemenskapsdetekterings algoritmer.De flesta av de befintliga metoderna är baserade på globala tillvägagångssätt som kräver att information om nätverket behandlas som helhet. Således kan dessa tekniker inte tillämpas när grafen är för stor för att passa in i en enda maskin, eller på distribuerat sätt när grafen är uppdelad bland flera maskiner. För att lösa dessa begränsningar, uppvisas en helt decentraliserad gemenskapsdetekterings algoritm.Denär baserad pådiffusion som följer en vertex-centrerad tillvägagångssätt.Varje node valder diffusionshastigheten baserad på lokal information. Deninnehåller även en mekanism som kontrollerar diffusionens hastighet genom en anpassningsbar funktion.Vi utvärderar algoritmen genom flera olika grafer med olika nivåer av obalans och gemenskaps strukurer. Vår algoritm kan (nästan) felfritt upptäcka gemenskaper där obalansen mellan dem inte är för stor. Vi visar även hur storlekenpå de hittade gemenskaperna kan kontrolleras genom diffusions strategin, somtillåter bättre uptäckt av finare eller grövre resolution av hierarkiska grafer. Algoritmen kan också jämföras med två befintliga, välkända metoder, vilka ger liknande resultat i de flesta fallen men tar längre tid att genomföra.

Place, publisher, year, edition, pages
2017. , p. 75
Series
TRITA-ICT-EX ; 2017:154
Keywords [en]
community detection; unbalanced communities; adaptive diffusion; decentralized algorithm
Keywords [sv]
Gemenskap detektering, obalanda gemenskaper, adaptativ diffusion, decentraliserad algoritm
National Category
Computer Sciences
Identifiers
URN: urn:nbn:se:kth:diva-215720OAI: oai:DiVA.org:kth-215720DiVA, id: diva2:1149120
Subject / course
Computer Science
Educational program
Master of Science - Computer Science
Supervisors
Examiners
Available from: 2017-10-13 Created: 2017-10-13 Last updated: 2018-01-13Bibliographically approved

Open Access in DiVA

fulltext(5627 kB)46 downloads
File information
File name FULLTEXT01.pdfFile size 5627 kBChecksum SHA-512
8c44151c9ed6be080864255b3db826a4a925e696d53b3b53a2a6af27c49f57c194c587ff7a2e84dad8c9b228f3a4371fd63735c08705431f2bd7fc14650dbd0d
Type fulltextMimetype application/pdf

By organisation
School of Information and Communication Technology (ICT)
Computer Sciences

Search outside of DiVA

GoogleGoogle Scholar
Total: 46 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: 67 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