[feed] pefprints@pef.uni-lj.si | [feed] Atom [feed] RSS 1.0 [feed] RSS 2.0 |
  Logo Login | Create Account

Algorithm for counting small induced subgraphs and orbits nodes in sparse graphs

Mariza Močnik (2017) Algorithm for counting small induced subgraphs and orbits nodes in sparse graphs. MSc thesis.

Download (1810Kb)


    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.

    Item Type: Thesis (MSc thesis)
    Keywords: network analysis, small induced subgraphs, graph theory, Orca, orbits
    Number of Pages: 60
    Language of Content: Slovenian
    Mentor / Comentors:
    Mentor / ComentorsIDFunction
    prof. dr. Janez DemšarMentor
    Link to COBISS: http://www.cobiss.si/scripts/cobiss?command=search&base=50126&select=(ID=11823945)
    Institution: University of Ljubljana
    Department: Faculty of Education
    Item ID: 4863
    Date Deposited: 20 Nov 2017 11:18
    Last Modified: 20 Nov 2017 11:18
    URI: http://pefprints.pef.uni-lj.si/id/eprint/4863

    Actions (login required)

    View Item