Search

In application domains such as routing, network analysis, scheduling, and planning, directed graphs are widely used as both formal models and core data structures for the development of efficient algorithmic solutions. In these areas, graphs are often evolving in time: for example, connection links may fail due to temporary technical issues, meaning that edges of the graph cannot be traversed for some time interval and alternative paths have to be followed. In classical computation graphs have been implemented both explicitly through adjacency matrices/lists and symbolically as ordered binary decision diagrams. Moreover, ad-hoc visit procedures have been developed to deal with dynamically evolving graphs. Quantum computation, exploiting interference and entanglement, has provided an exponential speed-up for specific problems, e.g., database search and integer factorization. In the quantum framework everything must be represented and manipulated using reversible operators. This poses a challenge when one has to deal with traversals of dynamically evolving directed graphs. Graph traversals are not intrinsically reversible because of converging paths. In the case of dynamically evolving graphs also the creation/destruction of paths comes into play against reversibility. In this paper we propose a novel high level graph representation in quantum computation supporting dynamic connectivity typical of real-world network applications. Our procedure allows to encode any multigraph into a unitary matrix. We devise algorithms for computing the encoding that are optimal in terms of time and space and we show the effectiveness of the proposal with some examples. We describe how to react to edge/node failures in constant time. Furthermore, we present two methods to perform quantum random walks taking advantage of this encoding: with and without projectors. We implement and test our encoding obtaining that the theoretical bounds for the running time are confirmed by the empirical

Graphs are widely used to model object relationships in real world applications such as biology, neuroscience, and communication networks. Traditional graph analysis tools focus on extracting key graph patterns to characterize graphs which are further used in the downstream tasks such as prediction. Common graph characteristics include global and local graph measurements such as clustering coefficient, global efficiency, characteristic path length, diameter and so on. Many applications often involve high dimensional and large-scale graphs for which existing methods, which rely on small numbers of graph characteristics, cannot be used to efficiently perform graph tasks. A major research challenge is to learn graph representations that can be used to efficiently perform graph tasks as required by a wide range of applications. In this thesis, we have developed a number of novel methods to tackle the challenges associated with processing or representing large-scale graphs. In the first part, we propose a general graph coarsening framework that maps large graphs into smaller ones while preserving important structural graph properties. Based on spectral graph theory, we define a novel distance function that measures the differences between graph spectra of the original and coarse graphs. We show that the proposed spectral distance sheds light on the structural differences in the graph coarsening process. In addition, we propose graph coarsening algorithms that aim to minimize the spectral distance, with provably strong bounds. Experiments show that the proposed algorithms outperform previous graph coarsening methods in applications such as graph classification and stochastic block recovery tasks. In the second part, we propose a new graph neural network paradigm that improves the expressiveness of the best known graph representations. Graph neural network (GNN) models have recently been introduced to solve challenging graph-related problems. Most GNN models follow the mes

We consider the problem of finding an accurate representation of neuron shapes, extracting sub-cellular features, and classifying neurons based on neuron shapes. In neuroscience research, the skeleton representation is often used as a compact and abstract representation of neuron shapes. However, existing methods are limited to getting and analyzing curve skeletons which can only be applied for tubular shapes. This paper presents a 3D neuron morphology analysis method for more general and complex neuron shapes. First, we introduce the concept of skeleton mesh to represent general neuron shapes and propose a novel method for computing mesh representations from 3D surface point clouds. A skeleton graph is then obtained from skeleton mesh and is used to extract sub-cellular features. Finally, an unsupervised learning method is used to embed the skeleton graph for neuron classification. Extensive experiment results are provided and demonstrate the robustness of our method to analyze neuron morphology.

El grup de recerca DTIM de la UPC ha desenvolupat ODIN, una eina que permet la integració de fonts de dades en diferents formats emprant un model basat en grafs com a model canònic. Una de les finalitats d'aquest sistema és que l'usuari pugui consultar dades sobre l'esquema de dades integrat, però la interfície actual no es presenta gaire usable per als usuaris. Aquest projecte, com a Treball de Fi de Grau d'Enginyeria Informàtica, té la intenció de millorar la interfície de consultes de l'eina ODIN. Durant aquest treball s'explica tot el procediment per a dur a terme el desenvolupament i se centra en la interfície d'exploració del graf, creant una nova interfície que permet a l'usuari dur a terme consultes i explorar les dades d'una forma més senzilla i eficient tenint en compte la seva complexitat i facilitat d'ús., The DTIM research group in UPC has developed ODIN, a tool that allows the integration of data sources in different formats using a graph-based model as the canonical model. One of the purposes of this system is to let users query data on the built-in data schema, but the current interface is not very usable. This project, as a Bachelor's thesis in Software Engineering, intends to improve the query interface of the ODIN tool. During this thesis, the entire procedure to carry out the development is explained, and it focuses on the graph exploration interface, creating a new interface that allows the user to perform queries and explore data in a simpler and more efficient way, taking into account its complexity and ease of use.

In this research, the topic of graph coloring was addressed, which includes coloring vertices, coloring edges, and coloring faces. Some relationships between the chromatic number and some graphs were also proven, and the color number of faces was obtained for some graphs, and a historical overview of one of the most important theorems in graph theory represented by the four-color theorem, was presented. The four-color theorem is applied to the map of Iraq and then transformed the map of Iraq into a graph.

