Problem maksimalne klike
Natalija Grbac · 2016
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.