Change search
ReferencesLink to record
Permanent link

Direct link
Community Detection in Imperfect Networks
Umeå University, Faculty of Science and Technology, Department of Physics.
2011 (English)Independent thesis Advanced level (degree of Master (Two Years)), 20 credits / 30 HE creditsStudent thesis
Abstract [en]

Community detection in networks is an important area of current research with many applications. Finding community structures is a challenging task and despite significant effort no satisfactory method has been found. Different methods find different communities in the same network and with different computational requirements. To counter this problem, several different methods are often used and the results compared manually. In this thesis, we present three different methods to instead merge the results from different methods (or several runs from the same algorithm) to find better estimates of the community structure.

Another problem in practical applications is noisy and imperfect networks with missing and false edges. These imperfections are natural results from the methods used to map the network structure and are often difficult to eliminate. In this thesis, we apply a Monte Carlo-sampling method in combination with the introduced methods for merging community detection results to find community structures in such networks. The method is tested by simulation studies on both real-world networks and synthetic networks with generated uncertainties and imperfections. We finally demonstrate how it is possible to generate confidence levels of the obtained community structure from the merging methods. This allows for a qualitative comparison of the robustness and significance of the network clustering.

Abstract [sv]

Identifikation av grupperingar i nätverk är ett viktigt område inom aktuell forskning med många olika tillämpningsområden. Att finna grupperingar är ofta svårt och trots betydande ansträngningar har ingen tillfredsställande metod hittats. Olika metoder finner ofta olika grupperingar i samma nätverk och kräver varierande beräkningskraft. För att hantera dessa problem används ofta flera metoder vartefter resultaten jämförs manuellt. I detta examensarbete presenterar vi tre olika metoder att istället slå samman resultat från olika metoder (eller fler körningar från samma algoritm) för att hitta bättre uppskattningar av grupperingarna.

Ett annat problem i praktiska tillämpningar är brus och ofullständiga nätverk med saknade och falska kanter. Dessa brister är naturliga resultat från de metoder som används för att kartlägga nätverketstrukturen och det är ofta svåra att eliminera dessa. I detta examensarbete använder vi Monte Carlo-metoder i kombination med de introducerade metoderna för att slå samman funna grupperingar för att hitta grupperingar i det osäkra nätverket. Vi testar metoden genom simuleringstudier på både verkliga och syntetiska nätverk med genererade osäkerheter och brister. Slutligen demostrerar vi hur det är möjligt att skapa konfidensnivåer för noder i grupperingar med hjälp av metoderna för sammanslagning. Detta möjliggör en kvalitativ jämförelse av stabilitet och signifikans av identifierade nätverksgrupperingar.

Place, publisher, year, edition, pages
2011.
Keyword [en]
social network analysis, imperfect networks, uncertain edges, community detection, ensemble clustering
Keyword [sv]
social nätverksanalys, ofullständiga nätverk, osäkra kanter, grupperingar, ensembleklustering
National Category
Other Physics Topics
Identifiers
URN: urn:nbn:se:umu:diva-44381OAI: oai:DiVA.org:umu-44381DiVA: diva2:420621
Subject / course
Examensarbete i teknisk fysik
Educational program
Civilingenjörsprogrammet i teknisk fysik
Presentation
2011-05-30, Universitetsklubben, Umeå universitet, Umeå, 11:00 (English)
Uppsok
Physics, Chemistry, Mathematics
Supervisors
Examiners
Available from: 2011-06-13 Created: 2011-06-03 Last updated: 2011-06-13Bibliographically approved

Open Access in DiVA

fulltext(4069 kB)1177 downloads
File information
File name FULLTEXT01.pdfFile size 4069 kBChecksum SHA-512
14d4db4da2737f987e6dea64a3322263d7b55631be4b915623c94631fcb214d6d6c489b5f61b7c2e528fa4bcd3383e507fbf2f38aade3e7de09a36b0c6f3bd90
Type fulltextMimetype application/pdf

By organisation
Department of Physics
Other Physics Topics

Search outside of DiVA

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

Total: 505 hits
ReferencesLink to record
Permanent link

Direct link