izpis_h1_title_alt

Statična in dinamična analiza omrežij na podlagi lokalnih vzorcev : doktorska disertacija
Polajnar, Matija (Author), Demšar, Janez (Mentor) More about this mentor... This link opens in a new window

URLURL - Presentation file, Visit http://eprints.fri.uni-lj.si/2710/ This link opens in a new window

Abstract
V disertaciji analiziramo uporabnost dveh vrst lokalnih vzorcev v omrežjih – t.i. (označenih) pogostih vzorcev ter grafkov – za raziskovanje časovnega razvoja omrežja ter napovedovanje nadaljnjega razvoja oziroma odkrivanje manjkajočih delov. Analiza kompleksno strukturiranih podatkov, kot so omrežja, zaradi razvoja strojne opreme v zadnjih dveh desetletjih, zaradi enostavnejšega zajema podatkov ter zaradi konkretnih potreb industrije vzbuja vedno več pozornosti raziskovalcev. Spletne družbene storitve, na primer, so na eni strani zelo bogat vir podatkov v obliki omrežij, po drugi strani pa zelo hvaležen odjemalec dobrih hipotez o nadaljnjem razvoju omrežja. Podatke o družbenih mrežah s pridom uporabljajo tudi raziskovalci s področja družboslovnih znanosti, prav tako analiza omrežij veliko prispeva k razvoju znanosti na področju biologije. Naše delo je bilo motivirano s konkretno aplikativno potrebo po odkrivanju manjkajočih elementov v majhnih označenih omrežjih. V literaturi tak problem še ni bil obravnavan, zato smo morali najprej postaviti teoretične temelje in izpostaviti razlike napram drugim do zdaj obravnavanim problemom. Zaradi ključnih razlik smo predlagali tudi drugačno metodologijo merjenja napovedne uspešnosti, ki testna omrežja gradi z odstranjevanjem po ene povezave iz dane množice omrežij. Definirali smo še metriko uspešnosti na podlagi ranga pravilne napovedi. Utemeljitev problema in postavitev metodologije merjenja uspešnosti štejemo za pomembna prispevka tega dela k znanosti. Reševanja problema smo se lotili z zasnovo družine metod, ki kot model domene uporabljajo označene pogoste vzorce. Napovedi, tj. hipoteze glede morebitnih manjkajočih elementov v omrežju, izdelujejo in vrednotijo z delnim vpenjanjem pogostih vzorcev v domnevno nepopolno omrežje. Na realnih in sintetičnih množicah izmerjena uspešnost kaže na koristnost ne le zasnovane družine metod, temveč posebne obravnave tako definiranega problema nasploh. Uveljavljene metode, ki rešujejo splošnejše probleme, so namreč pri odkrivanju manjkajočih elementov v majhnih označenih omrežjih dosegle bistveno nižjo uspešnost. Metoda ni namenjena analizi večjih omrežij. Že pri zmerno velikih omrežjih jo začne dušiti časovna potratnost, poskusi pa kažejo, da začne padati tudi njena napovedna točnost. To je pričakovano, saj metoda ni bila zasnovana za večja omrežja; za te so bolj primerne v obstoječi literaturi opisane metode. Posvetili smo se še eni vrsti lokalnih vzorcev, ki so se najprej uveljavili na področju bioinformatike, a so v splošnem primerni za analizo lokalnih podstruktur v velikih neusmerjenih neoznačenih omrežjih: grafkom. Problem opazovanja razvoja grafkov v rastočem omrežju skozi čas smo najprej osvetlili s teoretičnega vidika. Pokazali smo, kako se strukture lahko razvijajo iz ene v drugo ter pripravili matematična in algoritmična orodja za empirično obravnavo več realnih in sintetičnih omrežij. Pokazali smo, da določene značilnosti v razvoju veljajo splošno za vsa analizirana omrežja, v drugih pa se ta ločijo med seboj. Zasnovali smo tudi družino metod za napovedovanje nadaljnjega časovnega razvoja omrežja na podlagi analize dotedanjega razvoja grafkov. Ocena napovedne uspešnosti ne daje rezultatov, na podlagi katerih bi lahko zasnovane algoritme priporočili za praktično uporabo. Na vseh analiziranih omrežjih je obstoječa metoda naključnih sprehodov s ponovnimi začetki dosegla višjo napovedno uspešnost. Tudi pri zlaganju napovedi napovedi razvite družine metod ne prinesejo dodane vrednosti. So pa rezultati poskusov namignili, da bi bilo mogoče napovedno uspešnost metode naključnih sprehodov izboljšati z zlaganjem njenih napovedi pri uporabi različnih vrednosti parametrov.

