Umeå universitets logga

umu.sePublikationer
Ändra sökning
RefereraExporteraLänk till posten
Permanent länk

Direktlänk
Referera
Referensformat
  • apa
  • ieee
  • modern-language-association-8th-edition
  • vancouver
  • Annat format
Fler format
Språk
  • de-DE
  • en-GB
  • en-US
  • fi-FI
  • nn-NO
  • nn-NB
  • sv-SE
  • Annat språk
Fler språk
Utmatningsformat
  • html
  • text
  • asciidoc
  • rtf
Mapping flows on weighted and directed networks with incomplete observations
Umeå universitet, Teknisk-naturvetenskapliga fakulteten, Institutionen för fysik. Scientific Computing Laboratory, Center for the Study of Complex Systems, Institute of Physics Belgrade, University of Belgrade, Pregrevica 118, Belgrade, Serbia.ORCID-id: 0000-0003-0124-1909
Umeå universitet, Teknisk-naturvetenskapliga fakulteten, Institutionen för fysik.ORCID-id: 0000-0001-7881-2496
Umeå universitet, Teknisk-naturvetenskapliga fakulteten, Institutionen för fysik. Gothenburg Global Biodiversity Centre, Box 461, Gothenburg, Sweden; Department of Biological and Environmental Sciences, University of Gothenburg, Carl Skottsbergs Gata 22B, Gothenburg, Sweden.ORCID-id: 0000-0001-5420-0591
Umeå universitet, Teknisk-naturvetenskapliga fakulteten, Institutionen för fysik.ORCID-id: 0000-0002-7181-9940
2021 (Engelska)Ingår i: Journal of Complex Networks, ISSN 2051-1310, E-ISSN 2051-1329, Vol. 9, nr 6, artikel-id cnab044Artikel i tidskrift (Refereegranskat) Published
Abstract [en]

Detecting significant community structure in networks with incomplete observations is challenging because the evidence for specific solutions fades away with missing data. For example, recent research shows that flow-based community detection methods can highlight spurious communities in sparse undirected and unweighted networks with missing links. Current Bayesian approaches developed to overcome this problem do not work for incomplete observations in weighted and directed networks that describe network flows. To overcome this gap, we extend the idea behind the Bayesian estimate of the map equation for unweighted and undirected networks to enable more robust community detection in weighted and directed networks. We derive an empirical Bayes estimate of the transitions rates that can incorporate metadata information and show how an efficient implementation in the community-detection method Infomap provides more reliable communities even with a significant fraction of data missing.

Ort, förlag, år, upplaga, sidor
Oxford University Press, 2021. Vol. 9, nr 6, artikel-id cnab044
Nyckelord [en]
community detection, directed and weighted networks, incomplete data, the map equation
Nationell ämneskategori
Annan fysik
Identifikatorer
URN: urn:nbn:se:umu:diva-194470DOI: 10.1093/comnet/cnab044ISI: 000797304300006Scopus ID: 2-s2.0-85128774619OAI: oai:DiVA.org:umu-194470DiVA, id: diva2:1656672
Forskningsfinansiär
Wallenberg AI, Autonomous Systems and Software Program (WASP)Knut och Alice Wallenbergs StiftelseVetenskapsrådet, 2016-00796
Anmärkning

Errata: "Correction to “Mapping flows on weighted and directed networks with incomplete observations”, Journal of Complex Networks, Volume 10, Issue 2, April 2022, cnac010, https://doi.org/10.1093/comnet/cnac010"

Tillgänglig från: 2022-05-06 Skapad: 2022-05-06 Senast uppdaterad: 2022-12-08Bibliografiskt granskad
Ingår i avhandling
1. Through the coding-lens: community detection and beyond
Öppna denna publikation i ny flik eller fönster >>Through the coding-lens: community detection and beyond
2022 (Engelska)Doktorsavhandling, sammanläggning (Övrigt vetenskapligt)
Alternativ titel[sv]
Nätverksklustring, nätverkscentralitet och länkprediktion ur ett kodningsperspektiv
Abstract [en]

We live in a highly-connected world and find networks wherever we look: social networks, public transport networks, telecommunication networks, financial networks, and more. These networks can be immensely complex, comprising potentially millions or even billions of inter-connected objects. Answering questions such as how to control disease spreading in contact networks, how to optimise public transport networks, or how to diversify investment portfolios requires understanding each network's function and working principles.

Network scientists analyse the structure of networks in search of communities: groups of objects that form clusters and are more connected to each other than the rest. Communities form the building blocks of networks, corresponding to their sub-systems, and allow us to represent networks with coarse-grained models. Analysing communities and their interactions helps us unravel how networks function.

In this thesis, we use the so-called map equation framework, an information-theoretic community-detection approach. The map equation follows the minimum description length principle and assumes complete data in networks with one node type. We challenge these assumptions and adapt the map equation for community detection in networks with two node types and incomplete networks where some data is missing. We move beyond detecting communities and derive approaches for how, based on communities, we can identify influential objects in networks, and predict links that do not (yet) exist.

Abstract [sv]

