Search

L'objectiu principal d'aquest treball és estudiar el grafó, l'objecte límit per a seqüències de grafs densos convergents sota dues nocions equivalents de convergència, definides, respectivament, a partir de la distància de tall i de les densitats d’homomorfismes. Abordarem els resultats més rellevants que involucren els límits de grafs, teoria desenvolupada fonamentalment per Lovász i Szegedy, així com algunes aplicacions. Crucialment, veurem que l’espai mètric de grafons és compacte i que completa el conjunt de grafs, un fet amb profundes conseqüències en molts problemes extremals de grafs. En particular, examinarem el problema de minimitzar i maximitzar el nombre d’alguns subgrafs, com ara triangles o cicles de llargada 4, a grafs amb una densitat d’arestes donada. El nostre estudi dels límits de grafs anirà precedit per una necessària discussió sobre algunes nocions preliminars de teoria de grafs; concretament, grafs aleatoris i pseudoaleatoris i els lemes de regularitat i de comptatge., El objetivo principal de este trabajo es estudiar el grafón, el objeto límite para secuencias de grafos densos convergentes bajo dos nociones de convergencia, definidas, respectivamente, a partir de la distancia de corte y de las densidades de homomorfismos. Abordaremos los resultados más relevantes que involucran a los límites de grafos, teoría desarrollada fundamentalmente por Lovász y Szegedy, así como algunas aplicaciones. Crucialmente, veremos que el espacio métrico de grafones es compacto y que completa el conjunto de grafos, un hecho con profundas consecuencias en muchos problemas extremales de grafos. En particular, examinaremos el problema de minimizar y maximizar el número de algunos subgrafos, como triángulos o ciclos de longitud 4, en grafos con una densidad de aristas fijada. Nuestro estudio de los límites de grafos irá precedido por una necesaria discusión sobre algunas nociones preliminares de teoría de grafos; concretamente, grafos aleatorios y pseudoaleatorios y los lemas de regularidad y de conteo., The main objective of this thesis is to study the graphon, the limit object for convergent dense graph sequences under two equivalent notions of convergence, defined, respectively, from the cut metric and homomorphism densities. We will explore the principal results involving graph limits, a theory primarily developed by Lovász and Szegedy, as well as some of their applications. Fundamentally, we will see that the graphon metric space is compact and that it is the completion of the set of graphs, a statement with deep consequences in many graph extremal problems. In particular, we will examine the problem of minimizing and maximizing the number of some subgraphs like triangles or 4-cycles in graphs with a given edge density. Our study of graph limits will be preceded by a necessary discussion on some preliminar notions from graph theory, namely random and quasirandom graphs and the regularity and counting lemmas.

The version of record of this article, first published inBoletín de la Sociedad Matemática Mexicana, is available online at Publisher’s website: http://dx.doi.org/10.1007/s40590-023-00583-3, Let G be a graph on n vertices. The k-token graph (or symmetric k-th power) of G, denoted by , has as vertices the k-subsets of vertices from G, and two vertices are adjacent when their symmetric difference is a pair of adjacent vertices in G. In particular, is the Johnson graph J(n, k), which is a distance-regular graph used in coding theory. In this paper, we present some results concerning the (adjacency and Laplacian) spectrum of in terms of the spectrum of G. For instance, when G is walk-regular, an exact value for the spectral radius (or maximum eigenvalue) of is obtained. When G is distance-regular, other eigenvalues of its 2-token graph are derived using the theory of equitable partitions. A generalization of Aldous’ spectral gap conjecture (which is now a theorem) is proposed., The research of C. Dalfó and M. A. Fiol has been partially supported by AGAUR from the Catalan Government under Project 2017SGR1087 and by MICINN from the Spanish Government under Project PGC2018-095471-B-I00. The research of M. A. Fiol was also supported by a grant from the Universitat Politècnica de Catalunya with references AGRUPS-2022 and AGRUPS-2023., Peer Reviewed, Postprint (published version)

© 2024 Elsevier. This manuscript version is made available under the CC-BY-NC-ND 4.0 license http://creativecommons.org/licenses/by-nc-nd/4.0, A set D of vertices of a graph G is isolating if the set of vertices not in D and with no neighbor in D is independent. The isolation number of G, denoted by , is the minimum cardinality of an isolating set of G. It is known that , if G is a connected graph of order n, , distinct from . The main result of this work is the characterisation of unicyclic and block graphs of order n with isolating number equal to . Moreover, we provide a family of general graphs attaining this upper bound on the isolation number., Award-winning, Postprint (author's final draft)

