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

magistrsko delo

Mariza Močnik (Avtor), Janez Demšar (Mentor)

Povzetek

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.

Ključne besede

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

Podatki

Jezik:	Slovenski jezik
Leto izida:	2017
Tipologija:	2.09 - Magistrsko delo
Organizacija:	UL PEF - Pedagoška fakulteta
Založnik:	[M. Močnik]
UDK:	004(043.2)
COBISS:	11823945
Št. ogledov:	592
Št. prenosov:	173
Ocena:	0 (0 glasov)
Metapodatki:

Ostali podatki

Sekundarni jezik:	Angleški jezik
Sekundarni naslov:	Algorithm for counting small induced subgraphs and orbits nodes in sparse graphs
Sekundarni povzetek:	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.
Sekundarne ključne besede:	computer science;računalništvo;
Vrsta datoteke:	application/pdf
Vrsta dela (COBISS):	Magistrsko delo/naloga
Komentar na gradivo:	Univ. v Ljubljani, Pedagoška fak., Predmetno poučevanje, Matematika in računalništvo
Strani:	60 str.
ID:	10880216