On axiomatizations of the Shapley value for assignment games

We consider the problem of axiomatizing the Shapley value on the class of assignment games. We first show that several axiomatizations of the Shapley value on the class of all TU-games do not characterize this solution on the class of assignment games by providing alternative solutions that satisfy these axioms. However, when considering an assignment game as a communication graph game where the game is simply the assignment game and the graph is a corresponding bipartite graph buyers are connected with sellers only, we show that Myerson's component efficiency and fairness axioms do characterize the Shapley value on the class of assignment games. Moreover, these two axioms have a natural interpretation for assignment games. Component efficiency yields submarket efficiency stating that the sum of the payoffs of all players in a submarket equals the worth of that submarket, where a submarket is a set of buyers and sellers such that all buyers in this set have zero valuation for the goods offered by the sellers outside the set, and all buyers outside the set have zero valuations for the goods offered by sellers inside the set. Fairness of the graph game solution boils down to valuation fairness stating that only changing the valuation of one particular buyer for the good offered by a particular seller changes the payoffs of this buyer and seller by the same amount.

Learning Treewidth-Bounded Bayesian Networks with Thousands of Variables

We present a method for learning treewidth-bounded Bayesian networks from data sets containing thousands of variables. Bounding the treewidth of a Bayesian network greatly reduces the complexity of inferences. Yet, being a global property of the graph, it considerably increases the difficulty of the learning process. Our novel algorithm accomplishes this task, scaling both to large domains and to large treewidths. Our novel approach consistently outperforms the state of the art on experiments with up to thousands of variables.

On the extension complexity of combinatorial polytopes

In this paper we extend recent results of Fiorini et al. on the extension complexity of the cut polytope and related polyhedra. We first describe a lifting argument to show exponential extension complexity for a number of NP-complete problems including subset-sum and three dimensional matching. We then obtain a relationship between the extension complexity of the cut polytope of a graph and that of its graph minors. Using this we are able to show exponential extension complexity for the cut polytope of a large number of graphs, including those used in quantum information and suspensions of cubic planar graphs.

Hybrid Graph Heuristics within a Hyper-heuristic Approach to Exam Timetabling Problems

This paper is concerned with the hybridization of two graph coloring heuristics (Saturation Degree and Largest Degree), and their application within a hyperheuristic for exam timetabling problems. Hyper-heuristics can be seen as algorithms which intelligently select appropriate algorithms/heuristics for solving a problem. We developed a Tabu Search based hyper-heuristic to search for heuristic lists (of graph heuristics) for solving problems and investigated the heuristic lists found by employing knowledge discovery techniques. Two hybrid approaches (involving Saturation Degree and Largest Degree) including one which employs Case Based Reasoning are presented and discussed. Both the Tabu Search based hyper-heuristic and the hybrid approaches are tested on random and real-world exam timetabling problems. Experimental results are comparable with the best state-of-the-art approaches (as measured against established benchmark problems). The results also demonstrate an increased level of generality in our approach.

Top-K Query Processing in Edge-Labeled Graph Data