Vi lever i en värld som blir mer och mer sammanlänkad. Vart vi än tittar hittar vi nätverk: sociala nätverk, kollektivtrafiknätverk, telekommunikationsnätverk, finansiella nätverk och så vidare. Dessa nätverk kan vara oerhört komplexa och omfatta potentiellt miljoner eller till och med miljarder sammankopplade objekt. För att kunna besvara frågor som: hur kontrollerar vi sjukdomsspridning i kontaktnät, hur optimerar vi kollektivtrafiksnätverk eller hur diversifierar vi investeringsportföljer, krävs det att vi förstår varje nätverks funktion och principer.

Nätverksforskare analyserar strukturen i nätverk i jakt på kluster: grupper av objekt som är mer kopplade till varandra än till resten av nätverket. Kluster utgör byggstenarna, eller delsystemen, i nätverken och låter oss representera dessa med förenklade modeller. Att analysera kluster och deras interaktioner hjälper oss att ta reda på hur nätverk fungerar.

I denna avhandling vidareutvecklar vi den så kallade kartekvationen, en informationsteoretisk klusterdetekteringsmetod. Kartekvationen följer principen om minsta beskrivningslängd och förutsätter fullständiga data i nätverk som bara består av en typ av noder. Vi utmanar dessa antaganden och anpassar kartekvationen för klusterdetektering i nätverk som består av två typer av noder och ofullständiga nätverk där viss data saknas. Vi dyker också djupare in i kluster och härleder lösningar för hur vi, baserat på kluster, kan identifiera inflytelserika objekt i nätverk och förutsäga länkar som (ännu) inte existerar.

Abstract [de]

Wir leben in einer hochgradig vernetzten Welt und finden Netzwerke wo auch immer wir hinschauen: soziale Netzwerke, öffentliche Verkehrsnetze, Telekommunikationsnetze, Finanznetzwerke und mehr. Diese Netzwerke können immens komplex sein und potenziell Millionen oder sogar Milliarden miteinander verbundener Objekten umfassen. Um beantworten zu können, wie wir die Ausbreitung von Krankheiten in Kontaktnetzwerken kontrollieren, öffentliche Verkehrsnetze optimieren oder Anlageportfolios diversifizieren können, müssen wir die Funktionsweise und Arbeitsprinzipien dieser Netzwerke verstehen.

Netzwerkwissenschaftler analysieren die Struktur von Netzwerken auf der Suche nach Communities: Gruppen von Objekten, die Cluster bilden und stärker miteinander verbunden sind als mit dem Rest. Communities repräsentieren die Bausteine von Netzwerken, entsprechen ihren Subsystemen und erlauben es uns, Netzwerke mit vereinfachten Modellen darzustellen. Communities und ihre Interaktionen untereinander zu verstehen hilft uns dabei, zu enträtseln, wie Netzwerke funktionieren.

In dieser Doktorarbeit verwenden wir die sogenannte Kartengleichung, ein informationstheoretischer Ansatz zur Community-Erkennung. Die Kartengleichung folgt dem Prinzip der minimalen Beschreibungslänge und nimmt an, dass Netzwerke einen Knotentypen haben und ihre zugrundeliegenden Daten vollständig sind. Wir stellen diese Annahmen infrage und passen die Kartengleichung zur Community-Erkennung in Netzwerken mit zwei Knotentypen und unvollständigen Daten an. Darüber hinaus leiten wir Ansätze ab, die, basierend auf Communities, einflussreiche Objekte in Netzwerken identifizieren und (noch) nicht existierende Verbindungen zwischen Objekten vorhersagen.

Ort, förlag, år, upplaga, sidor
Umeå: Umeå University, 2022. s. 103
Nyckelord
community detection, map equation, Huffman coding, network centrality, link prediction
Nationell ämneskategori
Datavetenskap (datalogi) Annan data- och informationsvetenskap Beräkningsmatematik
Identifikatorer
urn:nbn:se:umu:diva-199631 (URN)978-91-7855-828-5 (ISBN)978-91-7855-827-8 (ISBN)
Disputation
2022-10-21, NAT.D.470, Naturvetarhuset, Umeå, 09:00 (Engelska)
Opponent
Handledare
Forskningsfinansiär
Wallenberg AI, Autonomous Systems and Software Program (WASP)
Tillgänglig från: 2022-09-30 Skapad: 2022-09-27 Senast uppdaterad: 2022-09-27Bibliografiskt granskad
2. Mapping incomplete relational data: networks in ecology & evolution
Öppna denna publikation i ny flik eller fönster >>Mapping incomplete relational data: networks in ecology & evolution
2022 (Engelska)Doktorsavhandling, sammanläggning (Övrigt vetenskapligt)
Alternativ titel[sv]
Kartläggning av inkomplett relationell data : nätverk inom ekologi & evolution
Abstract [en]

We live in an interconnected world full of complex systems that cannot be understood simply by analyzing their components. From how genes regulate biological functions to the distribution of life on Earth, we need methods that can analyze systems as a whole.

