umu.sePublications
Change search
ReferencesLink to record
Permanent link

Direct link
Variable-order Markov Model for Community Detection
Umeå University, Faculty of Science and Technology, Department of Physics.
2016 (English)Independent thesis Advanced level (degree of Master (Two Years)), 20 credits / 30 HE creditsStudent thesisAlternative title
Adaptiv Markovmodell för natverksklustring (Swedish)
Abstract [en]

To better understand complex systems, researchers analyze interactions in physical or bio-logical systems with network models. To model dynamics on the networks, such as passen-gers moving between airports or citation flows among scientific journals, they use methods that only account for information about the current position. Recent research shows that systems can be described more accurately by also including information about previous po-sitions with higher order Markov models, thereby including memory effects. For simplifying and highlighting important structures in the networks, the clustering algorithm Infomap can take advantage of this extra information to, for example, find overlapping communities. How-ever, the memory representation with state nodes leads to an explosion of possible solutions and is infeasible for anything but small networks. We solve this problem by introducing a variable-order Markov model; we merge similar state nodes in a pre-clustering step with a flexible algorithm. The algorithm builds on information theory and aggregates state nodes with similar properties until the global increase in conditional entropy reaches a certain limit. We use cross validation to statistically determine the aggregation limit and can in this way avoid under- or over-fitting with the variable-order Markov model. We validate the method with three different real-world systems and show that the method produces as good results as the full-order method more than ten times faster. This make it possible to analyze systems with higher order information that were considered infeasible and opens up a new horizon for researchers in the many fields that rely on network models.

Abstract [sv]

För att bättre förstå komplexa system studerar forskare interaktionsmönster i fysiska och biologiska system med nätverksbaserade modeller. För att beskriva dynamiken i nätverken, exempelvis passagerare som reser mellan flygplatser eller citeringsmönster i vetenskapliga tidskrifter, använder man metoder som bara tar tillvara på den nuvarande positionen i flödet. Ny forskning visar att dessa system bättre kan beskrivas genom att inkludera historiken med högre ordningens Markov-modeller genom att inkludera minneseffekter. För att förenkla och hitta viktiga strukturer i nätverk används klustringsalgoritmen Infomap, som tar tillvara på denna extra information för att hitta överlappande moduler. Denna minnesrepresentation leder dock till en explosion av möjliga lösningar och fungerar därför bara för små nätverk. Vi löser detta problem genom att aggregera liknande tillståndsnoder innan klustringen med en ny flexibel algorithm. Algoritmen bygger på informationsteoretiska resultat och aggregerar noder med liknande egenskaper till dess att den globala ökningen i den villkorliga entropin når ett särskilt gränsvärde. Vi använder korsvalidering för att hitta gränsvärdet och använder detta för att undvika över- och underanpassning. Vi validerar metoden med 3 olika verkliga system och visar att att den hittar lika bra lösningar som en explicit högre ordningens metod mer än 10 gånger snabbare. Detta gör det möjligt att analysera system med högre ordningens information som tidigare inte var möjligt och öppnar därmed upp helt nya möjligheter för forskare i områden som bygger på nätverksanalys.

Place, publisher, year, edition, pages
2016.
National Category
Other Physics Topics
Identifiers
URN: urn:nbn:se:umu:diva-114478OAI: oai:DiVA.org:umu-114478DiVA: diva2:896070
Subject / course
Examensarbete i teknisk fysik
Educational program
Master of Science Programme in Engineering Physics
Presentation
2015-06-06, 13:05 (Swedish)
Supervisors
Examiners
Available from: 2016-01-20 Created: 2016-01-20 Last updated: 2016-01-20Bibliographically approved

Open Access in DiVA

No full text

By organisation
Department of Physics
Other Physics Topics

Search outside of DiVA

GoogleGoogle Scholar
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: 53 hits
ReferencesLink to record
Permanent link

Direct link