Problem maksimalne klike

završni rad

• Naslov (engleski): Maximum clique problem
• Autor: Natalija Grbac
• Mentor: Lana Horvat Dmitrović (mentor)
• Član povjerenstva: Lana Horvat Dmitrović (predsjednik povjerenstva)
• Član povjerenstva: Mario Osvin Pavčević (član povjerenstva)
• Član povjerenstva: Andrea Aglić Aljinović (član povjerenstva)
• Ustanova koja je dodijelila akademski / stručni stupanj: Sveučilište u Zagrebu; Fakultet elektrotehnike i računarstva; Zagreb
• Datum i država obrane: 2016-07-11, Hrvatska
• Znanstveno / umjetničko područje, polje i grana: TEHNIČKE ZNANOSTI; Računarstvo

Sažetak

Cilj rada je opisati problem maksimalne klike, demonstrirati rad nekih algoritama za pronalaženje maksimalne klike te primijeniti te algoritme na primjeru socijalne mreže koja se sastoji od znanstvene zajednice Fakulteta elektrotehnike i računarstva u Zagrebu. Na početku se objašnjavaju osnovni pojmovi iz teorije grafova i stavljaju u kontekst problema maksimalne klike te se navode osnovne formulacije problema. Slijedi pojašnjenje računalne složenosti problema, težine aproksimacije i načina rada nekih heuristika. U srednjem dijelu se proučavaju tri postojeća algoritma za traženje maksimalne klike. Svaki algoritam se pokrenuo nad skupom grafova preuzetih iz baze DIMACS-a te su na temelju rezultata uspoređeni vrijeme rada, potrošnja memorije te veličina pronađene maksimalne klike svakog od algoritama. U zadnjem dijelu se objašnjava zašto je analitičarima socijalnih mreža pojam klike i njezina definicija zanimljiva te se navode primjeri istraživanja na području socijalnih mreža koji su povezani s problemom maksimalne klike. Na kraju se proučava znanstveno-istraživačka povezanost nastavnog osoblja Fakulteta elektrotehnike i računarstva. Za svaki Zavod Fakulteta je napravljen graf povezanosti članova i pomoću jednog od prije proučenih algoritama pronađena maksimalna klika. Nakon proučavanja svakog Zavoda pojedinačno, analizira se njihova međusobna povezanost te se zatim navode rezultati i zaključak analize.

Sažetak (engleski)

The purpose of this paper is to describe the maximum clique problem, demonstrate the work of some algorithms for finding a maximum clique and to apply those algorithms on a social network consisting of the scientific community of the Faculty of electrical engineering and computing in Zagreb. At the beginning, basic definitions from graph theory are explained and put in the context of the maximum clique problem and basic problem formulations are mentioned. The computational complexity of the problem as well as the hardness of approximation and the principles on which some heuristics operate are explained. In the central part three existing algorithms for finding maximum clique are examined. Each algorithm was tested on a collection of graphs taken from the DIMACS database and the run time, memory consumption and maximum clique size are compared. The last part explains why the concept of a clique and its definition are important to social network analysts and some research examples involving the maximum clique problem are mentioned. Finally, collaboration on scientific research papers between members of the academic community of the Faculty of electrical engineering and computing is examined. For each Faculty Department a graph containing connections between members is shown and using one of the previously described algorithms the maximum clique is found. After examining each Department individually, their interconnection is analysed and the results and conclusion of the analysis are presented.

• Ključne riječi: podgraf; klika; maksimalna klika; računalna složenost; socijalna mreža; akademska srodnost
• Ključne riječi (engleski): subgraph; clique; maximum clique; computational complexity; social network; academic inbreeding
• Jezik: hrvatski
• URN:NBN: urn:nbn:hr:168:845392
• Studijski program: Naziv: Računarstvo; Vrsta studija: sveučilišni; Stupanj studija: preddiplomski; Akademski / stručni naziv: sveučilišni/a prvostupnik/ prvostupnica (baccalaureus/baccalaurea) inženjer/inženjerka računarstva (univ.bacc.ing.comp.)
• Vrsta resursa: Tekst
• Način izrade datoteke: Izvorno digitalna
• Prava pristupa: Zatvoreni pristup
• Datum i vrijeme pohrane: 2018-02-06 08:59:39