Seminár z kognitívnej vedy a umelej inteligencie - Andrej Jursa (25.4.2017)
v utorok 25.4.2017 o 16:30 hod. v miestnosti I/9
Od: Igor Farkaš
Prednášajúci: Mgr. Andrej Jursa
Názov: Fast algorithm for clique number discovery in functional brain networks
Termín: 25.4.2017, 16:30 hod., I/9
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.