Umeå University's logo

umu.sePublications
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
Similarity-based Link Prediction from Modular Compression of Network Flows
Umeå University, Faculty of Science and Technology, Department of Physics.ORCID iD: 0000-0001-7881-2496
Umeå University, Faculty of Science and Technology, Department of Physics.ORCID iD: 0000-0003-0124-1909
Umeå University, Faculty of Science and Technology, Department of Physics.ORCID iD: 0000-0002-7181-9940
(English)Manuscript (preprint) (Other academic)
Abstract [en]

Node similarity scores constitute a foundation for machine learning in graphs. Besides clustering, node classification, and anomaly detection, they are a basis for link prediction with critical applications in biological systems, information networks, and recommender systems. Recent works on link prediction use vector space embeddings to calculate node similarities. While these methods can provide good performance in undirected networks, they have several disadvantages: limited interpretability, problem-specific hyperparameter tuning, manual model fitting through dimensionality reduction, and poor performance of symmetric similarities in directed link prediction. To address these issues, we propose MapSim, a novel information-theoretic approach to assess node similarities based on modular compression of network flows. Different from vector space embeddings, MapSim represents nodes in a discrete, non-metric space of communities and yields asymmetric similarities suitable to predict directed and undirected links in an unsupervised fashion. The resulting similarities can be explained based on a network's hierarchical modular organisation, facilitating interpretability. MapSim naturally accounts for Occam's razor, leading to parsimonious representations of clusters at multiple scales. Addressing unsupervised link prediction, we compare MapSim to popular embedding-based algorithms across 47 data sets of networks from a few hundred to hundreds of thousands of nodes and millions of links. Our analysis shows that MapSim's average performance across all networks is more than 7% higher than its closest competitor, outperforming all embedding methods in 14 of the 47 networks, and a more than 33% better worst-case performance. Our method demonstrates the potential of compression-based approaches in graph representation learning, with promising applications in other graph learning tasks.

Keywords [en]
machine learning, network analysis, graph learning, representation learning, link prediction, minimum description length
National Category
Computer Sciences Other Computer and Information Science
Identifiers
URN: urn:nbn:se:umu:diva-199604OAI: oai:DiVA.org:umu-199604DiVA, id: diva2:1698021
Available from: 2022-09-22 Created: 2022-09-22 Last updated: 2022-09-27
In thesis
1. Through the coding-lens: community detection and beyond
Open this publication in new window or tab >>Through the coding-lens: community detection and beyond
2022 (English)Doctoral thesis, comprehensive summary (Other academic)
Alternative title[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.

Place, publisher, year, edition, pages
Umeå: Umeå University, 2022. p. 103
Keywords
community detection, map equation, Huffman coding, network centrality, link prediction
National Category
Computer Sciences Other Computer and Information Science Computational Mathematics
Identifiers
urn:nbn:se:umu:diva-199631 (URN)978-91-7855-828-5 (ISBN)978-91-7855-827-8 (ISBN)
Public defence
2022-10-21, NAT.D.470, Naturvetarhuset, Umeå, 09:00 (English)
Opponent
Supervisors
Funder
Wallenberg AI, Autonomous Systems and Software Program (WASP)
Available from: 2022-09-30 Created: 2022-09-27 Last updated: 2022-09-27Bibliographically approved

Open Access in DiVA

No full text in DiVA

Other links

Full text

Authority records

Blöcker, ChristopherSmiljanic, JelenaRosvall, Martin

Search in DiVA

By author/editor
Blöcker, ChristopherSmiljanic, JelenaScholtes, IngoRosvall, Martin
By organisation
Department of Physics
Computer SciencesOther Computer and Information Science

Search outside of DiVA

GoogleGoogle Scholar

urn-nbn

Altmetric score

urn-nbn
Total: 202 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