magistrsko delo
Mariza Močnik (Author), Janez Demšar (Mentor)

Abstract

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.

Keywords

analiza omrežij;majhni inducirani podgrafi;teorija grafov;Orca;orbite;

Data

Language: Slovenian
Year of publishing:
Typology: 2.09 - Master's Thesis
Organization: UL PEF - Faculty of Education
Publisher: [M. Močnik]
UDC: 004(043.2)
COBISS: 11823945 Link will open in a new window
Views: 592
Downloads: 173
Average score: 0 (0 votes)
Metadata: JSON JSON-RDF JSON-LD TURTLE N-TRIPLES XML RDFA MICRODATA DC-XML DC-RDF RDF

Other data

Secondary language: English
Secondary title: Algorithm for counting small induced subgraphs and orbits nodes in sparse graphs
Secondary abstract: 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.
Secondary keywords: computer science;računalništvo;
File type: application/pdf
Type (COBISS): Master's thesis/paper
Thesis comment: Univ. v Ljubljani, Pedagoška fak., Predmetno poučevanje, Matematika in računalništvo
Pages: 60 str.
ID: 10880216