Neke tehnike za traženje pseudo-klika u grafu

master's thesis

• Title (english): Some techniques for searching for pseudo-cliques in a graph
• Author: Rok Štefan
• Mentor: Pavle Goldstein (mentor)
• Committee member: Pavle Goldstein (predsjednik povjerenstva)
• Committee member: Nenad Antonić (član povjerenstva)
• Committee member: Miljenko Marušić (član povjerenstva)
• Committee member: Hrvoje Šikić (član povjerenstva)
• Granter: University of Zagreb; Faculty of Science; (Department of Mathematics); Zagreb
• Defense date and country: 2023-03-02, Croatia
• Scientific / art field, discipline and subdiscipline: NATURAL SCIENCES; Mathematics

Abstract

Ovaj diplomski rad opisuje značaj i problematiku pronalaženja klika u grafovima, a naveli smo i neke poznate ideje i algoritme za traženje klika. Naš algoritam problem koji je zapisan u grafu postavlja kao geometrijski problem u euklidskom prostoru, pronalazi kuglu koja dobro opisuje vrhove iz klike te time pronalazi pseudo-kliku ili “seed” klike ako u prethodnom ne uspije. Nakon navođenja matematičkih pojmova nužnih za razumijevanje ovog rada, prezentira se algoritam koji u euklidskom prostoru pronalazi kuglu koja dobro opisuje vrhove iz klike. Algoritam je proveden na slučajnim grafovima veličine 2000 uz različite vjerojatnosti bridova i različite veličine klika, a svi grafovi imaju zadanu kliku znatno veću od očekivane. Za veće klike pseudo-klika je uspješno pronađena dok je u ostalim slučajevima uspješno pronađen “seed” klike. Rezultati pokazuju veliki potencijal ovakvog pristupa te možemo reći da se algoritam pokazao kao uspješan u pronalasku zadane klike čija veličina je znatno veća od očekivane veličine klike. Prikazani algoritam ima iznimno brzo vremensko izvođenje uz polinomijalnu složenost.

Abstract (english)

This thesis describes the importance and issues related to finding cliques in graphs. In addition to that, we mentioned some known ideas and algorithms for finding cliques. Our algorithm transforms the problem written in a graph into a geometrical problem in Euclidean space and finds a sphere that well-describes the vertices that belong to the clique. This way we find the pseudo-clique or seed of the clique if the former was not accomplished. After stating the mathematical terms necessary for understanding this thesis, we present an algorithm that finds a sphere in Euclidean space that well-describes the vertices belonging to a clique. The algorithm was conducted on random graphs of size 2000 with different edge probabilities and different clique sizes. All of the graphs have a previously set clique that is significantly larger than expected. For bigger cliques, a pseudo-clique was successfully found while in other cases seed of the clique was successfully found. Results show the huge potential for this kind of approach and we can say that the algorithm has shown success in finding the given clique whose size is significantly larger than the expected clique size. Shown algorithm has exceptionally good time performance with polynomial complexity

• Keywords: algoritmi za traženje klika; geometrijski problem u euklidskom prostoru; pseudo-klik; “seed” klik
• Keywords (english): algorithms for finding cliques; geometrical problem in Euclidean space; pseudo-clique; seed of the clique
• Language: croatian
• URN:NBN: urn:nbn:hr:217:367835
• Study programme: Title: Mathematical Statistics; Study programme type: university; Study level: graduate; Academic / professional title: magistar/magistra matematike (magistar/magistra matematike)
• Type of resource: Text
• File origin: Born digital
• Access conditions: Open access
• Created on: 2023-08-24 13:17:08