Edge-labeled graphs have proliferated rapidly over the last decade due to the increased popularity of social networks and the Semantic Web. In social networks, relationships between people are represented by edges and each edge is labeled with a semantic annotation. Hence, a huge single graph can express many different relationships between entities. The Semantic Web represents each single fragment of knowledge as a triple (subject, predicate, object), which is conceptually identical to an edge from subject to object labeled with predicates. A set of triples constitutes an edge-labeled graph on which knowledge inference is performed. Subgraph matching has been extensively used as a query language for patterns in the context of edge-labeled graphs. For example, in social networks, users can specify a subgraph matching query to find all people that have certain neighborhood relationships. Heavily used fragments of the SPARQL query language for the Semantic Web and graph queries of other graph DBMS can also be viewed as subgraph matching over large graphs. Though subgraph matching has been extensively studied as a query paradigm in the Semantic Web and in social networks, a user can get a large number of answers in response to a query. These answers can be shown to the user in accordance with an importance ranking. In this thesis proposal, we present four different scoring models along with scalable algorithms to find the top-k answers via a suite of intelligent pruning techniques. The suggested models consist of a practically important subset of the SPARQL query language augmented with some additional useful features. The first model called Substitution Importance Query (SIQ) identifies the top-k answers whose scores are calculated from matched vertices' properties in each answer in accordance with a user-specified notion of importance. The second model called Vertex Importance Query (VIQ) identifies important vertices in accordance with a user-defined scoring method that builds on top of various subgraphs articulated by the user. Approximate Importance Query (AIQ), our third model, allows partial and inexact matchings and returns top-k of them with a user-specified approximation terms and scoring functions. In the fourth model called Probabilistic Importance Query (PIQ), a query consists of several sub-blocks: one mandatory block that must be mapped and other blocks that can be opportunistically mapped. The probability is calculated from various aspects of answers such as the number of mapped blocks, vertices' properties in each block and so on and the most top-k probable answers are returned. An important distinguishing feature of our work is that we allow the user a huge amount of freedom in specifying: (i) what pattern and approximation he considers important, (ii) how to score answers - irrespective of whether they are vertices or substitution, and (iii) how to combine and aggregate scores generated by multiple patterns and/or multiple substitutions. Because so much power is given to the user, indexing is more challenging than in situations where additional restrictions are imposed on the queries the user can ask. The proposed algorithms for the first model can also be used for answering SPARQL queries with ORDER BY and LIMIT, and the method for the second model also works for SPARQL queries with GROUP BY, ORDER BY and LIMIT. We test our algorithms on multiple real-world graph databases, showing that our algorithms are far more efficient than popular triple stores.

Efficient domination through eigenvalues

The paper begins with a new characterization of (k,τ)(k,τ)-regular sets. Then, using this result as well as the theory of star complements, we derive a simplex-like algorithm for determining whether or not a graph contains a (0,τ)(0,τ)-regular set. When τ=1τ=1, this algorithm can be applied to solve the efficient dominating set problem which is known to be NP-complete. If −1−1 is not an eigenvalue of the adjacency matrix of the graph, this particular algorithm runs in polynomial time. However, although it does not work in polynomial time in general, we report on its successful application to a vast set of randomly generated graphs.

A lower bound for the energy of symmetric matrices and graphs

The energy of a symmetric matrix is the sum of the absolute values of its eigenvalues. We introduce a lower bound for the energy of a symmetric partitioned matrix into blocks. This bound is related to the spectrum of its quotient matrix. Furthermore, we study necessary conditions for the equality. Applications to the energy of the generalized composition of a family of arbitrary graphs are obtained. A lower bound for the energy of a graph with a bridge is given. Some computational experiments are presented in order to show that, in some cases, the obtained lower bound is incomparable with the well known lower bound $2\sqrt{m}$, where $m$ is the number of edges of the graph.

A SURVEY OF DISTANCE MAGIC GRAPHS

In this report, we survey results on distance magic graphs and some closely related graphs. A distance magic labeling of a graph G with magic constant k is a bijection l from the vertex set to {1, 2, . . . , n}, such that for every vertex x Σ l(y) = k,y∈NG(x) where NG(x) is the set of vertices of G adjacent to x. If the graph G has a distance magic labeling we say that G is a distance magic graph. In Chapter 1, we explore the background of distance magic graphs by introducing examples of magic squares, magic graphs, and distance magic graphs. In Chapter 2, we begin by examining some basic results on distance magic graphs. We next look at results on different graph structures including regular graphs, multipartite graphs, graph products, join graphs, and splitting graphs. We conclude with other perspectives on distance magic graphs including embedding theorems, the matrix representation of distance magic graphs, lifted magic rectangles, and distance magic constants. In Chapter 3, we study graph labelings that retain the same labels as distance magic labelings, but alter the definition in some other way. These labelings include balanced distance magic labelings, closed distance magic labelings, D-distance magic labelings, and distance antimagic labelings. In Chapter 4, we examine results on neighborhood magic labelings, group distance magic labelings, and group distance antimagic labelings. These graph labelings change the label set, but are otherwise similar to distance magic graphs. In Chapter 5, we examine some applications of distance magic and distance antimagic labeling to the fair scheduling of tournaments. In Chapter 6, we conclude with some open problems.