In this research, the topic of graph coloring was addressed, which includes coloring vertices, coloring edges, and coloring faces. Some relationships between the chromatic number and some graphs were also proven, and the color number of faces was obtained for some graphs, and a historical overview of one of the most important theorems in graph theory represented by the four-color theorem, was presented. The four-color theorem is applied to the map of Iraq and then transformed the map of Iraq into a graph.

Diffusion Magnetic Resonance Imaging (dMRI) is a method for measuring molecular diffusion in biological tissue microstructure. This information can be used to predict the location and orientation of white matter fibers in the brain, a process known as tractography. Analysis of the map of neural connections can provide meaningful information about the severity or progression of neurodegenerative diseases such as Alzheimer's, and allow for early intervention to prevent progression. However, tractography has its pitfalls; current fiber-tracking algorithms suffer from generating false-positive connections and affect the reliability of structural connectivity maps. To counter this downside, tractogram filtering methods have been created to remove inaccurately predicted connections. This study aims at evaluating the impact of the novel semi-supervised filtering method FINTA on the brain networks of people with Mild Cognitive Impairment (MCI), which precedes diseases like Alzheimer's. The proposed experiments use the Nipype Neuroimaging Python library for the automation of the entire process. Registration, parcellation, and tracking were performed using MRtrix and FSL. Furthermore, DIPY and NiBabel were used for tractogram processing. Finally, filtering was performed based on code provided by the authors of FINTA, and graph measures were computed using the NetworkX Python library. Experiments were performed on both raw and weighted structural connectivity matrices. Results suggest that filtering has an effect on graph measures such as the clustering coefficient and betweenness centrality for different nodes corresponding to brain regions., Diffusion magnetisk resonanstomografi (diffusions MRT) är en metod för att mäta den molekylära diffusionen i mikrostrukturen i biologisk vävnad. Denna information kan användas för att förutsäga var fibrerna i den vita substansen i hjärnan befinner sig och hur de är orienterade i den process som kallas traktografi. Analys av kartan över nervförbindelser kan ge meningsfull information om svårighetsgraden eller utvecklingen av neurodegenerativa sjukdomar som Alzheimers och möjliggöra tidiga insatser för att förhindra utvecklingen. Traktografi har dock sina fallgropar och nuvarande algoritmer för fiberspårning lider av att generera falska positiva anslutningar och påverkar de strukturella konnektivitetskartorna som förhindrar tillförlitliga förutsägelser. För att motverka denna nackdel har filtreringsmetoder för traktogram skapats för att ta bort de felaktigt förutsagda anslutningarna. Denna studie syftar till att utvärdera effekterna av den nya semi-övervakade filtreringsmetoden FINTA på hjärnnätverk hos personer med lindrig kognitiv störning (eng. mild cognitive impairment, MCI) som föregår sjukdomar som Alzheimers. I de föreslagna experimenten används Python-biblioteket Nipype Neuroimaging för automatisering av hela processen. Registrering, parcellering och spårning gjordes med hjälp av MRtrix och FSL, dessutom användes DIPY och NiBabel för traktogrambehandling. Slutligen utfördes filtrering baserat på kod från författarna till FINTA och grafmått beräknades med hjälp av NetworkX Python-bibliotek. Experimenten utfördes på råa och viktade strukturella konnektivitetsmatriser. Resultaten tyder på att filtrering har en effekt på grafmått som klustringskoefficient och betweenness centrality för olika noder som motsvarar hjärnregioner.

We describe a class of nilpotent Lie algebras completely determined by their associated weight graph. These algebras also present two important structural properties: to admit naturally a symplectic form and to be isomorphic to the nilradical of a solvable complete rigid Lie algebra. These solvable algebras are proved to constitute a class of algebras where a symplectic form cannot exist. Finally we analyze the product by generators of the preceding algebras, and show that this operator preserves the property of being the maximal nilpotent ideal of a solvable rigid Lie algebra, Fundacion Ramón Areces, Depto. de Álgebra, Geometría y Topología, Fac. de Ciencias Matemáticas, TRUE, pub

CRUE-CSIC (Acuerdos Transformativos 2023), In this paper we introduce a new species of evolution algebras that we call Cayley evolution algebras. We show that if a field k contains sufficiently many elements (for example if k is infinite) then every finite group G is isomorphic to Aut(X) where X is a finite-dimensional absolutely simple Cayley evolution k-algebra., Ministerio de Ciencia e Innovación (MICIN), Junta de Andalucía, Depto. de Álgebra, Geometría y Topología, Fac. de Ciencias Matemáticas, TRUE, pub

