Yliopiston etusivulle Suomeksi På svenska In English Helsingin yliopisto

Methods for Network Abstraction

Show simple item record

dc.contributor Helsingin yliopisto, matemaattis-luonnontieteellinen tiedekunta, tietojenkäsittelytieteen laitos fi
dc.contributor Helsingfors universitet, matematisk-naturvetenskapliga fakulteten, institutionen för datavetenskap sv
dc.contributor University of Helsinki, Faculty of Science, Department of Computer Science en
dc.contributor.author Zhou, Fang fi
dc.date.accessioned 2012-10-15T08:18:07Z
dc.date.available 2012-08-06 fi
dc.date.available 2012-10-15T08:18:07Z
dc.date.issued 2012-08-16 fi
dc.identifier.uri URN:ISBN:978-952-10-8158-3 fi
dc.identifier.uri http://hdl.handle.net/10138/37237
dc.description.abstract We propose network abstraction as a research area. It is motivated by the growth of networks in many areas of life. Consider, for instance, networks of thousands of genes, millions of people, or billions of web pages. They are too large to be directly analyzed by users. The aim of network abstraction is to summarize a large network as a smaller one. An abstracted network can then help users to see the overall topology of a large network, or to understand the connections of distant nodes. The general network abstraction task is: given a large network, transform it into a smaller one, which contains in some well-specified sense the most relevant information. In this thesis, we analyze this research area and propose methods to solve some instances of the problem. The methods also provide different trade-offs between the graph quality and simplicity, as well as between result quality and efficiency. More specifically, we propose two approaches to abstracting a network. The first one is to simplify a weighted network by removing edges under the constraint that distances between all pairs of nodes are preserved. We first empirically show that a number of edges can be removed from real biological networks without losing any graph connectivity. We next relax the constraint of fully preserving original graph connectivity, extend lossless network simplification to lossy network simplification, and demonstrate that many more edges can be removed with little loss of quality. The second approach we give for network abstraction is to compress a weighted network by grouping nodes and edges. We propose novel methods and experimentally show that real graphs can be compressed efficiently with relatively little error. We next consider graphs with weights also on the nodes, and utilize them as node importances to extend the definition of weighted graph compression. We present new compression operations and demonstrate that the compressed graph can preserve more information related to more important nodes. Furthermore, we propose the idea of using node weights and compression to summarize the metabolisms in a set of organisms, and apply the methodology to better understand the metabolic biodiversity between Archaea and Eubacteria, the two most fundamental branches of life. en
dc.description.abstract Sosiaaliset verkostot, web ja geenien säätelysuhteet ovat esimerkkejä monimutkaisista verkostoista, joiden ymmärtäminen ja havainnollistaminen on tärkeää erilaisissa sovelluksissa. Laajojen verkostojen tarkastelu on kuitenkin hyvin vaikeaa. Fang Zhoun väitöskirjatyö "Methods for network abstraction" käsittelee verkkojen yksinkertaistamista pienemmiksi ja helpommin käsiteltäviksi. Väitöskirjan alussa Fang muotoilee ja jäsentää tämän uuden tutkimusalueen sekä esittää katsauksen aiemmin hajallaan olleeseen aihepiirin tutkimukseen. Sen jälkeen työssä esitetään kahdentyyppisiä uusia menetelmiä verkkojen yksinkertaistamiseen. Näistä sieventämismenetelmät poistavat verkosta sellaisia yhteyksiä, jotka vaikuttavat verkkoon kokonaisuutena vähiten. Ryhmittelymenetelmät puolestaan kokoavat verkoston yksilöitä joukoiksi samantapaisten roolien perusteella. Kun kokonainen ryhmä yksilöitä korvataan yhdellä yleistyksellä, saadaan tuloksena yksinkertaisempi verkko. Niin sieventämis- kuin ryhmittelymenetelmäkin pyrkivät säilyttämään mahdollisimman paljon alkuperäistä tietoa, vaikka verkoston esityksen koko suppeneekin. Väitöskirjatyössä esiteltyjä menetelmiä on testattu sekä sosiaalisiin verkostoihin että biologisiin verkkoihin, ja ne kykenevät tuottamaan yksinkertaistuksia, joissa säilyy olennaista tietoa verkoston rakenteesta. Lisäksi ryhmittelymenetelmää sovelletaan työssö vielä erikseen bakteerien ja arkkien metaboliaverkkoihin niiden monimuotoisuuden tutkimiseksi. fi
dc.format.mimetype application/pdf fi
dc.language.iso en fi
dc.publisher Helsingin yliopisto fi
dc.publisher Helsingfors universitet sv
dc.publisher University of Helsinki en
dc.relation.isformatof URN:ISBN:978-952-10-8157-6 fi
dc.relation.isformatof Unigrafia, 1238-8645 fi
dc.rights Julkaisu on tekijänoikeussäännösten alainen. Teosta voi lukea ja tulostaa henkilökohtaista käyttöä varten. Käyttö kaupallisiin tarkoituksiin on kielletty. fi
dc.rights This publication is copyrighted. You may download, display and print it for Your own personal use. Commercial use is prohibited. en
dc.rights Publikationen är skyddad av upphovsrätten. Den får läsas och skrivas ut för personligt bruk. Användning i kommersiellt syfte är förbjuden. sv
dc.subject tietojenkäsittelytiede fi
dc.title Methods for Network Abstraction en
dc.type.ontasot Väitöskirja (artikkeli) fi
dc.type.ontasot Doctoral dissertation (article-based) en
dc.type.ontasot Doktorsavhandling (sammanläggning) sv
dc.ths Toivonen, Hannu fi
dc.opn Borgelt, Christian fi
dc.type.dcmitype Text fi

Files in this item

Files Size Format View

There are no files associated with this item.

This item appears in the following Collection(s)

Show simple item record

Search Helda


Advanced Search

Browse

My Account