Production Diseases in European Organic Dairy Farms – Current Status and Identification of Drivers for Improvement by Means of a Systemic Approach

The aims of this thesis were to determine the animal health status in organic dairy farms in Europe and to identify drivers for improving the current situation by means of a systemic approach. Prevalences of production diseases were determined in 192 herds in Germany, France, Spain, and Sweden (Paper I), and stakeholder consultations were performed to investigate potential drivers to improve animal health on the sector level (ibid.). Interactions between farm variables were assessed through impact analysis and evaluated to identify general system behaviour and classify components according to their outgoing and incoming impacts (Paper II-III). The mean values and variances of prevalences indicate that the common rules of organic dairy farming in Europe do not result in consistently low levels of production diseases. Stakeholders deemed it necessary to improve the current status and were generally in favour of establishing thresholds for the prevalence of production diseases in organic dairy herds as well as taking actions to improve farms below that threshold. In order to close the gap between the organic principle of health and the organic farming practice, there is the need to formulate a common objective of good animal health and to install instruments to ensure and prove that the aim is followed by all dairy farmers in Europe who sell their products under the organic label. Regular monitoring and evaluation of herd health performance based on reference values are considered preconditions for identifying farms not reaching the target and thus in need of improvement. Graph-based impact analysis was shown to be a suitable method for modeling and evaluating the manifold interactions between farm factors and for identifying the most influential components on the farm level taking into account direct and indirect impacts as well as impact strengths. Variables likely to affect the system as a whole, and the prevalence of production diseases in particular, varied largely between farms despite some general tendencies. This finding reflects the diversity of farm systems and underlines the importance of applying systemic approaches in health management. Reducing the complexity of farm systems and indicating farm-specific drivers, i.e. areas in a farm, where changes will have a large impact, the presented approach has the potential to complement and enrich current advisory practice and to support farmers’ decision-making in terms of animal health.

Semiclassical analysis of systems of Schrödinger equations

The scalar Schrödinger equation models the probability density distribution for a particle to be found in a point x given a certain potential V(x) forming a well with respect to a fixed energy level E_0. Formally two real inversion points a,b exist such that V(a)=V(b)=E_0, V(x)<0 in (a,b) and V(x)>0 for xb. Following the work made by D.Yafaev and performing a WKB approximation we obtain solutions defined on specific intervals. The aim of the first part of the thesis is to find a condition on E, which belongs to a neighbourhood of E_0, such that it is an eigenvalue of the Schrödinger operator, obtaining in this way global and linear dependent solutions in L2. In quantum mechanics this condition is known as Bohr-Sommerfeld quantization. In the second part we define a Schrödinger operator referred to two potential wells and we study the quantization conditions on E in order to have a global solution in L2xL2 with respect to the mutual position of the potentials. In particular their wells can be disjoint,can have an intersection, can be included one into the other and can have a single point intersection. For these cases we refer to the works of A.Martinez, S. Fujiié, T. Watanabe, S. Ashida.

Learning representations for graph-structured socio-technical systems

The recent widespread use of social media platforms and web services has led to a vast amount of behavioral data that can be used to model socio-technical systems. A significant part of this data can be represented as graphs or networks, which have become the prevalent mathematical framework for studying the structure and the dynamics of complex interacting systems. However, analyzing and understanding these data presents new challenges due to their increasing complexity and diversity. For instance, the characterization of real-world networks includes the need of accounting for their temporal dimension, together with incorporating higher-order interactions beyond the traditional pairwise formalism. The ongoing growth of AI has led to the integration of traditional graph mining techniques with representation learning and low-dimensional embeddings of networks to address current challenges. These methods capture the underlying similarities and geometry of graph-shaped data, generating latent representations that enable the resolution of various tasks, such as link prediction, node classification, and graph clustering. As these techniques gain popularity, there is even a growing concern about their responsible use. In particular, there has been an increased emphasis on addressing the limitations of interpretability in graph representation learning. This thesis contributes to the advancement of knowledge in the field of graph representation learning and has potential applications in a wide range of complex systems domains. We initially focus on forecasting problems related to face-to-face contact networks with time-varying graph embeddings. Then, we study hyperedge prediction and reconstruction with simplicial complex embeddings. Finally, we analyze the problem of interpreting latent dimensions in node embeddings for graphs. The proposed models are extensively evaluated in multiple experimental settings and the results demonstrate their effectiveness and reliability, achieving state-of-the-art performances and providing valuable insights into the properties of the learned representations.