Networks are abstractions of complex systems, helping capture properties that emerge from patterns of interactions rather than from the individual parts. To understand the patterns of interactions in large networks, we need to simplify them by discovering their modular structure that often characterizes complex systems. A hierarchical modular structure functions as a map that lets us navigate relational data efficiently and helps us see the general patterns. But how reliable is the map if it is based on incomplete data?

This thesis applies and builds upon the map equation, which is an information-theoretic method for detecting modular regularities in the flow patterns on networks. To robustly map incomplete data, we have developed three general approaches: (1) Adaptive resolution in both sampling of and dynamics on networks better fits the data. (2) Regularization avoids overfitting to random patterns. (3) Richer data can be included into the network for a more complete map. Methods that can include evolutionary relationships and handle incomplete data provide more powerful tools for mapping biodiversity in space and time.

Abstract [sv]

Vi lever i en sammankopplad värld full av komplexa system som inte låter sig förstås enbart genom att analysera dess komponenter. Från hur gener reglerar biologiska funktioner till livets utbredning på jorden behöver vi metoder som kan analysera system som en helhet.

Nätverk är abstraktioner av komplexa system som hjälper till att fånga egenskaper som uppstår genom interaktionsmönster snarare än hos de enskilda delarna. För att förstå dessa mönster i stora nätverk måste vi förenkla dem genom att upptäcka dess modulära stuktur som präglar komplexa system. En hierarkisk modulär struktur fungerar som en karta som låter oss navigera effektivt i relationsdata och hjälper oss att se de allmänna mönstren. Men hur tillförlitlig är kartan om den baseras på inkompletta data?

Den här avhandlingen applicerar och bygger vidare på kartekvationen som är en informationsteoretisk metod för att upptäcka modulära regelbundenheter i flödesmönstren på nätverk.För att robust kartlägga inkompletta data har vi utvecklat tre övergripande tillvägagångssätt: (1) Adaptiv upplösning i båda sampling av och dynamik på nätverk ger bättre anpassning till data. (2) Regularisering undviker överanpassning till slumpmässiga mönster. (3) Rikare data kan inkluderas i nätverket för en mer komplett karta. Metoder som kan inkludera evolutionära relationer och hantera inkompletta data ger kraftfullare verktyg för att kartlägga den biologiska mångfalden i rum och tid.

Ort, förlag, år, upplaga, sidor
Umeå: Umeå University, 2022. s. 66
Nyckelord
network science, information theory, map equation, community detection, biogeography, evolution
Nationell ämneskategori
Datavetenskap (datalogi) Annan fysik Biologisk systematik
Identifikatorer
urn:nbn:se:umu:diva-201176 (URN)978-91-7855-887-2 (ISBN)978-91-7855-888-9 (ISBN)
Disputation
2022-12-19, NAT.D.410, Naturvetarhuset, Umeå, 09:00 (Engelska)
Opponent
Handledare
Tillgänglig från: 2022-11-28 Skapad: 2022-11-22 Senast uppdaterad: 2022-11-24Bibliografiskt granskad

Open Access i DiVA

fulltext(1061 kB)86 nedladdningar
Filinformation
Filnamn FULLTEXT01.pdfFilstorlek 1061 kBChecksumma SHA-512
1eec1a10e26b94fe0035465a836e316274ff95f73c660abdfd638e8192d13f4635758be5302a9f54e0dfa1c63a4766e889bedb34022c1b7c0074dcd7faa174a6
Typ fulltextMimetyp application/pdf
errata(272 kB)24 nedladdningar
Filinformation
Filnamn ERRATA01.pdfFilstorlek 272 kBChecksumma SHA-512
265b605e808cded99b39bd2bc9e22506d500d0a146339090df1bc4a8a0885ce02b56d4112688a935597bc683f7382edb9ae699431884bd113329641595fc6bdb
Typ errataMimetyp application/pdf

Övriga länkar

Förlagets fulltextScopus

Person

Smiljanic, JelenaBlöcker, ChristopherEdler, DanielRosvall, Martin

Sök vidare i DiVA

Av författaren/redaktören
Smiljanic, JelenaBlöcker, ChristopherEdler, DanielRosvall, Martin
Av organisationen
Institutionen för fysik
I samma tidskrift
Journal of Complex Networks
Annan fysik

Sök vidare utanför DiVA

GoogleGoogle Scholar
Totalt: 86 nedladdningar
Antalet nedladdningar är summan av nedladdningar för alla fulltexter. Det kan inkludera t.ex tidigare versioner som nu inte längre är tillgängliga.

doi
urn-nbn

Altmetricpoäng

doi
urn-nbn
Totalt: 251 träffar
RefereraExporteraLänk till posten
Permanent länk

Direktlänk
Referera
Referensformat
  • apa
  • ieee
  • modern-language-association-8th-edition
  • vancouver
  • Annat format
Fler format
Språk
  • de-DE
  • en-GB
  • en-US
  • fi-FI
  • nn-NO
  • nn-NB
  • sv-SE
  • Annat språk
Fler språk
Utmatningsformat
  • html
  • text
  • asciidoc
  • rtf