En la actualidad, la ciudadanía recibe una gran cantidad de información desde medios de comunicación, prensa o redes sociales. En algunas ocasiones, esta información incluye gráficos estadísticos que contienen sesgos, por lo que es esencial que los ciudadanos y ciudadanas desarrollen unos conocimientos, destrezas y actitudes adecuadas para realizar una lectura crítica antes de asumirlos como ciertos. Por ello, en este trabajo, desde el marco teórico de las estadísticas cívicas, se ha realizado un análisis cualitativo de los errores cometidos por 305 estudiantes de cuatro centros diferentes de educación secundaria al interpretar noticias sesgadas que incluían gráficos y provenían de los medios de comunicación. En ninguna de las dos noticias se tenía en cuenta el tamaño de la población, por lo que esto podía provocar conclusiones erróneas. Se llegó a la conclusión de que una gran parte de los sujetos encuestados asumen la información que reciben como cierta, sin antes realizar una lectura crítica de ella. Además, no son capaces de interpretar ciertos gráficos y tienen dificultades también para comprender que el contexto de la noticia puede ser esencial para realizar conclusiones acertadas sobre ella. Conocer estos errores será fundamental para poder trabajarlos posteriormente, haciendo especial énfasis en los más habituales, y así formar ciudadanos estadísticamente cultos., Nowadays, citizens receive a great deal of information from the media, press or social networks. On some occasions, this information includes statistical graphs that contain biases. Therefore, it is essential that citizens develop adequate knowledge, skills and attitudes in order to adopt a critical attitude before accepting them as true. For this reason, framed in the theoretical framework of civic statistics, errors made by 305 students from four different Compulsary Secondary Education schools when interpreting biased news media items that included graphs were analysed. Neither of the two news items took into account the size of the population, which could lead to erroneous conclusions. It was concluded that a large proportion of the subjects surveyed assume the information they receive to be true, without first criticising it. In addition, they are not able to interpret certain graphics and they also have difficulties in understanding that the context of the news item may be essential for drawing accurate conclusions about it. Knowing about these errors will be fundamental in order to be able to work on them later, with special emphasis on the most common ones, and thus form statistically literate citizens

We define a new type of graph of a group with reference to the descending endomorphisms of the group. A descending endomorphism of a group is an endomorphism that induces a corresponding endomorphism in every homomorphic image of the group. We define the undirected (directed) descending endomorphism graph of a group as the undirected (directed) graph whose vertex set is the underlying set of the group, in which there is an undirected (directed) edge from one vertex to another if the group has a descending endomorphism that maps the former element to the latter. We investigate some basic properties of these graphs and show that they are closely related to power graphs. We also determine the descending endomorphism graphs of symmetric, dihedral, and dicyclic groups.

The paradigm of learning to optimise relies on the following principle: instead of designing an algorithm to solve a problem, we design an algorithm which will automate the design of such a solver. The initial idea was to alleviate the limitations stated by the No Free Lunch Theorem by producing an algorithm which efficiency is less dependent upon known instances of the problem to tackle. Hyper-heuristics constitute the main learning-to-optimise techniques. These rely on a high-level algorithm performing a search process into a space of low-level heuristics to tackle a given problem. Because the latter search space is problem-dependent, the vast majority of hyper-heuristics are designed to tackle a specific problem. Due to this lack of generality, existing works fully redesign hyper-heuristics when tackling a new problem, despite the fact that they may share a similar structure. In this dissertation, we tackle this challenge by proposing a generic way for learning to optimise any problem. To this end, this thesis introduces three main contributions: (i) an analysis of the formal functioning of learning-to-optimise techniques; (ii) a model of generic hyper-heuristic, named Algorithm Learner for Graph Optimisation problems (ALGO), constituting the central point of this work; (iii) a real-world use case where we use our generic hyper-heuristic to automate the design of behaviours within a swarm of drones. In the first part, we provide a formalism for optimisation and learning concepts, which we use to describe the large body of knowledge that combines two layers of optimisation and/or learning. We then put an emphasis on approaches using learning to improve an optimisation process, i.e., aiming at learning to optimise. In the second part, we present ALGO, our model of generic hyper-heuristic. We explain how we abstract from a given problem with a graph structure so that it can be used to tackle any optimisation problem. We also detail the steps to follow in order to us

Cloud computing has become an increasingly popular choice for businesses and individuals due to its flexibility, scalability, and convenience; however, the rising cost of cloud resources has become a significant concern for many. The pay-per-use model used in cloud computing means that costs can accumulate quickly, and the lack of visibility and control can result in unexpected expenses. The cost structure becomes even more complicated when dealing with hybrid or multi-cloud environments. For businesses, the cost of cloud computing can be a significant portion of their IT budget, and any savings can lead to better financial stability and competitiveness. In this respect, it is essential to manage cloud costs effectively. This requires a deep understanding of current resource utilization, forecasting future needs, and optimising resource utilization to control costs. To address this challenge, new tools and techniques are being developed to provide more visibility and control over cloud computing costs. In this respect, this paper explores a graph-based solution for modelling cost elements and cloud resources and potential ways to solve the resulting constraint problem of cost optimisation. We primarily consider utilization, cost, performance, and availability in this context. Such an approach will eventually help organizations make informed decisions about cloud resource placement and manage the costs of software applications and data workflows deployed in single, hybrid, or multi-cloud environments., Part of ISBN 9798350326970QC 20230920

This work introduces a data model, compiler and runtime interpreter to drive the logic of animation graphs in game engines. The primary purpose of an animation graph is to allow for animation logic to be evaluated in a data driven way, which enables game programmers and animators to work iteratively and in parallel. The combination of animation blend trees and hierarchical state machines serves to empower animators to break down the complexity into simpler units with precise and predictable control over animation sampling and the transitions between them. Additionally, the system also serves as a synchronization point between game play elements and animation with input parameters and output events which can potentially trigger other systems such as audio and visual effects. The result is a standalone library which can be used as a foundation in a project and expanded with additional functionality as required., Detta arbete introducerar en data model, kompilator och körmiljö för att driva logiken av animationsgrafer i spelmotorer. Huvudsyftet av en animationsgraf är att tillåta datadrivet animationslogik vilket möjliggör spelprogrammerare och animerare att arbeta iterativt och parallellt. Kombinationen av animationblandningsträd och hierarkiska statmaskiner ger animerare ett sätt att bryta ner komplexa problem till mindre enheter med exakt och förutsägbar kontroll av animationer och övergångar mellan dem. Systemet verkar också som en synkroniseringspunkt mellan spelelement och animation med inmatningsparameterar och utgående händelser som potentiellt kan utlösa andra system som ljud- och visuella effekter. Resultatet är ett fristående programbibliotek som kan användas som en startpunkt i ett projekt och vars funktionalitet kan utökas vid behov.