A study of brain functional connectivity and cognitive processes in long COVID-19 patients

In this work, a prospective study conducted at the IRCCS Istituto delle Scienze Neurologiche di Bologna is presented. The aim was to investigate the brain functional connectivity of a cohort of patients (N=23) suffering from persistent olfactory dysfunction after SARS-CoV-2 infection (Post-COVID-19 syndrome), as compared to a matching group of healthy controls (N=26). In particular, starting from individual resting state functional-MRI data, different analytical approaches were adopted in order to find potential alterations in the connectivity patterns of patients’ brains. Analyses were conducted both at a whole-brain level and with a special focus on brain regions involved in the processing of olfactory stimuli (Olfactory Network). Statistical correlations between functional connectivity alterations and the results of olfactory and neuropsychological tests were investigated, to explore the associations with cognitive processes. The three approaches implemented for the analysis were the seed-based correlation analysis, the group-level Independent Component analysis and a graph-theoretical analysis of brain connectivity. Due to the relative novelty of such approaches, many implementation details and methodologies are not standardized yet and represent active research fields. Seed-based and group-ICA analyses’ results showed no statistically significant differences between groups, while relevant alterations emerged from those of the graph-based analysis. In particular, patients’ olfactory sub-graph appeared to have a less pronounced modular structure compared to the control group; locally, a hyper-connectivity of the right thalamus was observed in patients, with significant involvement of the right insula and hippocampus. Results of an exploratory correlation analysis showed a positive correlation between the graphs global modularity and the scores obtained in olfactory tests and negative correlations between the thalamus hyper-connectivity and memory tests scores.

Directed Abelian algebras and their application to stochastic models

With each directed acyclic graph (this includes some D-dimensional lattices) one can associate some Abelian algebras that we call directed Abelian algebras (DAAs). On each site of the graph one attaches a generator of the algebra. These algebras depend on several parameters and are semisimple. Using any DAA, one can define a family of Hamiltonians which give the continuous time evolution of a stochastic process. The calculation of the spectra and ground-state wave functions (stationary state probability distributions) is an easy algebraic exercise. If one considers D-dimensional lattices and chooses Hamiltonians linear in the generators, in finite-size scaling the Hamiltonian spectrum is gapless with a critical dynamic exponent z=D. One possible application of the DAA is to sandpile models. In the paper we present this application, considering one- and two-dimensional lattices. In the one-dimensional case, when the DAA conserves the number of particles, the avalanches belong to the random walker universality class (critical exponent sigma(tau)=3/2). We study the local density of particles inside large avalanches, showing a depletion of particles at the source of the avalanche and an enrichment at its end. In two dimensions we did extensive Monte-Carlo simulations and found sigma(tau)=1.780 +/- 0.005.

Gibbs random graphs on point processes

Consider a discrete locally finite subset Gamma of R(d) and the cornplete graph (Gamma, E), with vertices Gamma and edges E. We consider Gibbs measures on the set of sub-graphs with vertices Gamma and edges E` subset of E. The Gibbs interaction acts between open edges having a vertex in common. We study percolation properties of the Gibbs distribution of the graph ensemble. The main results concern percolation properties of the open edges in two cases: (a) when Gamma is sampled from a homogeneous Poisson process; and (b) for a fixed Gamma with sufficiently sparse points. (c) 2010 American Institute of Physics. [doi:10.1063/1.3514605]

C4-saturated bipartite graphs

Let H be a graph. A graph G is said to be H-free if it contains no subgraph isomorphic to H. A graph G is said to be an H-saturated subgraph of a graph K if G is an H-free subgraph of K with the property that for any edge e is an element of E(K)\E(G), G boolean OR {e} is not H-free. We present some general results on K-s,K-t-saturated subgraphs of the complete bipartite graph K-m,K-n and study the problem of finding, for all possible values of q, a C-4-saturated subgraph of K., having precisely q edges. (C) 2002 Elsevier Science B.V. All rights reserved.