Seminar of Cognitive Science - Andrej Jursa (25.4.2017)

Tuesday 25.4.2017 at 16:30, Lecture room I/9

21. 04. 2017 09.12 hod.
By: Igor Farkaš

Mgr. Andrej Jursa:
Fast algorithm for clique number discovery in functional brain networks

Abstract:
We present our improved algorithm for finding the clique number of simple undirected graph based on Ostergaard's algorithm applied to functional brain networks. The clique number of a graph is a size of its maximum clique. Finding that clique is a NP-hard problem. Our algorithm implements several pruning techniques which greatly restricts depth-first search branching using the original method. The resulting algorithm works faster on arbitrary simple undirected graphs, but the best performance is on the graphs with a scale-free property. We have used this algorithm to find and analyse clique numbers of 40 functional brain networks for three groups of subjects: elderly patients suffering from Alzheimer disease, elderly people and young healthy individuals.