This paper was written as a bachelor thesis in mathematics. We study adjacency matrices and their eigenvalues to investigate what properties of the corresponding graphs can be determined by those eigenvalues, the spectrum of the graph. The question of which graphs are uniquely determined by their spectra is also covered. Later on we study some methods of finding examples of graphs with shared spectra, also referred to as cospectral graphs.

Algoritmy z teorie grafů mají velké použití např. v logistice, plánování projektů a v různých typech sítí. U některých algoritmů se nevyhneme rekurzi - tedy rozkladu problému na podproblémy. Cílem práce bude studium rekurzivních grafových algoritmů a jejich použitelnosti na konkrétních úlohách. Jako příklad uveďme např. určení všech možných maximálních toků v síti či určení všech nejkratších cest. Cílem teoretické části bude popis rekurzivních grafových algoritmů. Cílem praktické jejich implementace ve vlastní aplikaci., Algorithms from graph theory have many applications in e.g., logistics, project planning and various types of networks. For some algorithms, recursion - i.e., decomposing the problem into subproblems - is unavoidable. The aim of this paper will be to study recursive graph algorithms and their applicability to specific problems. Examples include determining all possible maximum flows in a network or determining all shortest paths. The aim of the theoretical part will be to describe recursive graph algorithms. The goal of the practical part is to implement them in own application., Fakulta elektrotechniky a informatiky, Obhajoba bakalářské práce proběhla na požadované úrovni, student prezentoval výsledky své bakalářské práce a zodpověděl dotazy vedoucího bakalářské práce. Dle vedoucího splňuje bakalářská práce veškeré náležitosti a cíle práce byly splněny v plném rozsahu. Cílem práce bylo studium rekurzivních algoritmů a jejich aplikace v problémech z teorie grafů na konkrétních úlohách ve vlastní aplikaci., Dokončená práce s úspěšnou obhajobou

The paradigm of learning to optimise relies on the following principle: instead of designing an algorithm to solve a problem, we design an algorithm which will automate the design of such a solver. The initial idea was to alleviate the limitations stated by the No Free Lunch Theorem by producing an algorithm which efficiency is less dependent upon known instances of the problem to tackle. Hyper-heuristics constitute the main learning-to-optimise techniques. These rely on a high-level algorithm performing a search process into a space of low-level heuristics to tackle a given problem. Because the latter search space is problem-dependent, the vast majority of hyper-heuristics are designed to tackle a specific problem. Due to this lack of generality, existing works fully redesign hyper-heuristics when tackling a new problem, despite the fact that they may share a similar structure. In this dissertation, we tackle this challenge by proposing a generic way for learning to optimise any problem. To this end, this thesis introduces three main contributions: (i) an analysis of the formal functioning of learning-to-optimise techniques; (ii) a model of generic hyper-heuristic, named Algorithm Learner for Graph Optimisation problems (ALGO), constituting the central point of this work; (iii) a real-world use case where we use our generic hyper-heuristic to automate the design of behaviours within a swarm of drones. In the first part, we provide a formalism for optimisation and learning concepts, which we use to describe the large body of knowledge that combines two layers of optimisation and/or learning. We then put an emphasis on approaches using learning to improve an optimisation process, i.e., aiming at learning to optimise. In the second part, we present ALGO, our model of generic hyper-heuristic. We explain how we abstract from a given problem with a graph structure so that it can be used to tackle any optimisation problem. We also detail the steps to follow in order to us

Sequential recommendation has been a widely popular topic of recommender systems. Existing works have contributed to enhancing the prediction ability of sequential recommendation systems based on various methods, such as recurrent networks and self-attention mechanisms. However, they fail to discover and distinguish various relationships between items, which could be underlying factors which motivate user behaviors. In this article, we propose an Edge-Enhanced Global Disentangled Graph Neural Network (EGD-GNN) model to capture the relation information between items for global item representation and local user intention learning. At the global level, we build a global-link graph over all sequences to model item relationships. Then a channel-aware disentangled learning layer is designed to decompose edge information into different channels, which can be aggregated to represent the target item from its neighbors. At the local level, we apply a variational auto-encoder framework to learn user intention over the current sequence. We evaluate our proposed method on three real-world datasets. Experimental results show that our model can get a crucial improvement over state-of-the-art baselines and is able to distinguish item features.

[Abstract]: In this paper we introduce a new species of evolution algebras that we call Cayley evolution algebras. We show that if a field k contains sufficiently many elements (for example if k is infinite) then every finite group G is isomorphic to Aut(X) where X is a finite-dimensional absolutely simple Cayley evolution k-algebra.

It is standard in chemistry to represent a sequence of reactions by a single overall reaction, often called a complex reaction in contrast to an elementary reaction. Photosynthesis is an example of such complex reaction. We introduce a mathematical operation that corresponds to summing two chemical reactions. Specifically, we define an associative and non-communicative operation on the product space (representing the reactant and the product of a chemical reaction, respectively). The operation models the overall effect of two reactions happening in succession, one after the other. We study the algebraic properties of the operation and apply the results to stochastic reaction networks (RNs), in particular to reachability of states, and to reduction of RNs.

