Problem maksimalne klike

undergraduate thesis

• Title (english): Maximum clique problem
• Author: Natalija Grbac
• Mentor: Lana Horvat Dmitrović (mentor)
• Committee member: Lana Horvat Dmitrović (predsjednik povjerenstva)
• Committee member: Mario Osvin Pavčević (član povjerenstva)
• Committee member: Andrea Aglić Aljinović (član povjerenstva)
• Granter: University of Zagreb; Faculty of Electrical Engineering and Computing; Zagreb
• Defense date and country: 2016-07-11, Croatia
• Scientific / art field, discipline and subdiscipline: TECHNICAL SCIENCES; Computing

Abstract

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.

Abstract (english)

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.

• Keywords: podgraf; klika; maksimalna klika; računalna složenost; socijalna mreža; akademska srodnost
• Keywords (english): subgraph; clique; maximum clique; computational complexity; social network; academic inbreeding
• Language: croatian
• URN:NBN: urn:nbn:hr:168:845392
• Study programme: Title: Computing; Study programme type: university; Study level: undergraduate; Academic / professional title: sveučilišni/a prvostupnik/ prvostupnica (baccalaureus/baccalaurea) inženjer/inženjerka računarstva (sveučilišni/a prvostupnik/ prvostupnica (baccalaureus/baccalaurea) inženjer/inženjerka računarstva)
• Type of resource: Text
• File origin: Born digital
• Access conditions: Closed access
• Created on: 2018-02-06 08:59:39