Ing. Šimon Schierreich

Ing. Šimon Schierreich

Ing. Magda Friedjungová, Ph.D.

Department of Applied Mathematics

This bachelor thesis deals with a detailed explanation of group centrality measures, which is one of the techniques for analyzing graph networks. The various measures are described in terms of their applications and the principles of the algorithms for finding these measures are also explained. The individual measures are measured on real social network datasets and a discussion is given on these results.

Thesis on DSpace

Ing. Šimon Schierreich

Mgr. Michal Opler, Ph.D.

Department of Theoretical Computer Science

The Maximum Betweenness Centrality problem consists in picking a group of b nodes from a social network so that it has the greatest likelihood of detecting communication, assuming that nodes communicate only along shortest paths, chosen uniformly at random. Finding such groups is relevant for the study of communication in complex networks. Although this problem has been studied within the framework of classical complexity, its parameterized complexity has remained an open question. We close this gap by studying Maximum Betweenness Centrality from a parameterized perspective. We show that Maximum Betweenness Centrality is W[1]-hard when parameterized by the budget b, and complement this result with a lower bound of f(b) * n^o(b) for any algorithm for Maximum Betweenness Centrality parameterized by the budget b, under ETH. On a positive tone, we show that Maximum Betweenness Centrality is in FPT when parameterized by the vertex cover number, by the distance to clique and the budget, or by the twin cover number and the budget.

Thesis on DSpace

Ing. Šimon Schierreich

RNDr. Jiřina Scholtzová, Ph.D.

Department of Theoretical Computer Science

In this thesis, we provide an introduction to the topic of covert networks and their analysis, with emphasis on the Hiding Leaders problem which we study with respect to the degree centrality measure and using the framework of parameterized computational complexity. We analyze results for the Hiding Leaders problem provided in the literature and put them into a perspective of the parameterized complexity. We also point out that there are multiple definitions of the problem and review some of the results from the literature with respect to the definition we picked. We then bring new results to the domain by showing that the problem is W[1]-hard when parameterized by b + d even when |L| = 1, and para-NP-hard with respect to |L|, where b denotes the number of edges allowed to be added into a given network, d denotes the number of followers needed to have centrality at least as high as any of the leaders and L denotes a set of leaders. We also show that the problem is in XP when parameterized by b or d. In the end, we put together our results and their corollaries - for parameters |L|, b, d - and results from the literature - for parameter l, where l denotes a maximum degree among leaders - and visualize them altogether in an overviewing graph, providing an easily accessible summary of the current state of the research of Hiding Leaders given the decision version of the problem, the degree centrality and the four aforementioned parameters.

Thesis on DSpace

Ing. Šimon Schierreich

doc. RNDr. Dušan Knop, Ph.D.

Department of Applied Mathematics

We study strategic games inspired by Schelling's segregation model. In these games, we study how agents of multiple types are moving on undirected graphs. We consider two types of agents: strategic} agents aim to maximize the fraction of their neighbors who have the same type, while stubborn agents do not move at all. We explore two common variants of the model: jump games, where agents can jump to empty nodes, and swap games, where agents move by swapping positions with other agents. We investigate the computational complexity of these games and the increase in social welfare when considering neighbors of stubborn agents. We propose a novel approach to classify games with maximal social welfare in equilibrium using a graph neural network.

Thesis on DSpace

Ing. Šimon Schierreich

doc. Ing. Ivan Šimeček, Ph.D.

Department of Applied Mathematics

In this paper we study a card game Cubirds form the viewpoint of complexity and finding a optimal winning strategy. We define a generalized mathematical model for the game. This model can be transformed to more simple variants of Cubirds. We analyze a one-player game and prove, that it is NP-complete problem. Next we create several heuristic algorithms for playing Cubirds. For the same reason we try to train a neural network with reinforcement learning method. At the end both approaches will be compared.

Thesis on DSpace