Elliptic multiple polylogarithms occur in Feynman integrals and in particular in scattering amplitudes. They can be characterized by their symbol, a tensor product in the so-called symbol letters. In contrast to the non-elliptic case, the elliptic letters themselves satisfy highly non-trivial identities, which we discuss in this paper. Moreover, we introduce the symbol prime, an analog of the symbol for elliptic symbol letters, which makes these identities manifest. We demonstrate its use in two explicit examples at two-loop order: the unequal-mass sunrise integral in two dimensions and the ten-point double-box integral in four dimensions. Finally, we also report the result of the polylogarithmic nine-point double-box integral, which arises as the soft limit of the ten-point integral.

Schur decompositions and the corresponding Schur forms of a single matrix, a pair of matrices, or a collection of matrices associated with the periodic eigenvalue problem are frequently used and studied. These forms are upper-triangular complex matrices or quasi-upper-triangular real matrices that are equivalent to the original matrices via unitary or, respectively, orthogonal transformations. In general, for theoretical and numerical purposes we often need to reduce, by admissible transformations, a collection of matrices to the Schur form. Unfortunately, such a reduction is not always possible. In this paper we describe all collections of complex (real) matrices that can be reduced to the Schur form by the corresponding unitary (orthogonal) transformations and explain how such a reduction can be done. We prove that this class consists of the collections of matrices associated with pseudoforest graphs. In other words, we describe when the Schur form of a collection of matrices exists and how to find it.

This paper proposes a temporal graph neural network model for forecasting of graph-structured irregularly observed time series. Our TGNN4I model is designed to handle both irregular time steps and partial observations of the graph. This is achieved by introducing a time-continuous latent state in each node, following a linear Ordinary Differential Equation (ODE) defined by the output of a Gated Recurrent Unit (GRU). The ODE has an explicit solution as a combination of exponential decay and periodic dynamics. Observations in the graph neighborhood are taken into account by integrating graph neural network layers in both the GRU state update and predictive model. The time-continuous dynamics additionally enable the model to make predictions at arbitrary time steps. We propose a loss function that leverages this and allows for training the model for forecasting over different time horizons. Experiments on simulated data and real-world data from traffic and climate modeling validate the usefulness of both the graph structure and time-continuous dynamics in settings with irregular observations.

This work introduces a data model, compiler and runtime interpreter to drive the logic of animation graphs in game engines. The primary purpose of an animation graph is to allow for animation logic to be evaluated in a data driven way, which enables game programmers and animators to work iteratively and in parallel. The combination of animation blend trees and hierarchical state machines serves to empower animators to break down the complexity into simpler units with precise and predictable control over animation sampling and the transitions between them. Additionally, the system also serves as a synchronization point between game play elements and animation with input parameters and output events which can potentially trigger other systems such as audio and visual effects. The result is a standalone library which can be used as a foundation in a project and expanded with additional functionality as required., Detta arbete introducerar en data model, kompilator och körmiljö för att driva logiken av animationsgrafer i spelmotorer. Huvudsyftet av en animationsgraf är att tillåta datadrivet animationslogik vilket möjliggör spelprogrammerare och animerare att arbeta iterativt och parallellt. Kombinationen av animationblandningsträd och hierarkiska statmaskiner ger animerare ett sätt att bryta ner komplexa problem till mindre enheter med exakt och förutsägbar kontroll av animationer och övergångar mellan dem. Systemet verkar också som en synkroniseringspunkt mellan spelelement och animation med inmatningsparameterar och utgående händelser som potentiellt kan utlösa andra system som ljud- och visuella effekter. Resultatet är ett fristående programbibliotek som kan användas som en startpunkt i ett projekt och vars funktionalitet kan utökas vid behov.

This paper was written as a bachelor thesis in mathematics. We study adjacency matrices and their eigenvalues to investigate what properties of the corresponding graphs can be determined by those eigenvalues, the spectrum of the graph. The question of which graphs are uniquely determined by their spectra is also covered. Later on we study some methods of finding examples of graphs with shared spectra, also referred to as cospectral graphs.

This manuscript introduces a finite collection of generalized permutohedra associated to a simple graph. The first polytope of this collection is the graphical zonotope of the graph and the last is the graph–associahedron associated to it. We describe the weighted integer points enumerators for polytopes in this collection as Hopf algebra morphisms of combinatorial Hopf algebras of decorated graphs. In the last section, we study some properties related to H–polytopes.

