Algoritem za štetje malih induciranih podgrafov in orbit vozlišč v redkih grafih
V magistrskem delu se ukvarjamo z novejšo metodo za analizo omrežij, ki temelji na majhnih povezanih induciranih podgrafih, ki jim rečemo grafki (ang. graphlets). V ta namen na začetku najprej definiramo graf oziroma omrežje, predstavimo standardne družine grafov in nekaj njegovih lastnosti, ki so p...
Main Author: | |
---|---|
Other Authors: | |
Format: | Master Thesis |
Language: | Slovenian |
Published: |
M. Močnik
2017
|
Subjects: | |
Online Access: | https://repozitorij.uni-lj.si/IzpisGradiva.php?id=98166 https://repozitorij.uni-lj.si/Dokument.php?id=107378&dn= https://plus.si.cobiss.net/opac7/bib/11823945?lang=sl |
id |
ftuniljubljanair:oai:repozitorij.uni-lj.si:IzpisGradiva.php-id-98166 |
---|---|
record_format |
openpolar |
spelling |
ftuniljubljanair:oai:repozitorij.uni-lj.si:IzpisGradiva.php-id-98166 2023-05-15T17:53:24+02:00 Algoritem za štetje malih induciranih podgrafov in orbit vozlišč v redkih grafih Algorithm for counting small induced subgraphs and orbits nodes in sparse graphs Močnik, Mariza Demšar, Janez 2017-12-13 text/url https://repozitorij.uni-lj.si/IzpisGradiva.php?id=98166 https://repozitorij.uni-lj.si/Dokument.php?id=107378&dn= https://plus.si.cobiss.net/opac7/bib/11823945?lang=sl slv slv M. Močnik https://repozitorij.uni-lj.si/IzpisGradiva.php?id=98166 https://repozitorij.uni-lj.si/Dokument.php?id=107378&dn= https://plus.si.cobiss.net/opac7/bib/11823945?lang=sl info:eu-repo/semantics/openAccess analiza omrežij majhni inducirani podgrafi teorija grafov Orca orbite computer science računalništvo info:eu-repo/classification/udc/004(043.2) info:eu-repo/semantics/masterThesis info:eu-repo/semantics/publishedVersion 2017 ftuniljubljanair 2021-12-06T09:56:41Z V magistrskem delu se ukvarjamo z novejšo metodo za analizo omrežij, ki temelji na majhnih povezanih induciranih podgrafih, ki jim rečemo grafki (ang. graphlets). V ta namen na začetku najprej definiramo graf oziroma omrežje, predstavimo standardne družine grafov in nekaj njegovih lastnosti, ki so potrebne za nadaljnje razumevanje magistrskega dela. V nadaljevanju opišemo nekaj pogostih tipov omrežij in se posvetimo analizi omrežij. Osredotočimo se na metodo za analizo omrežij z grafki, kjer definiramo nekaj vrednosti, ki določajo strukturne lastnosti omrežij, njihov izračun pa temelji na grafkih. Dalje predstavimo nekaj algoritmov, ki uporabljajo grafke pri svojem delovanju in nekaj algoritmov, ki grafke štejejo. Izmed teh podrobneje predstavimo algoritem Orca za štetje orbit vozlišč in povezav za grafke na 2- do 5-vozliščih. Na konkretnih primerih opišemo metodo, na kateri algoritem deluje, predstavimo potek samega algoritma ter na konkretnem omrežju pokažemo delovanje programa Orca, ki je implementiran v programskem orodju R. The thesis deals with a newer method of network analysis which is based on small connected induced subgraphs or graphlets. First, a definition of a graph or network is provided, then standard graph families and some of their characteristics are presented, which helps the reader understand the thesis more thoroughly. Later in the work, a few frequently used types of networks are described in detail. The main focus is on the method of network analysis using graphlets, and several values that determine the structural characteristics of networks are defined in the course of the thesis. Each calculation of networks is based on graphlets. Furthermore, a few algorithms that use graphlets in order to operate properly, and several algorithms that count graphlets are presented as well. One of such algorithms is called Orca and it is used for counting orbits, nodes and connections for graphlets on 2- to 5-nodes. The method by which the algorithm operates is described, using specific examples. The course of the mere algorithm is presented as well as the function of the programme Orca, which is implemented in R tools. Master Thesis Orca Repository of the University of Ljubljana (RUL) |
institution |
Open Polar |
collection |
Repository of the University of Ljubljana (RUL) |
op_collection_id |
ftuniljubljanair |
language |
Slovenian |
topic |
analiza omrežij majhni inducirani podgrafi teorija grafov Orca orbite computer science računalništvo info:eu-repo/classification/udc/004(043.2) |
spellingShingle |
analiza omrežij majhni inducirani podgrafi teorija grafov Orca orbite computer science računalništvo info:eu-repo/classification/udc/004(043.2) Močnik, Mariza Algoritem za štetje malih induciranih podgrafov in orbit vozlišč v redkih grafih |
topic_facet |
analiza omrežij majhni inducirani podgrafi teorija grafov Orca orbite computer science računalništvo info:eu-repo/classification/udc/004(043.2) |
description |
V magistrskem delu se ukvarjamo z novejšo metodo za analizo omrežij, ki temelji na majhnih povezanih induciranih podgrafih, ki jim rečemo grafki (ang. graphlets). V ta namen na začetku najprej definiramo graf oziroma omrežje, predstavimo standardne družine grafov in nekaj njegovih lastnosti, ki so potrebne za nadaljnje razumevanje magistrskega dela. V nadaljevanju opišemo nekaj pogostih tipov omrežij in se posvetimo analizi omrežij. Osredotočimo se na metodo za analizo omrežij z grafki, kjer definiramo nekaj vrednosti, ki določajo strukturne lastnosti omrežij, njihov izračun pa temelji na grafkih. Dalje predstavimo nekaj algoritmov, ki uporabljajo grafke pri svojem delovanju in nekaj algoritmov, ki grafke štejejo. Izmed teh podrobneje predstavimo algoritem Orca za štetje orbit vozlišč in povezav za grafke na 2- do 5-vozliščih. Na konkretnih primerih opišemo metodo, na kateri algoritem deluje, predstavimo potek samega algoritma ter na konkretnem omrežju pokažemo delovanje programa Orca, ki je implementiran v programskem orodju R. The thesis deals with a newer method of network analysis which is based on small connected induced subgraphs or graphlets. First, a definition of a graph or network is provided, then standard graph families and some of their characteristics are presented, which helps the reader understand the thesis more thoroughly. Later in the work, a few frequently used types of networks are described in detail. The main focus is on the method of network analysis using graphlets, and several values that determine the structural characteristics of networks are defined in the course of the thesis. Each calculation of networks is based on graphlets. Furthermore, a few algorithms that use graphlets in order to operate properly, and several algorithms that count graphlets are presented as well. One of such algorithms is called Orca and it is used for counting orbits, nodes and connections for graphlets on 2- to 5-nodes. The method by which the algorithm operates is described, using specific examples. The course of the mere algorithm is presented as well as the function of the programme Orca, which is implemented in R tools. |
author2 |
Demšar, Janez |
format |
Master Thesis |
author |
Močnik, Mariza |
author_facet |
Močnik, Mariza |
author_sort |
Močnik, Mariza |
title |
Algoritem za štetje malih induciranih podgrafov in orbit vozlišč v redkih grafih |
title_short |
Algoritem za štetje malih induciranih podgrafov in orbit vozlišč v redkih grafih |
title_full |
Algoritem za štetje malih induciranih podgrafov in orbit vozlišč v redkih grafih |
title_fullStr |
Algoritem za štetje malih induciranih podgrafov in orbit vozlišč v redkih grafih |
title_full_unstemmed |
Algoritem za štetje malih induciranih podgrafov in orbit vozlišč v redkih grafih |
title_sort |
algoritem za štetje malih induciranih podgrafov in orbit vozlišč v redkih grafih |
publisher |
M. Močnik |
publishDate |
2017 |
url |
https://repozitorij.uni-lj.si/IzpisGradiva.php?id=98166 https://repozitorij.uni-lj.si/Dokument.php?id=107378&dn= https://plus.si.cobiss.net/opac7/bib/11823945?lang=sl |
genre |
Orca |
genre_facet |
Orca |
op_relation |
https://repozitorij.uni-lj.si/IzpisGradiva.php?id=98166 https://repozitorij.uni-lj.si/Dokument.php?id=107378&dn= https://plus.si.cobiss.net/opac7/bib/11823945?lang=sl |
op_rights |
info:eu-repo/semantics/openAccess |
_version_ |
1766161112131174400 |