In this paper, we study the order of the largest connected component of a random graph having two sources of randomness: first, the graph is chosen randomly from all graphs with a given degree sequence, and then bond percolation is applied. Far from being able to classify all such degree sequences, we exhibit several new threshold phenomena for the order of the largest component in terms of both sources of randomness. We also provide an example of a degree sequence for which the order of the largest component undergoes an unbounded number of jumps in terms of the percolation parameter, giving rise to a behavior that cannot be observed without percolation., Peer Reviewed, Postprint (author's final draft)

Self-supervised learning is gaining considerable attention as a solution to avoid the requirement of extensive annotations in representation learning on graphs. Current algorithms are based on contrastive learning, which is computation an memory expensive, and the assumption of invariance under certain graph augmentations. However, graph transformations such as edge sampling may modify the semantics of the data so that the invariance assumption may be incorrect. We introduce Regularized Graph Infomax (RGI), a simple yet effective framework for node level self-supervised learning that trains a graph neural network encoder by maximizing the mutual information between output node embeddings and their propagation through the graph, which encode the nodes’ local and global context, respectively. RGI do not use graph data augmentations but instead generates self-supervision signals with feature propagation, is non-contrastive and does not depend on a two branch architecture. We run RGI on both transductive and inductive settings with popular graph benchmarks and show that it can achieve state-of-the-art performance regardless of its simplicity., This work has been supported by the Spanish Research Agency (AEI) under project PID2020-116907RB-I00 of the call MCIN/AEI/ 10.13039/501100011033 and the FI-AGAUR 2021-FI-B-00845 grant funded by Secretaria d’Universitats i Recerca de la Generalitat de Catalunya and the European Social Fund (ESF)., Peer Reviewed, Postprint (published version)

Este Trabajo Final de Grado explora la determinación de la dimensión métrica de varios grafos para los que ciertos investigadores han proporcionado cotas o no han investigado a fondo. La dimensión métrica de un grafo es un concepto bien conocido en teoría de grafos, representando el número mínimo de vértices necesarios para identificar de manera única todos los demás vértices en el grafo usando distancias. Este estudio tiene como objetivo ampliar el conocimiento actual y potencialmente descubrir cotas más estrictas para la dimensión métrica. Para lograr esto, utilizaremos "solvers", que son herramientas computacionales poderosas para resolver problemas NP-Completos. A través de un análisis exhaustivo de diferentes grafos y sus métricas asociadas, esta investigación contribuye a la comprensión de la dimensión métrica y proporciona valiosos conocimientos para futuras investigaciones en teoría de grafos., This undergraduate thesis explores the determination of the metric dimension of various graphs for which certain researchers have provided bounds or have not thoroughly investigated. The metric dimension of a graph is a well-known concept in graph theory, representing the smallest number of vertices required to uniquely identify all other vertices in the graph using distances. This study aims to extend the current knowledge and potentially discover tighter bounds for the metric dimension. To achieve this, we will make use of solvers, which are powerful computational tools for solving NP-Complete problems. Through a comprehensive analysis of different graphs and their associated metrics, this research contributes to the understanding of the metric dimension and provides valuable insights for future investigations in graph theory.

F. Klute was supported by the Netherlands Organisation for Scientific Research (NWO) project no. 612.001.651 and the Austrian Science Foundation (FWF) grant J4510. I. Parada was supported by the Margarita Salas Fellowship 2021UPC‐MS‐67392 funded by the Ministry of Universities of Spain and the European Union (NextGenerationEU). F. Klute and I. Parada were supported by grant PID2019104129GB‐I00 funded by MICIU/AEI/10.13039/501100011033., Peer Reviewed, Postprint (published version)

El problema dels quatre colors va ser el problema central en teoria de grafs per més de cent anys. La conjectura d’Hadwiger va sorgir com un intent de generalitzar el problema. En canvi, va donar lloc a un dels problemes més complicats de teoria de grafs que, actualment, encara resta per resoldre. Malgrat els esforços de molts investigadors, només un nombre petit de casos s’han resolt, i la conjectura continuarà present per molts més anys. El nostre treball estableix una base teòrica per entendre la conjectura i dona una perspectiva general dels últims resultats obtinguts. Específicament, hem dut a terme una anàlisi detallada de l’últim avenç, fet per Delcourt i Postle, en la fita del nombre cromàtic per a grafs sense menors de Kt, destacant les idees clau darrere la seva demostració. El treball també s’enfoca en grafs amb nombre d’estabilitat igual a 2, un cas complex de la conjectura. Es presenten els resultats més importants en la literatura, com també alguns grafs que hem estudiat per la seva complexitat. Finalment, es presenten els nostres descobriments relacionats amb la conjectura d’Hadwiger per als grafs triats., El problema de los cuatro colores fue el problema central en teoría de grafos por más de cien años. La conjetura de Hadwiger surgió como un intento de generalizar el problema. En cambio, dio lugar a uno de los problemas más complicados de teoría de grafos que, a día de hoy, aún está sin resolver. A pesar de los esfuerzos de muchos investigadores, solo un nombre pequeño de casos se han resuelto, y la conjetura seguirá presente por muchos años más. Nuestro trabajo establece una base teórica para entender la conjetura y da una perspectiva general de los últimos resultados obtenidos. Específicamente, hemos llevado a cabo un análisis detallado del último avance, hecho por Delcourt y Postle, en la cota del número cromático para grafos sin menores de Kt, destacando las ideas clave detrás de la demostración. El trabajo también se enfoca en grafos con número de estabilidad igual a 2, un caso complejo de la conjetura. Se presentan los resultados más importantes de la literatura, así como algunos grafos que hemos estudiado debido a su complejidad. Finalmente, se presentan nuestros descubrimientos relacionados con la conjetura de Hadwiger para los grafos escogidos., The four colour problem was the central open problem in graph theory for over a hundred years. Hadwiger's conjecture originated as an attempt to generalise this problem. Instead, it gave rise to one of the most complicated problems in graph theory that, up to this date, remains unsolved. Despite the efforts of many researchers, only a few cases have been proved, and the conjecture will be around for many more years. Our work provides the theoretical foundation to understand the conjecture and an overview of its state of the art. Specifically, we present a deep analysis of the latest breakthrough done by Delcourt and Postle on the bound of the chromatic number of Kt-minor-free graphs, highlighting the key ideas behind their proof. The thesis also focuses on graphs with independence number 2, a challenging case of the conjecture. We present the most important results in the literature and some graphs we consider worth studying due to their complexity. We then present our original work, demonstrating some results related to Hadwiger's conjecture for the chosen graphs., Outgoing

Graph Neural Networks (GNNs) have achieved great success in solving many machine learning tasks, and many different neural architectures have been proposed over the past few years. However, the lack of robust public benchmarks hinders the assessment of GNN architectures, which has made most research papers rely on the same 5-10 datasets. Our first contribution is Graphlaxy++, a novel generative graph learning model designed to emulate GNN performance and that can be used to generate artificial benchmarks with user-defined metrics. Leveraging Graphlaxy++, we generate a diverse synthetic graph dataset that serves as input to a predictive statistical model that can predict the performance of GNNs. This model is able to successfully predict the relative performance of 4 different architectures: GCN, GAT, GIN, and MLP. The predictive capacity of this model offers potential applications in speeding up neural architecture searches and optimizing graph modeling strategies.

Les Xarxes Neuronals sobre Feixos (SNNs) estenen de forma natural les Xarxes Neuronals sobre Grafs (GNNs) otorgant un feix cel·lular sobre el graf, equipant els seus nodes i arestes amb espais vectorials i definint aplicacions lineals entre aquests. Tot i que s'ha demostrat que l'estructura geomètrica afegida al graf és útil per analitzar l'heterofília i el sobre allisament, fins ara els mètodes pels quals s'ha inferit el feix no sempre garanteixen un bon rendiment en aquestes circumstàncies. Aquest projecte agafa inspiració de conceptes de dinàmica d'opinions per proposar nous mètodes per aprendre el feix per tal que sigui més intuitiu entendre'l i tractin el sobre allisament i l'heterofília de forma més explícita. Aquests es centren en explorar modificacions del Laplacià per grafs amb conjunts de punts d'equilibri més diversos. Amb aquest propòsit, en primer lloc tenim una explicació exhaustiva de tots els conceptes matemàtics que hi ha darrere els feixos i el sobre allisament. Després repassem algunes de les GNNs més populars, incloent-hi les SNNs, i cobrim els conceptes de sobre allisament i heterofília en el context de les GNNs. Llavors, ens endinsem a la teoria de dinàmica d'opinions per extreure'n processos útils per dades heterofíliques. Un cop tota la base teòrica ha estat coberta, proposem dos nous models, JdSNN i RiSNN, per ser utilitzats en dades heterofíliques on les GNNs tinguin problemes de sobre allisament. Per comparar aquests models amb les SNNs originals en un problema controlat proposem una nova forma de generar dades sintètiques per evaluar xarxes neuronals basades en feixos. Fent servir aquestes dades, evaluem els nostres models i les SNNs per treure conclusions significatives sobre el seu comportament. Després, evaluem els nostres models en dades referents que s'havien fet servir prèviament, noves dades referents, un problema de detecció de notícies falses i algunes dades referents d'hipergrafs., Las Redes Neuronales sobre Fajos (SNNs) extienden de forma natural las Redes Neuronales sobre Grafos (GNNs) otorgando un fajo celular sobre el grafo, equipando sus nodos y aristas con espacios vectoriales y definiendo aplicaciones lineales entre estos. Aunque se ha demostrado que la estructura geométrica añadida al grafo es útil para analizar la heterofilia y el sobre alisamiento, hasta ahora los métodos por los cuales el fajo se ha calculado no siempre garantizan un buen rendimiento en estas circumstancias. Este proyecto coge inspiración de conceptos de dinámica de opiniones para proponer nuevos métodos para aprender el fajo para que sea más intuitivo entenderlo y traten el sobre alisamiento y la heterofilia de forma más explícita. Estos se focalizan en explorar modificaciones del Laplaciano para grafos con conjuntos de puntos de equilibrio más ricos. Con este propósito, en primer lugar tenemos una explicación exhaustiva de todos los conceptos matemáticos que hay destrás de los fajos y el sobre alisamiento. Después repasamos algunas de las GNNs más populares, incluyendo las SNNs, y cubrimos los conceptos de sobre alisamiento y heterofília en el contexto de las GNNs. Entonces entramos en la teoria de dinámica de opiniones para extraer procesos útiles para datos heterofílicos. Con toda la base teórica cubierta, proponemos dos nuevos modelos, JdSNN y RiSNN, para ser usados en datos heterofílicos donde las GNNs tengan problemas de sobre alisamiento. Para comparar estos modelos con las SNNs originales en un problema controlado proponemos una nueva forma de generar datos sintéticos para evaluar redes neuronales basades en fajos. Usando estos datos, evaluamos nuestros modelos y las SNNs para extraer conclusiones significativas sobre su comportamiento. Después, evaluamos nuestros modelos en datos referentes que se habían usado previamente, nuevos datos referentes, un problema de detección de notícias falsas y algunos datos referentes de hipergrafos., Sheaf Neural Networks (SNNs) naturally extend Graph Neural Networks (GNNs) by endowing a cellular sheaf over the graph, equipping nodes and edges with vector spaces and defining linear mappings between them. While the attached geometric structure has proven to be useful in analyzing heterophily and oversmoothing, so far the methods by which the sheaf is computed do not always guarantee a good performance in such settings. This work draws inspiration from opinion dynamics concepts to propose novel sheaf learning methods to provide a more intuitive understanding of the sheaf and address oversmoothing and heterophily more explicitly than previous works. These focus on exploring modifications of the graph Laplacian with richer sets of equilibrium points. For this purpose, an exhaustive explanation of the mathematical concepts behind sheaves and oversmoothing is done. Then we go over some of the most popular GNN models, including SNNs, and cover the concepts of oversmoothing and heterophily in the context of GNNs. After this, we dive into the concepts of opinion dynamics theory that are useful for heterophilic data. With all the background done, two new models, JdSNN and RiSNN, are proposed to be used on heterophilic data where oversmoothing might be a problem. To test these models against regular SNNs in a controlled environment we propose a new framework to generate synthetic data to test sheaf-based graph neural networks. Using said framework we test our models against regular SNNs and draw meaningful conclusions from said results. Then these new models are tested on previously used benchmarks, new benchmarks, a fake news detection dataset and some hypergraph datasets. Finally, there's a methodology and planning section which explains how this thesis was developed as well as a sustainability report., Outgoing

The model of approximate computing can be used to increase performance or optimize resource usage in stream and graph processing. It can be used to satisfy performance requirements (e.g., throughput, lag) in stream processing by reducing the effort that applications need to process datasets. There are currently multiple stream processing platforms, and most of them do not natively support approximate results. A recent one, Stateful Functions, is an API that uses Flink to enable developers to easily build stream and graph processing applications. It also retains Flink's features like stateful computations, fault-tolerance, scalability, control events and its graph processing library Gelly. Herein we present Approxate, an extension over this platform to support approximate results. It can also support more efficient stream and graph processing by allocating available resources adaptively, driven by user-defined requirements on throughput, lag, and latency. This extension enables flexibility in computational trade-offs such as trading accuracy for performance. The user can choose which metrics should be guaranteed at the cost of others, and/or the accuracy. Approxate incorporates approximate computing (using load shedding) with adaptive accuracy and resource manegement in state-of-the-art stream processing platforms, which are not targeted in other relevant related work. It does not require significant modifications to application code, and minimizes imbalance in data source representation when dropping events., This work was supported by national funds through FCT, Fundação para a Ciência e a Tecnologia, under project UIDB/50021/2020. DL 60/2018, de 3-08 – Aquisição necessária para a atividade de I&D do INESC-ID, no âmbito do projeto SmartRetail (02/C-05i01/2022). This work was partially supported by the Spanish Government under research contracts PID2019-106774RB-C21 and PCI2019-111850-2 (DiPET CHIST-ERA)., Peer Reviewed, Postprint (author's final draft)

