
Detekce skupin v davech pomocí časoprostorových dat
Říha, David ; Hartman, David (advisor) ; Neruda, Roman (referee)
This thesis addresses the challenge of social group detection in crowds, presenting an algorithm informed by sociological insights into common group formations among pedestrians. Our proposed algorithm demonstrates comparable performance to existing solutions  Timesequence DBSCAN and Agglomerative Hierarchical Clustering with Hausdorff Distance, using the DIAMOR dataset for testing and comparison. Additionally, we introduce a validator tool potentially capable of refining results from existing algorithms based on a group shape criterion, leading to improved accuracy in identifying groups. Keywords: groups detection; clustering; group shape analysis; pedestrian behavior;


Using gadget construction in structural convergence
Hons, Tomáš ; Hartman, David (advisor) ; Ossona de Mendez, Patrice (referee) ; Pultr, Aleš (referee)
Structural convergence is a framework for convergence of graphs and relational struc tures based on the probability of satisfaction of firstorder formulas. We consider gadget construction, which is a ubiquitous tool in many areas of mathematics, as a method for constructing convergent sequences of structures. Both for elementary and local conver gence, we investigate the behavior of a sequence created by gadget construction from convergent sequences of base structures and gadgets. We show that elementary conver gence is always preserved while additional assumptions are necessary for local convergence as witnessed by several examples. We give various different conditions that ensure local convergence. One of them states that the resulting sequence is local convergent if the replaced edges are dense in the sequence of base structures. The sufficient conditions are partially complemented by inverse theorems. 1


Graphlets in Complex Networks
Trlifaj, Daniel ; Hartman, David (advisor) ; Černý, Martin (referee)
Analyzing the characteristics of complex networks is a principal task of network sci ence. In this thesis, we study graphets, small induces subgraphs rooted in a vertex, as a tool to describe and compare networks. First, we use graph theory to explore the theo retical properties of graphlets, propose a framework for studying them, and make novel observations. We discuss the link between graphlets and the WeisfeilerLehman isomor phism test and the reconstruction conjecture. We prove that the knowledge of graphlets of size n − 1 for certain graphs is sufficient for their reconstruction. Second, we develop several graphletbased metrics and apply them to realworld networks and their models. In line with prior literature, the results suggest that graphlets are potentially an excellent tool of characterizing networks. Counter to prior literature, the results suggest that the AlbertBarabási model produces more realistic synthetic networks than other models. 1


Nodeattributed community detection
Vokálová, Kateřina ; Hartman, David (advisor) ; Korvasová, Karolína (referee)
Complex systems surround us in our everyday lives and their understanding can bring crucial insights into many fields. These systems consist of components (also known as communities) tied together. This thesis focuses on community detection in node attributed networks, which are networks with some extra information about nodes. At first, we introduced the necessary terminology and provided an overview of node attributed benchmarks used for testing. Then we studied the setting of the benchmark and algorithm parameters and discussed the obtained results. The analysis was made on synthetic networks and focused on the impact of the benchmark and algorithm parameters on the results, which we then discussed. In particular, we have found that the algorithms are less influenced by mixing parameter when the size of the network is bigger. We also confirmed our expectation, that results will be negatively influenced by higher mixing and noise parameters. 1


On the structure and values of betweenness centrality in dense betweennessuniform graphs
Ghanbari, B. ; Hartman, David ; Jelínek, V. ; Pokorná, Aneta ; Šámal, R. ; Valtr, P.
Betweenness centrality is a network centrality measure based on the amount of shortest paths passing through a given vertex. A graph is betweennessuniform (BUG)if all vertices have an equal value of betweenness centrality. In this contribution, we focus on betweennessuniform graphs with betweenness centrality below one. We disprove a conjecture about the existence of a BUG with betweenness value α for any rational numberαfrom the interval (3/4,∞) by showing that only very few betweenness centrality values below 6/7 are attained for at least one BUG. Furthermore, among graphs with diameter at least three, there are no betweennessuniform graphs with a betweenness centrality smaller than one. In graphs of smaller diameter, the same can be shown under a uniformity condition on the components of the complement.


