Graphlets in multilayer networks

Loading...
Thumbnail Image

URL

Journal Title

Journal ISSN

Volume Title

Perustieteiden korkeakoulu | Master's thesis

Date

2018-02-12

Department

Major/Subject

Complex Systems

Mcode

SCI3060

Degree programme

Master’s Programme in Life Science Technologies

Language

en

Pages

82 + 6

Series

Abstract

Networks, consisting of nodes and edges, are used to model and analyze a wide array of phenomena in various disciplines. Recently, increasing attention has been given to more realistic network representations such as multilayer networks, which can include different types of interactions between nodes or other additional structural information. However, generalizing concepts devised for ordinary graphs to multilayer networks is in its early stages. In this thesis, the concept of graphlets and algorithms utilizing them to analyze networks are generalized to multilayer networks. Graphlet analysis has been applied to alignment-free network comparison, and here such a comparison method is developed for multiplex networks, which are a type of multilayer networks. The ability of multilayer-graphlet-based distance measures to cluster similar networks is assessed by applying the measures for both real world and random networks, and the performance of these new multilayer methods are compared to methods based on ordinary networks. The results indicate that one can benefit from the multiplex measures when there exists clear multiplex structure in the network.

Verkostoja, jotka koostuvat solmuista ja kaarista, käytetään erilaisten ilmiöiden mallintamiseen ja analysointiin eri aloilla. Viime aikoina on kiinnitetty yhä enemmän huomiota realistisempiin verkkoesityksiin, kuten monitasoverkostoihin, jotka voivat sisältää eri tyyppisiä vuorovaikutuksia solmujen välillä tai muuta rakenteellista lisätietoa. Tavallisille verkoille laadittujen käsitteiden yleistäminen monitasoverkostoille on kuitenkin vielä alkuvaiheissaan. Tässä työssä monitasoverkostoihin yleistetään graflettien käsite sekä algoritmeja, jotka hyödyntävät niitä verkkojen analysoimisessa. Graflet-analyysiä on sovellettu kohdistamattomaan verkkojen vertailuun, ja tässä eräs vertailumenetelmä kehitetään multiplex-verkkoille, jotka ovat monitasoverkostojen tyyppi. Monitasoisiin grafletteihin perustuvien etäisyysmittojen kykyä samankaltaisten verkkojen klusterointiin arvioidaan soveltamalla mittoja sekä reaalimaailman verkkoihin että satunnaisverkkoihin, ja näiden uusien monitasoisten menetelmien suorituskykyä verrataan tavallisiin verkkoihin perustuviin menetelmiin. Tulokset osoittavat, että multiplex-mitoista voidaan hyötyä, kun verkossa on selkeä multiplex-rakenne.

Description

Supervisor

Kivelä, Mikko

Thesis advisor

Kivelä, Mikko

Keywords

multilayer networks, graphlets, graph isomorphisms, graph automorphism orbits, alignment-free network comparison

Other note

Citation