The main goal of this paper is to determine the asymptotic behavior of the number X n of cut-vertices in random planar maps with n edges. It is shown that X n / n ¿ c in probability (for some explicit c > 0 ). For so-called subcritical classes of planar maps (like outerplanar maps) we obtain a central limit theorem, too. Interestingly the combinatorics behind this seemingly simple problem is quite involved., Peer Reviewed, Postprint (published version)

A set D of vertices of a graph is isolating if the set of vertices not belonging to D or not having a neighbour in D is independent. The isolation number of a graph G, denoted by ¿(G), is the minimum cardinality of an isolating set. It is known that ¿(G) = n/3 if G is a connected graph of order n, n = 3, different from a cycle of order 5. Moreover, trees attaining this upper bound have been characterized. In this work we characterize all unicyclic and block graphs of order n such that ¿(G) = n/3., Partially supported by projects PID2020-113230RB-C21 and PID2019-104129GBI00/MCIN/AEI/10.13039/501100011033 of the Spanish Ministry of Science and Innovation, and Gen.Cat. DGR2021-SGR-00266., Peer Reviewed, Postprint (author's final draft)

A k-coloring of a graph G is a partition of the vertices of G into k independent sets, which are called colors. A k-coloring is neighbor-locating if any two vertices belonging to the same color can be distinguished from each other by the colors of their respective neighbors. The neighbor-locating chromatic number ¿NL (G) is the minimum cardinality of a neighbor-locating coloring of G. In this paper, we determine the neighbor-locating chromatic number of paths, cycles, fans and wheels. Moreover, a procedure to construct a neighbor-locating coloring of minimum cardinality for these families of graphs is given. We also obtain tight upper bounds on the order of trees and unicyclic graphs in terms of the neighbor-locating chromatic number. Further partial results for trees are also established., Peer Reviewed, Postprint (published version)

We propose a stochastic epidemiological model for simplicial complex networks by means of a stochastic differential equation (SDE) that extends the mean field approach of the simplicial social contagion model. We show that, under appropriate conditions, if the stochastic basic reproductive number is smaller than one, then the disease dies out with probability one; otherwise the solution of the SDE oscillates infinitely often around a point which can be explicitly computed. We perform numerical experiments which illustrate the theoretical results. In addition, we carry out simulations on a real simplicial network and on a synthetic network, which show good agreement with the theoretical and numerical predictions of the SDE., D.H.S. is supported by Ministerio de Economía y Competitividad (Spain) under grant MTM2017-86042-P, the project STAMGAD 18.J445/463AC03 by Consejería de Educación (GIR, Junta de Castilla y León, Spain) and by Universidad de Salamanca (Spain) under project PIC2-2021-10. J.H.S. is supported by the Spanish Ministry of Science and Education under the project TCO-RISEBLOCK (PID2019-110224RB-I00), the European Union’s H2020 Research and Innovation Programme under the Grant Agreement No. 871754 (i3-MARKET), and the Generalitat de Catalunya, Spain grant 2017-SGR-00782. JV was supported by MINEICO (Spain), Agencia Estatal de Investigación (AEI), Spain and European Regional Development Fund, under grant number PID 2019-106811GB-C33., Postprint (published version)

We study the size of the largest component of two models of random graphs with prescribed degree sequence, the configuration model (CM) and the uniform model (UM), in the (barely) subcritical regime. For the CM, we give upper bounds that are asymptotically tight for certain degree sequences. These bounds hold under mild conditions on the sequence and improve previous results of Hatami and Molloy on the barely subcritical regime. For the UM, we give weaker upper bounds that are tight up to logarithmic terms but require no assumptions on the degree sequence. In particular, the latter result applies to degree sequences with infinite variance in the subcritical regime., M.C. was supported by the FPI grant PRE2018-083621 associated to the project MTM2017-82166-P from the Spanish Ministerio de Economía y Competitividad. G.P was supported by the Spanish Agencia Estatal de Investigación under projects MTM2017-82166-P and PID2020-113082GB-I00, and by the Severo Ochoa and María de Maeztu Program for Centers and Units of Excellence in R&D (CEX2020-001084-M)., Postprint (author's final draft)

The main result of this paper is the introduction of marked graphs and the marked graph polynomials ( -polynomial) associated with them. These polynomials can be defined via a deletion-contraction operation. These polynomials are a generalization of the -polynomial, introduced by Noble and Welsh, and a specialization of the -polynomial, introduced by Ellis-Monaghan and Moffatt. In addition, we describe an important specialization of the -polynomial, which we call the -polynomial. Furthermore, we present an efficient algorithm for computing the chromatic symmetric function of a graph in the star basis of symmetric functions. As an application of these tools, we prove that proper trees of diameter at most 5 are reconstructible from its chromatic symmetric function., JAP was partially supported by FONDECYT REGULAR 1160975 CONICYT Chile. AdM was partially supported by PID2020-113082GB-I00 funded by MCIN/AEI. RO was partially supported by NSF grant DMS–300512. JZ was partially supported by FONDECYT REGULAR 1180994 CONICYT Chile., Peer Reviewed, Postprint (published version)

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.

The development of the project has been contextualized in LEO satellite constellations and the possibilities they offer as a communications network, with particular focus on ground-to-air communications (aircraft). The initial objective of this thesis has been the research of the A* shortest path routing algorithm, trying to find heuristic models that generate competitive performance versus the optimal path routing provided by the Dijkstra algorithm. At the same time, a graphical environment has been developed in order to show the algorithm's behaviour. Secondly, another algorithm (Yen) to provide alternatives to the shortest path without necessarily considering disjoint paths has been searched and developed. To conclude, a jump into spatiotemporal domain perspective has been made, developing a methodology to establish routings that are able to provide real-time voice signals, while the delay steps through time are minimised, offering a reliable communications system. The results offer a new research framework, analysing the feasibility of the offered solutions., El desarrollo del proyecto se ha contextualizado en las redes satelitales LEO y las posibilidades que ofrecen como red de comunicaciones, con un enfoque particular en las comunicaciones tierra-aire (aviación). El objetivo inicial de esta tesis ha sido investigar el algoritmo de búsqueda de caminos A*, tratando de hallar modelos heurísticos que generen un rendimiento competitivo frente al algoritmo óptimo (Dijkstra). Al mismo tiempo, se ha desarrollado una interfaz gráfica para mostrar el funcionamiento del algoritmo. Seguidamente, se ha desarrollado otro algoritmo (Yen) para tener otra opción a considerar caminos disjuntos al óptimo como alternativa. Como conclusión, se ha hecho un salto al dominio espacio-temporal, desplegando una metodología para establecer rutas capaces de ofrecer señal de voz en tiempo real, mientras se minimizan transiciones abruptas de retardo, ofreciendo un sistema de comunicaciones fiable. Los resultados ofrecen un nuevo marco de investigación, analizando la factibilidad de las soluciones ofrecidas., El desenvolupament del projecte s'ha contextualitzat a les xarxes de satèl·lits LEO i les possibilitats que ofereixen com a xarxa de comunicacions, amb un enfocament particular en les comunicacions terra-aire (aviació). L'objectiu inicial d'aquesta tesi ha sigut el d'investigar l'algoritme de cerca de camins A*, tractant de trobar models heurístics que generin un rendiment competitiu vers l'algoritme òptim (Dijkstra). Al mateix temps, s'ha desenvolupat una interfície gràfica per mostrar el funcionament de l'algoritme. Seguidament, s'ha desenvolupat un altre algoritme (Yen) per tindre un altra opció a considerar camins disjunts a l'òptim com a alternativa. Com a conclusió, s'ha fet un salt al domini espacial-temporal, desplegant una metodologia per establir rutes capaces d'oferir senyal de veu en temps real, alhora que minimitzant transicions abruptes de retard, oferint un sistema de comunicacions fiable. Els resultats ofereixen un nou camp d'investigació, analitzant la factibilitat de les solucions oferides.

Utilitzar filtre en grafs per a predir la topologia d'un graf., This project will focus on the development of methods to predict relations (links) between elements (nodes) of a network structured in a graph. In order to study these systems, the graphs will be understood as a signal domain. Therefore, the aim of the project becomes to design a signal processing method to predict missing or future links of a graph, Este proyecto se centra en el desarrollo de métodos para predecir las relaciones (enlaces) entre elementos (nodos) de una red estructurada en un grafo. Para estudiar estos sistemas, los grafos se entenderán como un dominio de señales. Por lo tanto, el objetivo del proyecto se convierte a diseñar un método de procesamiento de señales para predeci enlaces futuros o desconocidos de un grafo, Aquest projecte se centra en el desenvolupament de mètodes per predir les relacions (enllaços) entre elements (nodes) d'una xarxa estructurada en un graf. Per tal d'estudiar aquests sistemes, els grafs s'entendran com un domini de senyals. Per tant, l'objectiu del projecte es converteix en dissenyar un mètode de processament de senyals per predir enllaços futurs o desconeguts d'un graf

Nowadays, businesses are faced with an overwhelming amount of data. Companies are using data-driven solutions to improve decision making and stay competitive, especially in the supply chain industry where data management and analysis can improve operations and reduce costs. Accenture is no exception. As the amount of data increases, some internal libraries have become the bottleneck for large size client projects. In this work, we aim to improve the performance of the Network library used for generating graphs from supply chain data. Research is conducted on two popular graph tools (NetworkX and Neo4j) to find a suitable alternative. Results show that NetworkX offers a good balance between execution time and memory usage while Neo4j has fast query performance but high memory usage.

En aquest treball abordem els problemes de mostreig i comptatge aproximat en models d'espins en grafs, recopilant els resultats més significatius de l'àrea i introduïnt els coneixements previs necessaris del camp de la física estadística. En particular, prestem especial atenció als mètodes generals de disseny d'algorismes desenvolupats per Weitz i Barvinok, així com els avenços recents en matèria de comptatge i mostreig de conjunts independents de mida donada. Així mateix, discutim com es podrien adaptar aquests arguments als problemes de comptatge i mostreig de coloracions amb les mides de cada color fixades, explicant amb detall la línia de recerca actual que estem duent a terme., En este trabajo abordamos los problemas de muestreo y conteo aproximado en modelos de espines en grafos, recopilando los resultados más significativos del campo e introduciendo el conocimiento previo necesario del área de la física estadística. En particular, prestamos especial atención a los métodos generales de diseño de algorismos desarrollados por Weitz y Barvinok, así como a los avances recientes en cuanto al conteo y muestreo de conjuntos independientes de un tamaño dado. Así mismo, discutimos cómo se podrían adaptar estos argumentos al problema de contar y muestrear coloraciones con el tamaño de cada color fijo, explicando en detalle la línea de investigación que estamos llevando a cabo actualmente., We approach the problems of approximate sampling and counting in spin models on graphs, surveying the most significant results in the area and introducing the necessary background from statistical physics. We pay particular attention to the general algorithm design frameworks developed by Weitz and Barvinok, as well as to the newer results on counting and sampling independent sets of given size. In addition, we discuss the adaptation of the arguments behind these results to count and sample colorings with fixed color sizes, explaining in detail the current research line we are undertaking., Outgoing

© 2023 Elsevier. This manuscript version is made available under the CC-BY-NC-ND 4.0 license http://creativecommons.org/licenses/by-nc-nd/4.0, For , the -independence number of a graph is the maximum number of vertices that are mutually at distance greater than . The well-known inertia and ratio bounds for the (1-)independence number of a graph, due to Cvetković and Hoffman, respectively, were generalized recently for every value of . We show that, for graphs with enough regularity, the polynomials involved in such generalizations are closely related and give exact values for , showing a new relationship between the inertia and ratio type bounds. Additionally, we investigate the existence and properties of the extremal case of sets of vertices that are mutually at maximum distance for walk-regular graphs. Finally, we obtain new sharp inertia and ratio type bounds for partially walk-regular graphs by using the predistance polynomials., The research of Aida Abiad is partially supported by the FWO, Belgium grant 1285921N. The research of Cristina Dalfó and Miquel Àngel Fiol has been partially supported by AGAUR from the Catalan Government under project 2021SGR00434 and MICINN from the Spanish Government under project PID2020-115442RB-I00., Peer Reviewed, Postprint (published version)

A Moore (r, z, k)-mixed graph G has every vertex with undirected degree r, directed in- and outdegree z, diameter k, and number of vertices (or order) attaining the corresponding Moore bound M(r, z, k) for mixed graphs. When the order of G is close to M(r, z, k) vertices, we refer to it as an almost Moore graph. The first part of this paper is a survey about known Moore (and almost Moore) general mixed graphs that turn out to be Cayley graphs. Then, in the second part of the paper, we give new results on the bipartite case. First, we show that Moore bipartite mixed graphs with diameter three are distance-regular, and their spectra are fully characterized. In particular, an infinity family of Moore bipartite (1, z, 3)-mixed graphs is presented, which are Cayley graphs of semidirect products of groups. Our study is based on the line digraph technique, and on some results about when the line digraph of a Cayley digraph is again a Cayley digraph., This research has been partially supported by AGAUR from the Catalan Government under project 2021SGR00434 and MICINN from the Spanish Government under project PID2020-115442RBI00., Peer Reviewed, Postprint (published version)

We determine the number of labelled chordal planar graphs with n vertices, which is asymptotically for a constant and . We also determine the number of rooted simple chordal planar maps with n edges, which is asymptotically , where , , and s is an algebraic number of degree 12. The proofs are based on combinatorial decompositions and singularity analysis. Chordal planar graphs (or maps) are a natural example of a subcritical class of graphs in which the class of 3-connected graphs is relatively rich. The 3-connected members are precisely chordal triangulations, those obtained starting from by repeatedly adding vertices adjacent to an existing triangular face., We gratefully acknowledge earlier discussions on this project with Erkan Narmanli. M.N. was supported by grants MTM2017-82166-P and PID2020-113082GB-I00, the Severo Ochoa and María de Maeztu Program for Centers and Units of Excellence in R&D (CEX2020-001084-M). C.R. was supported by the grant Beatriu de Pinós BP2019, funded by the H2020 COFUND project No 801370 and AGAUR (the Catalan agency for management of university and research grants), and the grant PID2020-113082GB-I00 of the Spanish Ministry of Science and Innovation., Peer Reviewed, Postprint (author's final draft)

The code (and data) in this article has been certified as Reproducible by Code Ocean: (https://codeocean.com/). More information on the Reproducibility Badge Initiative is available at https://www.elsevier.com/physical-sciences-andengineering/computer-science/journals, Network Alignment (NA) is a hard optimization problem with important applications such as, for example, the identification of orthologous relationships between different proteins and of phylogenetic relationships between species. Given two (or more) networks, the goal is to find an alignment between them, that is, a mapping between their respective nodes such that the topological and functional structure is well preserved. Although the problem has received great interest in recent years, there is still a need to unify the different trends that have emerged from diverse research areas. In this paper, we introduce AntNetAlign, an Ant Colony Optimization (ACO) approach for solving the problem. The proposed approach makes use of similarity information extracted from the input networks to guide the construction process. Combined with an improvement measure that depends on the current construction state, it is able to optimize any of the three main topological quality measures. We provide an extensive experimental evaluation using real-world instances that range from Protein–Protein Interaction (PPI) networks to Social Networks. Results show that our method outperforms other state-of-the-art approaches in two out of three of the tested scores within a reasonable amount of time, specially in the important score. Moreover, it is able to obtain near-optimal results when aligning networks with themselves. Furthermore, in larger instances, our algorithm was still able to compete with the best performing method in this regard., Christian Blum and Guillem Rodríguez Corominas, Spain were supported by grants PID2019-104156GB-I00 and TED2021- 129319B-I00 funded by MCIN/AEI/10.13039/501100011033. Maria J. Blesa acknowledges support from AEI, Spain under grant PID2020-112581GB-C21 (MOTION) and the Catalan Agency for Management of University and Research Grants (AGAUR), Spain under grant 2017-SGR-786 (ALBCOM)., Peer Reviewed, Postprint (published version)

This is the peer reviewed version of the following article: Fàbrega, J.; Martí, J.; Muñoz, X. Distance-layer structure of the De Bruijn and Kautz digraphs: analysis and application to deflection routing. "Networks", 29 Juliol 2023, which has been published in final form at https://onlinelibrary.wiley.com/doi/10.1002/net.22177. This article may be used for non-commercial purposes in accordance with Wiley Terms and Conditions for Use of Self-Archived Versions. This article may not be enhanced, enriched or otherwise transformed into a derivative work, without express permission from Wiley or by statutory rights under applicable legislation. Copyright notices must not be removed, obscured or modified. The article must be linked to Wiley’s version of record on Wiley Online Library and any embedding, framing or otherwise making available the article or pages thereof by third parties from platforms, services and websites other than Wiley Online Library must be prohibited., In this article, we present a detailed study of the reach distance-layer structure of the De Bruijn and Kautz digraphs, and we apply our analysis to the performance evaluation of deflection routing in De Bruijn and Kautz networks. Concerning the distance-layer structure, we provide explicit polynomial expressions, in terms of the degree of the digraph, for the cardinalities of some relevant sets of this structure. Regarding the application to defection routing, and as a consequence of our polynomial description of the distance-layer structure, we formulate explicit expressions, in terms of the degree of the digraph, for some probabilities of interest in the analysis of this type of routing. De Bruijn and Kautz digraphs are fundamental examples of digraphs on alphabet and iterated line digraphs. If the topology of the network under consideration corresponds to a digraph of this type, we can perform, in principle, a similar vertex layer description., Partially supported by the Ministerio de Ciencia e Innovación/Agencia Estatal de Investigación, Spain, and the European Regional Development Fund under project PGC2018-095471-B-I00; and by AGAUR from the Catalan Government under project 2017SGR-1087., Peer Reviewed, Postprint (author's final draft)

© 2023 Elsevier. This manuscript version is made available under the CC-BY-NC-ND 4.0 license http://creativecommons.org/licenses/by-nc-nd/4.0, Many dissemination processes in graphs can be described as follows at a basic level. At each step of the process, some vertices of the graph are coloured blue, and the remaining are coloured white, and a well-defined infection rule acts locally on a chosen element of the graph. As an outcome of this action, perhaps one or more white vertices are forced to become blue. Zero forcing, power domination and bootstrap percolation are some examples of widely studied infection rules. This paper presents a general view of infection rules on graphs, paying particular attention to monotone rules. We state several results referring to the final stable set of blue vertices at the end of the dissemination process driven by the infection rule , and to the combinatorial transversal relation between the families of inclusion-minimal -forcing and -immune sets of the graph. Our results apply to many infection rules considered in the literature, as well as to new ones introduced in this paper. Besides, for each one of these infection rules, we provide a characterization of their -immune sets formulated in terms of neighbourhood, so without referring to the iterative dissemination process acting on the graph. In the second part of the paper, and for the particular rules treated in the first part ( -PUSH, -PUSH, -PUSH, -PULL, -PULL, and -wPULL), we prove the -Completeness of the decision problem associated to the corresponding -immune number of the graph., Partially supported by the Ministerio de Ciencia e Innovaci´on/Agencia Estatal de Investigaci´on, Spain, and the European Regional Development Fund under project PGC2018- 095471-B-I00; and by AGAUR from the Catalan Government under project 2017SGR–1087., Peer Reviewed, Postprint (published version)

Aquesta tesi explora la relació entre triangulacions combinatòries i geomètriques en geometria discreta i combinatòria. Per triangulacions combinatòries ens referim a grafs, mentre que per triangulacions geomètriques ens referim a dibuixos de grafs com a plans maximals amb línies rectes com a arestes sobre un conjunt de punts fixat al pla. Estudiem de quantes maneres es pot traçar una triangulació combinatòria com a triangulació geomètrica sobre un conjunt de punts donat. La nostra contribució central és demostrar que una triangulació combinatòria fixa amb n vèrtexs es pot dibuixar d'almenys 1,31^n maneres en un conjunt de n punts com a diferents triangulacions geomètriques. També analitzem els límits superiors i una versió acolorida daquest problema. L'enfocament suggerit pot ajudar a avançar en la resolució del problema obert per limitar el nombre de triangulacions geomètriques. A més, aprofundim en fonaments històrics, com el treball de Tutte, que proporciona el nombre exacte de triangulacions combinatòries amb n vèrtexs., Esta tesis explora la relación entre triangulaciones combinatorias y geométricas en geometría discreta y combinatoria. Con triangulaciones combinatorias nos referimos a grafos, mientras que con triangulaciones geométricas nos referimos a dibujos de grafos como planos maximales con líneas rectas como aristas sobre un conjunto de puntos fijado en el plano. Estudiamos de cuántas maneras se puede trazar una triangulación combinatoria como triangulación geométrica sobre un conjunto de puntos dado. Nuestra contribución central es demostrar que una triangulación combinatoria fija con n vértices se puede dibujar de al menos 1,31^n maneras en un conjunto de n puntos como diferentes triangulaciones geométricas. También analizamos los límites superiores y una versión coloreada de este problema. El enfoque sugerido puede ayudar a avanzar en la resolución del problema abierto para limitar el número de triangulaciones geométricas. Además, profundizamos en fundamentos históricos, como el trabajo de Tutte, que proporciona el número exacto de triangulaciones combinatorias con n vértices., This thesis explores the intricate relationship between combinatorial and geometric triangulations in discrete and combinatorial geometry. With combinatorial triangulations we refer to graphs, while with geometric triangulations we refer to maximal planar straight-line drawings on a point set in the plane. We study in how many ways can a combinatorial triangulation be drawn as geometric triangulation on a given point set. Our central contribution is proving that a fixed combinatorial triangulation with n vertices can be drawn in at least 1.31^n ways in a set of n points as different geometric triangulations. We also discuss upper bounds and a colored version of this problem. The suggested approach may help to advance the resolution of the open problem to bound the number of geometric triangulations. Additionally, we delve into historical foundations, such as Tutte's work, which provides the exact number of combinatorial triangulations with n vertices.

© 2023 Elsevier. This manuscript version is made available under the CC-BY-NC-ND 4.0 license http://creativecommons.org/licenses/by-nc-nd/4.0, The k-token graph of a graph G is the graph whose vertices are the k-subsets of vertices from G, two of which being adjacent whenever their symmetric difference is a pair of adjacent vertices in G. It is a known result that the algebraic connectivity (or second Laplacian eigenvalue) of equals the algebraic connectivity of G. In this paper, we first give results that relate the algebraic connectivities of a token graph and the same graph after removing a vertex. Then, we prove the result on the algebraic connectivity of 2-token graphs for two infinite families: the odd graphs for all r, and the multipartite complete graphs for all In the case of cycles, we present a new method that allows us to compute the whole spectrum of . This method also allows us to obtain closed formulas that give asymptotically exact approximations for most of the eigenvalues of ., Peer Reviewed, Postprint (author's final draft)

The total angular resolution of a straight-line drawing is the minimum angle between two edges of the drawing. It combines two properties contributing to the readability of a drawing: the angular resolution, which is the minimum angle between incident edges, and the crossing resolution, which is the minimum angle between crossing edges. We consider the total angular resolution of a graph, which is the maximum total angular resolution of a straight-line drawing of this graph. We prove tight bounds for the number of edges for graphs for some values of the total angular resolution up to a finite number of well specified exceptions of constant size. In addition, we show that deciding whether a graph has total angular resolution at least is NP-hard. Further we present some special graphs and their total angular resolution., Peer Reviewed, Postprint (published version)

We show that the diameter of the directed configuration model with n vertices rescaled by log n converges in probability to a constant. Our assumptions are the convergence of the in- and out-degree of a uniform random vertex in distribution, first and second moment. Our result extends previous results on the diameter of the model and applies to many other random directed graphs. Nous montrons que le diamètre du modèle de configuration dirigé avec n sommets renormalisé par log n converge en probabilité vers une constante. Nos hypothèses sont la convergence en loi des degrés entrant et sortant d’un sommet uniformément choisi, et celles en moments d’ordre 1 et d’ordre 2. Notre résultat étend les résultats précédents sur le diamètre du modèle et s’applique à de nombreux autres graphes orientés aléatoires., This work is supported by the Agencia Estatal de Investigación (MCIN/AEI) through the a Proyecto I+D+i 2020 (PID2020-113082GB-I00), through the Marie Skłodowska-Curie Research and Innovation Staff Exchange grant RandNet (MSCA-RISE-2020-101007705) and through the Severo Ochoa and María de Maeztu Program for Centers and Units of Excellence in R&D (CEX2020-001084-M)., Peer Reviewed, Postprint (author's final draft)

Es presenta una exploració de les Transformades en Grafs amb l'objectiu de millorar els algorismes de codificació en un còdec de video actual, AV2. Definim una versió paramètrica de transformada, basada en Grafs Lineals, i trobem una expressió per als paràmetres òptims en base a un model teòric de la senyal. A banda, explorem el concepte de transformades irregulars, que generalitzen la formulació i ens permeten regular la importància de cada pixel individualment. Finalment, presentem una implementació eficient de les Transformades en Grafs al software de referència d'AV2, aconseguint un guany de compressió d'un 0.16%., Se presenta una exploración de las Transformadas en Grafos con el objetivo de mejorar los algoritmos de codificación en un códec de video actual, AV2. Definimos una versión paramétrica de transformada, basada en Grafos Lineales, y encontramos una expresión para los parámetros óptimos en base a un modelo teórico de la señal. Aparte, exploramos el concepto de transformadas irregulares, que generalizan la formulación y nos permiten regular la importancia de cada pixel individualmente. Por último, presentamos una implementación eficiente de las Transformadas en Grafos en el software de referencia de AV2, consiguiendo una ganancia de compresión de un 0.16%., We present an exploration of Graph Transforms to improve the Transform Coding algorithms in a modern video codec, AV2. We define a parametrized transform based on a Line Graph, and find the best parameter values according to a theoretical model of the signal. Then, we explore the concept of irregular transforms, which generalize the framework and allow to tune the importance of each pixel individually. Finally, we present an implementation of the Graph Transforms in the AV2 reference software, which achieves a 0.16% compression efficiency gain., Outgoing

We propose a graph neural network (GNN)-based method to predict the distribution of penalties induced by outages in communication networks, where connections are protected by resources shared between working and backup paths. The GNN-based algorithm is trained only with random graphs generated on the basis of the Barabási–Albert model. However, the results obtained show that we can accurately model the penalties in a wide range of existing topologies. We show that GNNs eliminate the need to simulate complex outage scenarios for the network topologies under study—in practice, the entire time of path placement evaluation based on the prediction is no longer than 4 ms on modern hardware. In this way, we gain up to 12 000 times in speed improvement compared to calculations based on simulations., This work was supported by the Polish Ministry of Science and Higher Education with the subvention funds of the Faculty of Computer Science, Electronics and Telecommunications of AGH University of Science and Technology (P.B., P.C.) and by the PL-Grid Infrastructure (K.R.)., Peer Reviewed, Postprint (published version)

La coloració de grafs dibuixats a superfícies és un àrea antiga i molt estudiada de la teoria de grafs. Thomassen va demostrar que hi ha un nombre finit de grafs 6-crítics a qualsevol superfície fixa i va proporcionar el conjunt explícit dels grafs 6-crítics al torus. Després, Postle va demostrar que hi ha un nombre finit de grafs 6-llista-crítics a qualsevol superfície fixa. Amb l'objectiu de trobar el conjunt de grafs 6-llista-crítics al torus, desenvolupem i implementem tècniques algorítmiques per la cerca per ordinador de grafs crítics en diferents situacions de coloració per llistes., La coloración de grafos dibujados en superficies es un área antigua y muy estudiada de la teoría de grafos. Thomassen demostró que hay un número finito de grafos 6-críticos en cualquier superficie fija y proporcionó el conjunto explícito de los grafos 6-críticos en el toro. Después, Postle demostró que hay un número finito de grafos 6-lista-críticos en cualquier superficie fija. Con el objetivo de encontrar el conjunto de grafos 6-lista-críticos en el toro, desarrollamos e implementamos técnicas algorítmicas para la búsqueda por ordenador de grafos críticos en diferentes situaciones de coloración por listas., Coloring graphs embedded on surfaces is an old and well-studied area of graph theory. Thomassen proved that there are finitely many 6-critical graphs on any fixed surface and provided the explicit set of 6-critical graphs on the torus. Later, Postle proved that there are finitely many 6-list-critical graphs on any fixed surface. With the goal of finding the set of 6-list-critical graphs on the torus, we develop and implement algorithmic techniques for computer search of critical graphs in different list-coloring settings., Outgoing

We analyse uniform random cubic rooted planar maps and obtain limiting distributions for several parameters of interest. From the enumerative point of view, we present a unified approach for the enumeration of several classes of cubic planar maps, which allow us to recover known results in a more general and transparent way. This approach allows us to obtain new enumerative results. Concerning random maps, we first obtain the distribution of the degree of the root face, which has an exponential tail as for other classes of random maps. Our main result is a limiting map-Airy distribution law for the size of the largest block L, whose expectation is asymptotically n/v3 in a random cubic map with n+ 2 faces. We prove analogous results for the size of the largest cubic block, obtained from L by erasing all vertices of degree two, and for the size of the largest 3-connected component, whose expected values are respectively n/2 and n/4. To obtain these results we need to analyse a new type of composition scheme which has not been treated by Banderier et al. [Random Structures Algorithms 2001]., Peer Reviewed, Postprint (author's final draft)

© 2023 IEEE. Personal use of this material is permitted. Permission from IEEE must be obtained for all other uses, in any current or future media, including reprinting/republishing this material for advertising or promotional purposes,creating new collective works, for resale or redistribution to servers or lists, or reuse of any copyrighted component of this work in other works., Knowledge of the Laplacian eigenvalues of a network provides important insights into its structural features and dynamical behaviours. Node or link removal caused by possible outage events, such as mechanical and electrical failures or malicious attacks, significantly impacts the Laplacian spectra. This can also happen due to intentional node removal against which, increasing the algebraic connectivity is desired. In this article, an analytical metric is proposed to measure the effect of node removal on the Laplacian eigenvalues of the network. The metric is formulated based on the local multiplicity of each eigenvalue at each node, so that the effect of node removal on any particular eigenvalues can be approximated using only one single eigen-decomposition of the Laplacian matrix. The metric is applicable to undirected networks as well as strongly-connected directed ones. It also provides a reliable approximation for the “Laplacian energy” of a network. The performance of the metric is evaluated for several synthetic networks and also the American Western States power grid. Results show that this metric has a nearly perfect precision in correctly predicting the most central nodes, and significantly outperforms other comparable heuristic methods., This research was partly supported by the Erasmus+ KA107 grant. AMA, MJ, LS and XY were supported by the Australian Research Council through project No. DP170102303. MJ and XY are also supported by the Australian Research Council through project No. DP200101199. MAF was supported by AGAUR from the Catalan Government under project 2017SGR1087, and by MICINN from the Spanish Government with the European Regional Development Fund under project PGC2018-095471-B-I00, Peer Reviewed, Postprint (author's final draft)

En este trabajo estudiamos la dimensión métrica y la dimensión métrica tolerante en grafos periplanos maximales. Concretamente, damos cotas ajustadas de ambos parámetros y caracterizamos los grafos que alcanzan las cotas inferiores., Postprint (author's final draft)

We study the complexity of computing the Banzhaf index in incompatibility games. We show: 1) weak #P-completeness for computing the index when the incompatibility graph has very few maximal independent sets, 2) strong #P-completeness if the incompatibility graph is co-planar and perfect, 3) weak NP-completeness for deciding whether the index is non-zero when the incompatibility graph has few maximal independent sets. Finally, we discuss the possible existence of pseudopolynomial time algorithms to compute the index for some classes of incompatibility graphs.

The analysis of colonic contents is a valuable tool for the gastroenterologist and has multiple applications in clinical routine. When considering magnetic resonance imaging (MRI) modalities, T2 weighted images are capable of segmenting the colonic lumen, whereas fecal and gas contents can only be distinguished in T1 weighted images. In this paper, we present an end-to-end quasi-automatic framework that comprises all the steps needed to accurately segment the colon in T2 and T1 images and to extract colonic content and morphology data to provide the quantification of colonic content and morphology data. As a consequence, physicians have gained new insights into the effects of diets and the mechanisms of abdominal distension, Peer Reviewed, Postprint (published version)

The version of record is available online at: http://dx.doi.org/10.1007/s40840-023-01582-3, The metric representation of a vertex u in a connected graph G respect to an ordered vertex subset is the vector of distances . A vertex subset W is a resolving set of G if , for every with . Thus, a resolving set with n elements provides a set of metric representation vectors with cardinal equal to the order of the graph. In this paper, we address the reverse point of view; that is, we characterize the finite subsets that are realizable as the set of metric representation vectors of a graph G with respect to some resolving set W. We also explore the role that the strong product of paths plays in this context. Moreover, in the case , we characterize the sets that are uniquely realizable as the set of metric representation vectors of a graph G with respect to a resolving set W., This work was partially supported by the grants of the Spanish Ministry of Science and Innovation PID2021-123278OB-I00 and PID2019-104129GB-I00, both funded by MCIN/AEI/10.13039/501100011033 and by “ERDF A way of making Europe”, and Gen. Cat. DGR 2021-SGR-00266., Peer Reviewed, Postprint (author's final draft)

We consider the extremal values of the stationary distribution of sparse directed random graphs with given degree sequences and their relation to the extremal values of the in-degree sequence. The graphs are generated by the directed configuration model. Under the assumption of bounded ( 2 + ¿ ) -moments on the in-degrees and of bounded out-degrees, we obtain tight comparisons between the maximum value of the stationary distribution and the maximum in-degree. Under the further assumption that the order statistics of the in-degrees have a power-law behavior, we show that the extremal values of the stationary distribution also have a power-law behavior with the same index. In the same setting, we prove that these results extend to the PageRank scores of the random digraph, thus confirming a version of the so-called power-law hypothesis. Along the way we establish several facts about the model, including the mixing time cutoff and the characterization of the typical values of the stationary distribution, which were previously obtained under the assumption of bounded in-degrees., The third author was supported by the Spanish Agencia Estatal de Investigación under projects MTM2017-82166-P and PID2020-113082GB-I00 and by the Severo Ochoa and María de Maeztu Program for Centers and Units of Excellence in R&D (CEX2020-001084-M)., Postprint (author's final draft)

The version of record of this article, first published in Journal of Combinatorial Optimization, is available online at Publisher’s website: http://dx.doi.org/10.1007/s10878-023-01010-z, Given n > 0, let S ¿ [0,1]2 be a set of n points, chosen uniformly at random. Let R¿B be a random partition, or coloring, of S in which each point of S is included in R uniformly at random with probability 1/2. We study the random variable M(n) equal to the number of points of S that are covered by the rectangles of a maximum strong matching of S with axis-aligned rectangles. The matching consists of closed axis-aligned rectangles that cover exactly two points of S of the same color, and is strong in the sense that all of its rectangles are pairwise disjoint. We prove that almost surely M(n) = 0.83n for n large enough. Our approach is based on modeling a deterministic greedy matching algorithm that runs over the random point set as a Markov chain., Author Corujo was supported by grants from the Université Paris-Dauphine (France) and the ITI IRMIA++. Author Flores-Peñaloza was supported by project PAPIIT IN120520 (UNAM, Mexico). Author Huemer was supported by projects PID2019-104129GB-I00/ MCIN/ AEI/ 10.13039/501100011033 and Gen. Cat. DGR 2021-SGR-00266. Author Pérez-Lantero was supported by projects CONICYT FONDECYT/Regular 1160543 (Chile), DICYT 041933PL Vicerrectoría de Investigación, Desarrollo e Innovación USACH (Chile), and Programa Regional STICAMSUD 19-STIC-02. Author Seara was supported by project PID2019-104129GB-I00/ MCIN/ AEI/ 10.13039/ 501100011033 and Gen. Cat. DGR 2021-SGR-00266., Postprint (author's final draft)

Hom vol introduir-se dins de l’àmbit de la inferència causal i dels grafs acíclics dirigits a fi de millorar l’anàlisi estadística i causal en estudis observacionals, la seva especificació i reproductibilitat. Hom tria dos problemes per tal d’aplicar-hi el corpus teòric après dels estudiosos en inferència causal Anne Brumback i Judea Pearl: el primer problema és una revisió crítica d’un article clínic sobre la pervivència de pacients de càncer i símptomes de COVID i el segon és un problema d’enginyeria astronàutica, l’estudi de l’accident del Challenger.

We propose a stochastic model that describes of epidemics over simplicial complex networks (SSCM) in which higher-order unforeseen or random interactions may occur. Its dynamics obeys a stochastic differential equation (SDE) based on the mean field approach of the simplicial social contagion model. In this stochastic regime the only possible equilibrium state is the origin. We give conditions to guarantee global stability and hence that the disease dies out. We partition the parameter space into the instability, the bi-stability and the globally asymptotically stable regions described in terms of appropriate epidemiological parameters. These regimes codify whether the disease will, can or will not disappear. We also present empirical results obtained by running different simulations of the SSCM over several real-world simplicial networks and over a synthetically generated one, which validate the theoretical results presented., D.H.S. is supported by Grant PID2021-128665NB-I00 funded by MCIN/AEI/ 10.13039/501100011033 and, as appropriate, by \ERDF A way of making Eu- rope", Ministerio de Econom a y Competitividad (Spain) under grant MTM2017- 86042-P, the project STAMGAD 18.J445 / 463AC03 by Consejer a de Edu- caci on (GIR, Junta de Castilla y Le on, Spain) and by Universidad de Sala- manca (Spain) under project PIC2-2021-10. J.H.S. is supported by the Span- ish Ministry of Science and Education under the project TCO-RISEBLOCK (PID2019-110224RB-I00), the European Union's H2020 Research and Innova- tion Programme under the Grant Agreement No. 871754 (i3-MARKET), and the Generalitat de Catalunya grant 2017-SGR-00782., Postprint (author's final draft)