Rooting algebraic vertices of convergent sequences
Hartman, David ; Hons, T. ; Nešetřil, J.
Structural convergence is a framework for convergence of graphs by Nešetřil and Ossona de Mendez that unifies the dense (left) graph convergence and BenjaminiSchramm convergence. They posed a problem asking whether for a given sequence of graphs (Gn) converging to a limit L and a vertex r of L it is possible to find a sequence of vertices (rn) such that L rooted at r is the limit of the graphs Gn rooted at rn. A counterexample was found by Christofides and Král’, but they showed that the statement holds for almost all vertices r of L. We offer another perspective to the original problem by considering the size of definable sets to which the root r belongs. We prove that if r is an algebraic vertex (i.e. belongs to a finite definable set), the sequence of roots (rn) always exists.


Analysis of blockchain used for Bitcoin
Surma, David ; Hartman, David (advisor) ; Hubáček, Pavel (referee)
This thesis deals with the analysis of the blockchain used for Bitcoin. Blockchain is a distributed database of all transactions made with this cryptocurrency. Its public availability represents the possibility of examining the transfer of funds between all users. However, they appear in transactions under anonymous addresses, the number of which is practically unlimited. The main goal of our work is to find a clustering of addresses corresponding to their belonging to real users. In this work, we propose new heuristics that can be used in clustering. The main benefit is a method that uses the properties of transactions created very quickly one after the other. Furthermore, we analyze the problem of the formation of a supercluster containing a disproportionately large number of addresses and propose a way in which the cluster can be appropriately partitioned. 1


Approximative symmetries of complex networks
Straka, Matej ; Hartman, David (advisor) ; Černý, Martin (referee)
The aim of this thesis is to investigate the problem of an approximate symmetry of complex networks. First, we analyze how to measure such symmetry. Then we explore two algorithms by which we can measure levels of symmetry of networks and also find permutations representing those symmetries. First method uses a simulated annealing algorithm which is very slow if implemented naively. We exploit properties of an objective function to make this approach much faster, making it usable for large networks. In second approach we modify an existing method for inexact graph matching, making it applicable for measuring symmetry. We then provide a comparison of these two approaches. We then apply these algorithms to explore levels of symmetry produced by artificial networks, which are used to generate networks with properties possessed by real sys tems. We explore how does our measure of an approximate symmetry correlate with other network measures, such as clustering coefficient or modularity. Finally, we measure symmetry of real brain networks and look where their symmetry comes from. 1


Utilization of brain connectivity in classification and regression tasks in brain data
Řežábková, Jana ; Hartman, David (advisor) ; Neruda, Roman (referee)
This thesis investigates how incorporating progressive amounts of struc tural information into machine learning models affects their accuracy in dis criminating schizophrenia from functional connectivity matrices obtained by resting state functional magnetic resonance. Three structural settings were exploredno structure via traditional machine learning models, modeling nodes through proposed feed forward based architecture that allows com bining node neighborhoods individually for each node, and modeling both nodes and edges using graph neural networks. Although the results on the available 190 subjects dataset did not reveal the best strategy, two findings were identified (a) the superiority of sparsifiying matrices by taking top k neighborhoods over keeping top n% values and (b) the benefit of node cor respondence across samples. All experiments were evaluated using a proper validation strategynested cross validationa piece that was largely missing in reviewed literature.


Computational models of dendritic cell development
Štráchalová, Sára ; Bílý, Tomáš (advisor) ; Hartman, David (referee)
Computational modelling is gradually establishing its place in biology and medicine as a tool for research of systems and prediction of their behaviour. In this thesis we propose and analyze a simple compartmental model of the immune system and its responses, focusing on dendritic cells. These cells are an important component of the immune system that is crucial for initiation of the specific part of immune response. The analysis focuses on the types of behaviour and stability of the model. We compare our results with already existing basic model of the immune system. 1