Graph topology inference is a research field that studies how to learn the structure of a graph from data related to it. It is a very popular research topic in which algorithms are being developed faster and more efficient year after year. Graphs are a mathematical tool that allows us to model relationships between data obtained from complex structures, such as the human brain. In this thesis, we have developed a graph topology inference algorithm based on the estimation of the precision matrix with Laplacian constraints, where we have used real data obtained by f-MRI to evaluate the algorithm. Then, we have applied network science parameters, such as the small-world parameter, in order to compare different graph network topologies and provide valuable information about the structure of these graphs., La inferencia de topología de grafos es un campo de investigación en el que se estudia cómo aprender la estructura de un grafo a partir de datos relacionados con él. Es un tema de investigación muy popular en el que se desarrollan algoritmos cada vez más rápidos y eficientes año tras año. Los grafos son una herramienta matemática que nos permite modelar las relaciones entre datos obtenidos en estructuras complejas, como por ejemplo el cerebro humano. En esta tesis, hemos desarrollado un algoritmo de inferencia de topología de grafos basado en la estimación de la matriz de precisión con restricciones de Laplaciana, donde hemos utilizado datos reales obtenidos por f-MRI para evaluar el algoritmo. Después, hemos aplicado parámetros de ciencia de redes, como por ejemplo el parámetro "small-world", para poder comparar diferentes topologías de grafos y proporcionar una información valiosa sobre la estructura de estos grafos., La inferència de topologia de grafs és un camp de recerca en el qual s'estudia com aprendre l'estructura d'un graf a partir de dades relacionades amb ell. És un tema de recerca molt popular en el qual es desenvolupen algorismes cada vegada més ràpids i eficients any rere any. Els grafs són una eina matemàtica que ens permet modelar les relacions entre dades obtingudes en estructures complexes, com per exemple el cervell humà. En aquesta tesi, hem dut a terme un algorisme d'inferència de topologia de grafs basat en l'estimació de la matriu de precisió amb restriccions de Laplaciana, on hem utilitzat dades reals aconseguides per f-MRI per avaluar l'algorisme. Després, hem aplicat paràmetres de ciència de xarxes, com per exemple el paràmetre "small-world", per poder comparar diferents topologies de grafs i proporcionar una informació valuosa sobre l'estructura d'aquests grafs.

Aviation is characterized by many stakeholders, long lifespans of its assets, and high requirements regarding safety, security, and documentation. To meet these requirements as well as customer needs, aircraft are regularly retrofitted with new cabins. During the planning and execution of this cabin retrofit, handling the needed and available data poses a challenge to the engineers. While much of the required data is available in some form, generally there is a lack of a digitally usable dataset of the specific aircraft—a virtual representation of the physical asset is missing. To support the implementation of such a digital twin and, thus, the overall process of retrofitting aircraft, an approach to model-driven data handling tailored to the unique circumstances and requirements of aviation is introduced. The methodology consists of a combination of systems engineering and data science techniques framed by an overarching procedure that iteratively creates and enhances a digitally accessible dataset of the relevant data, hence supporting the retrofit engineers by easing access to needed information. Besides the presentation of the research background and the methodology, a simplified example is shown, demonstrating the approach using abstracted but realistic information provided by partners from the industry., Aviation is characterized by many stakeholders, long lifespans of its assets, and high requirements regarding safety, security, and documentation. To meet these requirements as well as customer needs, aircraft are regularly retrofitted with new cabins. During the planning and execution of this cabin retrofit, handling the needed and available data poses a challenge to the engineers. While much of the required data is available in some form, generally there is a lack of a digitally usable dataset of the specific aircraft - a virtual representation of the physical asset is missing. To support the implementation of such a digital twin and, thus, the overall process of retrofitting aircraft, an approach to model-driven data handling tailored to the unique circumstances and requirements of aviation is introduced. The methodology consists of a combination of systems engineering and data science techniques framed by an overarching procedure that iteratively creates and enhances a digitally accessible dataset of the relevant data, hence supporting the retrofit engineers by easing access to needed information. Besides the presentation of the research background and the methodology, a simplified example is shown, demonstrating the approach using abstracted but realistic information provided by partners from the industry.

Elliptic multiple polylogarithms occur in Feynman integrals and in particular in scattering amplitudes. They can be characterized by their symbol, a tensor product in the so-called symbol letters. In contrast to the non-elliptic case, the elliptic letters themselves satisfy highly non-trivial identities, which we discuss in this paper. Moreover, we introduce the symbol prime, an analog of the symbol for elliptic symbol letters, which makes these identities manifest. We demonstrate its use in two explicit examples at two-loop order: the unequal-mass sunrise integral in two dimensions and the ten-point double-box integral in four dimensions. Finally, we also report the result of the polylogarithmic nine-point double-box integral, which arises as the soft limit of the ten-point integral.

Differential privacy (DP) has become the de facto standard of privacy protection. For graphs, there are two widely used definitions of differential privacy, namely, edge differential privacy (edge-DP) and node differential privacy (node-DP), and node-DP is preferred when the minimal unit of interest is a node. To preserve node-DP, one can develop different methods to answer each specific graph query, or develop a graph publishing method to answer all graph queries. However, no existing works worked on such graph publishing methods. In this work, we propose two methods for publishing graphs under node-DP. One is the node-level perturbation algorithm which modifies the input graph by randomly inserting and removing nodes. The other one is the edge-level perturbation algorithm which randomly removing edges and inserting nodes. Both methods can achieve a flexible privacy guarantee by adjusting the running parameters. We conduct extensive experiments on both real-world and synthetic graphs to show the effectiveness and efficiency of proposed algorithms.

Data visualization aims to effectively communicate quantitative information by understanding which techniques and displays work better for different circumstances and why. There are a variety of software solutions capable of generating a multitude of different visualizations of the same dataset. However, data visualization ex poses a large space of visual configurations depending on the type of data to be visualized, the different displays (e.g., scatter plots, line graphs, pie charts), the visual components to encode the data (e.g., lines, dots, bars), or the specific visual attributes of those com ponents (e.g., color, shape, size, length). Researchers and developers are not usually aware about best practices in data visualization, and they are required to learn about both the design practices that make communication effective and the low level details of the specific software tool used to generate the visualization. This paper pro poses a software product line approach to model and materialize the variability of the visualization design process, guided by fea ture models. We encode the visualization knowledge regarding the best design practices, resolve the variability following a step-wise configuration approach, and then evaluate our proposal for a spe cific software visualization tool. Our solution helps researchers and developers communicate their quantitative results effectively by assisting them in the selection and generation of the visualizations that work best for each case. We open a new window of research where data visualization and variability meet each other.

