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

21. 04. 2017 09.05 hod.
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.