izpis_h1_title_alt

Prilagojeno zmanjševanje kompleksnih realnih omrežij
ID BLAGUS, NELI (Author), ID Bajec, Marko (Mentor) More about this mentor... This link opens in a new window

.pdfPDF - Presentation file, Download (7,76 MB)
MD5: 869A347FE20992C51CF26DF03EC68660
PID: 20.500.12556/rul/037f0343-ad76-41c1-bdb3-813d9c798051

Abstract
Omrežja so pomembno orodje za analizo, razumevanje in prikaz kompleksnih sistemov, kot so na primer družbeno omrežje uporabnikov Facebooka, tehnološko omrežje železniških povezav, biološko omrežje interakcij med beljakovinami in informacijsko omrežje povezav med spletnimi stranmi. Zaradi hitrega razvoja svetovnega spleta in možnosti shranjevanja velikih količin podatkov v zadnjih letih z omrežji opisujemo vse večje sisteme. Velikost omrežij otežuje njihovo razumevanje in prikaz, prav tako je časovno in prostorsko zahtevnejša njihova analiza. Problem za učinkovito analizo predstavljajo tudi hitro spreminjajoča se omrežja ter omrežja z nepopolnimi ali skritimi podatki. Realna omrežja so tako pogosto zmanjšane različice dejanskih sistemov, ki so z omrežji opisani. Z namenom reševanja problema velikosti omrežij in razumevanja razlik med dejanskimi in nepopolnimi sistemi so bili predlagani različni pristopi za zmanjševanje omrežij. Pri procesu zmanjševanja z združevanjem, vzorčenjem ali s preiskovanjem vozlišč in povezav veliko omrežje preoblikujemo v manjše. Hkrati želimo, da se lastnosti osnovnega omrežja z zmanjševanjem čimbolj ohranijo. Zmanjšano omrežje je tako uporabno na primer za hitrejšo analizo, učinkovitejši prikaz ali simulacijo dinamičnih procesov. V literaturi je analiziranih veliko pristopov za zmanjševanje, redke študije pa medsebojno primerjajo različne pristope. V disertaciji se ukvarjamo z analizo spreminjanja omrežij med zmanjševanjem in primerjavo pristopov za zmanjševanje. Predlagamo mero za oceno učinkovitosti zmanjševanja, ki temelji na uspešnosti ohranjanja lastnosti osnovnega omrežja. S predlagano mero primerjamo več pristopov za zmanjševanje omrežji različnih tipov in velikosti ter opazujemo uspešnost ohranjanja lastnosti pri zmanjšanih omrežjih različnih velikosti. Podrobneje analiziramo spreminjanje gostote omrežij in povezovanje skupin vozlišč med zmanjševanjem. Na podlagi rezultatov oblikujemo shemo za pomoč pri izbiri pristopa za zmanjševanje izbranega omrežja.

Language:Slovenian
Keywords:analiza omrežij, realna omrežja, zmanjševanje omrežij, združevanje, vzorčenje, preiskovanje, uspešnost zmanjševanja, skupine vozlišč, gostota omrežja
Work type:Doctoral dissertation
Organization:FRI - Faculty of Computer and Information Science
Year:2016
PID:20.500.12556/RUL-85988 This link opens in a new window
COBISS.SI-ID:1537166531 This link opens in a new window
Publication date in RUL:03.10.2016
Views:2652
Downloads:884
Metadata:XML DC-XML DC-RDF
:
Copy citation
Share:Bookmark and Share

Secondary language

Language:English
Abstract:
Networks are an important tool for analyzing and visualizing different complex systems. Examples of real-world networks include social network of friends on Facebook, technological network of railways, biological network of interactions between proteins and information networks of hyperlinks between the Web pages. The evolution of the Web and the capability of storing large amounts of data have caused the size of networked systems and their complexity to increase. However, the algorithms for network analysis and visualization appear impractical for addressing very large systems. Furthermore, data about networks are not always complete, their structure may be hidden, or they may change quickly over time. Any network studied in the literature is thus inevitably just a simplified representative of its real-world analogue. For these reasons, understanding how an incomplete system differs from a complete one is crucial. Recently, a number of techniques have been proposed for simplifying complex networks. The simplification is a process, which reduce the size of a large network with merging, sampling or exploration of nodes or links in a network. Simplification techniques are applied to large networks to allow for their faster and more efficient analysis. Since the findings of the analyses and simulations of simplified networks are implied for the original ones, it is of key importance to understand the structural differences between the original networks and their simplified variants. Network simplification has been extensively investigated from different perspectives. A large number of studies focus on the changes in network properties introduced by simplification. On the other hand, only a few studies compare simplification techniques. In this doctoral thesis, we study the changes of real-world networks introduced by simplification and analyze the differences among simplification techniques. We propose an approach for assessing the effectiveness of simplification. Based on the similarity between original and simplified networks, we compare different simplification techniques. We simplify a number of real-world networks of various types and sizes and explore the preservation of network properties on simplified networks of different sizes. We analyze the changes of network density under the simplification and compare characteristic groups of nodes in original and simplified networks. Based on the findings of the analyses we introduce the scheme for choosing the appropriate simplification technique for a particular network.

Keywords:network analysis, real networks, network simplification, merging, sampling, exploration, simplification effectiveness, node groups, network density

Similar documents

Similar works from RUL:
Similar works from other Slovenian collections:

Back