Graphs are one of the most common data structures in classical computer science and graph theory has been widely used in complexity and computability. Recently, the use of graphs in application domains such as routing, network analysis and resource allocation has become crucial. In these areas, graphs are often evolving in time: for example, connection links may fail due to temporary technical issues, meaning that edges of the graph cannot be traversed for some time interval and alternative paths have to be followed. In classical computation, where graphs are represented as adjacency matrices or lists, these problems are well studied and ad-hoc visit procedures have been developed. For specific problems quantum computation, through superpositions and entanglement has provided faster algorithms than their classical counterpart. However, in this model, only reversible operations are allowed and this poses the quest of augmenting a graph in order to be able to reverse edge traversals. In this paper we present a novel graph representation in quantum computation supporting dynamic connectivity typical of real-world network applications. Our proposal has the advantage of being closer than others in literature to the adjacency matrix of the graph. This makes easy dynamic edge-failure modeling. We introduce optimal algorithms for computing our graph encoding and we show the effectiveness of our proposal with some examples.

Data visualization aims to effectively communicate quantitative information by understanding which techniques and displays work better for different circumstances and why. There are a variety of software solutions capable of generating a multitude of different visualizations of the same dataset. However, data visualization ex poses a large space of visual configurations depending on the type of data to be visualized, the different displays (e.g., scatter plots, line graphs, pie charts), the visual components to encode the data (e.g., lines, dots, bars), or the specific visual attributes of those com ponents (e.g., color, shape, size, length). Researchers and developers are not usually aware about best practices in data visualization, and they are required to learn about both the design practices that make communication effective and the low level details of the specific software tool used to generate the visualization. This paper pro poses a software product line approach to model and materialize the variability of the visualization design process, guided by fea ture models. We encode the visualization knowledge regarding the best design practices, resolve the variability following a step-wise configuration approach, and then evaluate our proposal for a spe cific software visualization tool. Our solution helps researchers and developers communicate their quantitative results effectively by assisting them in the selection and generation of the visualizations that work best for each case. We open a new window of research where data visualization and variability meet each other.

Robin Kaiser, Masterarbeit University of Innsbruck 2022

