Algoritem za štetje malih induciranih podgrafov in orbit vozlišč v redkih grafih : magistrsko delo

Močnik, Mariza (author), Demšar, Janez (mentor)

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.

• Language: Slovenian
• Keywords: analiza omrežij, majhni inducirani podgrafi, teorija grafov, Orca, orbite
• Work type: Master's thesis/paper
• Typology: 2.09 - Master's Thesis
• Organization: PEF - Faculty of Education
• Publisher: [M. Močnik]
• Year: 2017
• Number of pages: 60 str.
• PID: 20.500.12556/RUL-98166
• UDC: 004(043.2)
• COBISS.SI-ID: 11823945
• Publication date in RUL: 13.12.2017

Secondary language

• Language: English
• Title: Algorithm for counting small induced subgraphs and orbits nodes in sparse graphs

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.

• Keywords: computer science, računalništvo