Language:Slovenian
Keywords:analiza omrežij, nadzorovano učenje, pogosti vzorci, grafki, računalništvo, disertacije
Work type:Doctoral dissertation (mb31)
Tipology:2.08 - Doctoral Dissertation
Organization:FRI - Faculty of computer and information science
Year:2014
Publisher:[M. Polajnar]
Number of pages:98 str.
UDC:004.7(043.3)
COBISS.SI-ID:1536016835 Link is opened in a new window
Views:966
Downloads:137
Metadata:XML RDF-CHPDL DC-XML DC-RDF
 
Average score:(0 votes)
Your score:Voting is allowed only to logged in users.
:
Share:AddThis
AddThis uses cookies that require your consent. Edit consent...

Secondary language

Language:English
Title:Static and dynamic analysis of networks based on local patterns
Abstract:
In this work, we attempt to determine applicability of two kinds of local network patterns, i.e. labelled frequent patterns and graphlets, to the problems of network evolution analysis and prediction of either further temporal development of the network or its missing elements. Networks and other data with complex structure are attracting ever more attention in the research community. This is partly due to large network analysis finally being feasible with the hardware, developed in the last two decades. Beside that, methods to collect large amounts of network-structured data have also emerged, with industry-fueled need for its analysis following closely. For instance, World Wide Web-based social networking services offer unprecedented insight into social strucutures, and on the other hand provide strong incentive for development of methods that analyse networks and predict their future evolution. The data gathered by those services are a rich source for social sciences researchers, and network analysis also provides useful tools for scientists in the field of biology. Our work was motivated by our own need of a method to generate sensible hypotheses about missing elements in small labeled networks. No research of such a problem has been done before in the published literature. Therefore, we began by establishing theoretical foundations of the problem by formally defining it and pointing out similarities and differences with regard to other similar problems. Key differences required us to propose a new prediction quality evaluation methodology that constructs test networks by removing an edge from some network in a given set in every possible way. We defined an evaluation metrics based on the rank of correct prediction as well. The justification of the problem definition and the set up of the prediction quality evaluation methodology are important scientific contributions of this work. We propose a family of methods to solve the defined problem that use frequent patterns to model the domain. Hypotheses about missing elements in the network are constructed and scored by looking for partial embeddings of frequent patterns in what is considered to be an incomplete network. Results of evaluation on real and synthetic data sets indicate not only the usefulness of the proposed family of methods, but also the need to consider this type of problem separately from previously researched network analysis and completion problems. Methods, proposed in the available literature, that solve the latter, performed far worse in our small network completion problem. The proposed method is not suitable for large network analysis. Its time complexity begins to hinder its usefulness in slightly larger networks. Experiments show that its prediction quality declines with network size as well. That is an expected outcome as the method was not designed to handle large networks. While working with local network patterns, another type of them caught our attention: graphlets. Those have been first considered in the field of bioinformatics, but their use has since spread to other domains. We considered the process of graphlet evolution in growing networks from a theoretical viewpoint first. We showed how structures can transform into one another and defined mathematical and algorithmic tools for an empirical analysis of multiple real and synthetic networks. We showed how some evolution properties are shared among all analysed networks and others are domain-specific. Also proposed in this doctoral dissertation is a method for prediction of further temporal evolution of the network, based on analysis of graphlet evolution. Evaluation results do not indicate its usefulness for practical applications. On all analysed networks, the well-known method named Random Walk with Restarts (RWR) achieved better prediction. The predictions generated by our method also did not aid with prediction stacking. The evaluation results did, however, surprisingly show that stacking the RWR predictions, obtained using different parameter values, can increase prediction quality.

Keywords:network analysis, supervised learning, frequent patterns, graphlets, doctoral dissertations, theses

Similar documents

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

Comments

Leave comment

You have to log in to leave a comment.

Comments (0)
0 - 0 / 0
 
There are no comments!

Back