The processing of sorted key-value arrays using a "merge style operation (MSO)"is a very basic and important problem in domains like scientific computing, deep learning, database, graph analysis, sorting, set-operation etc. MSOs dominate the execution time in some important applications like SpGEMM and graph mining. For example, sparse vector addition as an MSO takes up to 98% execution time in SpGEMM in our experiment. For this reason, accelerating MSOs on CPU, GPU, and accelerators using parallel execution has been extensively studied but the solutions in prior work have three major limitations. (1) They treat different MSOs as isolated problems using incompatible methods and an unified solution is still lacking. (2) They do not have the flexibility to support variable key/value sizes and value calculations in the runtime given a fixed hardware design. (3) They require a quadratic hardware cost (O(V2)) for given parallelism V in most cases. To address above three limitations, we make the following efforts. (1) We present a one-for-All solution to support all interested MSOs based on a unified abstraction model "restricted zip machine (RZM)". (2) We propose a set of composable and parallel primitives for RZM to provide the flexibility to support variable key/value sizes and value calculations. (3) We provide the hardware design to implement the proposed primitives using only O(Vlog(V)) resource. With the above techniques, a flexible and efficient solution for MSOs has been built. Our design can be used either as a drop-in replacement of the merge unit in prior accelerators to reduce the cost from O(V2) to O(Vlog(V)), or as an extension to the SIMD ISA of CPU and GPU. In our evaluation on CPU, when V=16 (512-bit SIMD, 32-bit element), we achieve significant speedup on a range of representative kernels including set operations (8.4×), database joins (7.3×), sparse vector/matrix/tensor addition/multiplication on real/complex numbers (6.5×), merge sort (8.0× over scala

In 1959, Dijkstra announced a method for determining the shortest path between two nodes in a network. This algorithm has received much attention because it can deal with various real-life problems. The algorithm is a greedy type. Other types of algorithms are also created and compared. Application-related changes are made to the original algorithm. The time complexity of the algorithm increases at the expense of space complexity. Space is more complex with modern hardware, so that you can implement such an algorithm.

Graph processing is an area that has received significant attention in recent years due to the substantial expansion in industries relying on data analytics. Alongside the vital role of finding relations in social networks, graph processing is also widely used in transportation to find optimal routes and biological networks to analyse sequences. The main bottleneck in graph processing is irregular memory accesses rather than computation intensity. Since computational intensity is not a driving factor, we propose a method to perform graph processing at the edge more efficiently. We believe current cloud computing solutions are still very costly and have latency issues. The results demonstrate the benefits of a dedicated sparse graph processing algorithm compared with dense graph processing when analysing data with low density. As graph datasets grow exponentially, traversal algorithms such as breadth-first search (BFS), fundamental to many graph processing applications and metrics, become more costly to compute. Our work focuses on reviewing other implementations of breadth-first search algorithms designed for low power systems and proposing our solution that utilises advanced enhancements to achieve a significant performance boost up to 9.2x better performance in terms of MTEPS compared to other state-of-the-art solutions with a power usage of 2.32W.

The peripheral nervous system can be seen as a huge network of neurons that prop-agates signals across the human body. In fact, as seen in [1] , "All the information streaming in the peripheral nervous system (PNS) is transmitted along axons byelectro-chemical signals called action potentials". The ordinary conduction of such nervous signals, or action potentials, can be prevented however due to nerve damage. In this context, the accurate passage of information to an intended destination or partwithin the organism is obstructed. Admittedly, it is understood that physiotherapy can be quite helpful in regaining correct functionality over a damaged part of the peripheral nervous system. Yet, it is still hard to visualize the nervous activity as it is achieved inside the human body. Simulating the nervous system would providea platform to visualize how the system works and how a damaged nerve can affect the PNS. Indeed, the purpose of this study is to simulate a virtual network that im-itates a general topology of the human peripheral nervous system e.g(simulate the nervous structure and behaviour of the human arm) that shows how the signals canbe routed to their correct destination and showcase how can the simulator created simulate biological nerve damage in its system.

The Gaussian Conditional Random Fields (GCRF) algorithm and its extensions are used for machine learning regression problems in which the attributes of objects and the correlation between objects should be considered when making predictions. These algorithms can be applied in different domains where problems can be seen as graphs, but their implementation requires complex calculations and good programming skills. This paper presents an open source software package that includes a tool with graphical user interface (GCRFs tool) and Java library (GCRFs library). GCRFs tool is software that integrates various GCRF-based algorithms and supports training and testing of those algorithms on real-world datasets. The main goal of GCRFs tool is to provide a straightforward and user-friendly graphical user interface that will simplify the use of GCRF-based algorithms. GCRFs Java library contains basic classes for GCRF concepts and can be used by researchers who have experience in Java programming. Also, this paper presents the results of a pilot usability evaluation of the GCRFs tool, where the software was evaluated with expert and non-expert users. This evaluation gave us detailed insight into the experiences and opinions of the users and helped us outline priorities for future development.

El camp de recerca de les xarxes neuronals aplicades a grafs (GNN) ha experimentat un creixement explosiu en els darrers anys. Aquesta és una conseqüència de la seva capacitat única per gestionar dades en forma de graf, una estructura de dades molt comuna que s'aplica àmpliament a innombrables indústries, des de la sanitat fins als sistemes de recomanació. Malgrat la popularitat, encara hi ha alguns aspectes que no s'han desenvolupat tant com d'altres. Un dels casos és la recerca de maneres més eficients de computar-los. Aquest problema pateix d'una complexitat important, a causa de la flexibilitat dels grafs per adaptar-se a una àmplia gamma de problemes. Les dissimilaritats estructurals entre diferents grafs dificulten el disseny d'un algorisme eficient amb una bona generalització. Juntament amb això, també hi ha la qüestió de la quantitat considerable de multiplicacions de matrius esparses que afecten negativament a l'eficiència. S'han proposat diversos nous algorismes d'acceleració, inclosos els enfocats al software, hardware i el hardware-software. Hi ha acceleradors que es basen a representar el graf d'entrada d'una forma més adequada per al hardware per tal d'aconseguir l'acceleració. Altres utilitzen un esquema diferent per calcular el graf per aprofitar diferents plataformes hardware. En aquesta tesi suggerim dues hipòtesis. A la llum del fet que no tots els acceleradors funcionen bé per a tots els grafs, la nostra primera hipòtesi és que no hi ha cap accelerador que funcioni bé per a tots els grafs. La segona hipòtesi és que, donada una caracterització adequada del graf, podem predir quin pot ser el millor accelerador entre una selecció d'ells. Per donar una resposta a ambdues hipòtesis, comparem dues alternatives de càlcul GNN: deep graph library (DGL) com a model de referència i TC-GNN com a accelerador de software per a GNN. La comparació es fa a través d'un conjunt de grafs tan ampli i complet com sigui possible, que contingui grafs de moltes estructur, The research field of Graph Neural Networks (GNNs) has been experimenting an explosive growth in the recent years. This is a consequence of their unique capability to manage graph data, a highly common data structure which is widely applied across innumerable industries ranging from healthcare to recommendation systems. Despite the popularity, there are still some aspects which have not been developed as much as others. One of the cases is the research on more efficient ways of computing. This problem suffers from a significant complexity, due to the flexibility of graph for adapting a wide range of problems. The structural dissimilarities between different graphs makes it difficult to design an efficient computing algorithm with good generalization. Along with that, there is also the problem of the considerable amount of sparse matrix multiplications which impact negatively on efficiency. Several new acceleration algorithms have been proposed, including software, hardware and hardware-software co-design approaches. There are accelerators which rely on represent the input graph in a more suitable form for hardware in order to get the speedup. Others use a different schema of computing the graph for taking advantage of different hardware platforms. In this thesis, we propose two hypotheses. In light of the fact that not all accelerators work well for all graphs, our first assumption is that there is no accelerator that works well for all graphs.The second hypothesis follows that, given a proper graph characterization, we can predict which can be the best accelerator among selection of them. Towards providing an answer to both hypotheses, we compare two GNN computing alternatives: deep graph library (DGL) as a baseline library and TC-GNN as a software accelerator for GNNs. The comparison is done over a wide and comprehensive graph dataset which contains graphs of many different structures. To that end, we use a synthetic graph generator, GraphLaxy, from our research g