Search

This work deals with undirected graphs that have the same betweenness centrality for each vertex, so-called betweenness uniform graphs (or BUGs). The class of these graphs is not trivial and its classification is still an open problem. Recently, Gago, Coroni\v{c}ov\'a-Hurajov\'a and Madaras conjectured that for every rational $\alpha\ge 3/4$ there exists a BUG having betweenness centrality~$\alpha$. We disprove this conjecture, and provide an alternative view of the structure of betweenness-uniform graphs from the point of view of their complement. This allows us to characterise all the BUGs with betweennes centrality at most 9/10, and show that their betweenness centrality is equal to $\frac{\ell}{\ell+1}$ for some integer $\ell\le 9$. We conjecture that this characterization extends to all the BUGs with betweenness centrality smaller than~1.

The symmetry of complex networks is a global property that has recently gained attention since MacArthur et al. 2008 showed that many real-world networks contain a considerable number of symmetries. These authors work with a very strict symmetry definition based on the network's automorphism. The potential problem with this approach is that even a slight change in the graph's structure can remove or create some symmetry. Recently, Liu 2020 proposed to use an approximate automorphism instead of strict automorphism. This method can discover symmetries in the network while accepting some minor imperfections in their structure. The proposed numerical method, however, exhibits some performance problems and has some limitations while it assumes the absence of fixed points. In this work, we exploit alternative approaches recently developed for treating the Graph Matching Problem and propose a method, which we will refer to as Quadratic Symmetry Approximator (QSA), to address the aforementioned shortcomings. To test our method, we propose a set of random graph models suitable for assessing a wide family of approximate symmetry algorithms. The performance of our method is also demonstrated on brain networks.

Structural convergence is a framework for convergence of graphs by Ne\v{s}et\v{r}il and Ossona de Mendez that unifies the dense (left) graph convergence and Benjamini-Schramm convergence. They posed a problem asking whether for a given sequence of graphs $(G_n)$ converging to a limit $L$ and a vertex $r$ of $L$ it is possible to find a sequence of vertices $(r_n)$ such that $L$ rooted at $r$ is the limit of the graphs $G_n$ rooted at $r_n$. A counterexample was found by Christofides and Kr\'{a}l', but they showed that the statement holds for almost all vertices $r$ of $L$. We offer another perspective to the original problem by considering the size of definable sets to which the root $r$ belongs. We prove that if $r$ is an algebraic vertex (i.e. belongs to a finite definable set), the sequence of roots $(r_n)$ always exists.

We deal with linear programming problems involving absolute values in their formulations, so that they are no more expressible as standard linear programs. The presence of absolute values causes the problems to be nonconvex and nonsmooth, so hard to solve. In this paper, we study fundamental properties on the topology and the geometric shape of the solution set, and also conditions for convexity, connectedness, boundedness and integrality of the vertices. Further, we address various complexity issues, showing that many basic questions are NP-hard to solve. We show that the feasible set is a (nonconvex) polyhedral set and, more importantly, every nonconvex polyhedral set can be described by means of absolute value constraints. We also provide a necessary and sufficient condition when a KKT point of a nonconvex quadratic programming reformulation solves the original problem.

Ne\v{s}et\v{r}il and Ossona de Mendez recently proposed a new definition of graph convergence called structural convergence. The structural convergence framework is based on the probability of satisfaction of logical formulas from a fixed fragment of first-order formulas. The flexibility of choosing the fragment allows to unify the classical notions of convergence for sparse and dense graphs. Since the field is relatively young, the range of examples of convergent sequences is limited and only a few methods of construction are known. Our aim is to extend the variety of constructions by considering the gadget construction. We show that, when restricting to the set of sentences, the application of gadget construction on elementarily convergent sequences yields an elementarily convergent sequence. On the other hand, we show counterexamples witnessing that a generalization to the full first-order convergence is not possible without additional assumptions. We give several different sufficient conditions to ensure the full convergence. One of them states that the resulting sequence is first-order convergent if the replaced edges are dense in the original sequence of structures.

We consider the classical sensor scheduling problem for linear systems where only one sensor is activated at each time. We show that the sensor scheduling problem has a close relation to the sensor design problem and the solution of a sensor schedule problem can be extracted from an equivalent sensor design problem. We propose a convex relaxation to the sensor design problem and a reference covariance trajectory is obtained from solving the relaxed sensor design problem. Afterwards, a covariance tracking algorithm is designed to obtain an approximate solution to the sensor scheduling problem using the reference covariance trajectory obtained from the sensor design problem. While the sensor scheduling problem is NP-hard, the proposed framework circumvents this computational complexity by decomposing this problem into a convex sensor design problem and a covariance tracking problem. We provide theoretical justification and a sub-optimality bound for the proposed method using dynamic programming. The proposed method is validated over several experiments portraying the efficacy of the framework., Comment: To appear in Automatica

Betweenness centrality is a centrality measure based on the overall amount of shortest paths passing through a given vertex. A graph is betweenness-uniform if all its vertices have the same betweenness centrality. We study the properties of betweenness-uniform graphs. In particular, we show that every connected betweenness-uniform graph is either a cycle or a $3$-connected graph. Also, we show that betweenness uniform graphs of high maximal degree have small diameter., Comment: minor changes; to bepublished in Discrete Applied Mathematics

Betweenness centrality is a measure of the importance of a vertex x inside a network based on the fraction of shortest paths passing through x. We study a blow-up construction that has been shown to produce graphs with uniform distribution of betweenness. We disprove the conjecture about this procedure's universality by showing that trees with a diameter at least three cannot be transformed into betweenness-uniform by the blow-up construction. It remains open to characterize graphs for which the blow-up construction can produce betweenness-uniform graphs.

Incomplete cooperative games generalise the classical model of cooperative games by omitting the values of some of the coalitions. This allows to incorporate uncertainty into the model and study the underlying games as well as possible payoff distribution based only on the partial information. In this paper we perform a systematic study of incomplete games, focusing on two important classes of cooperative games: positive and convex games. Regarding positivity, we generalise previous results for a special class of minimal incomplete games to general setting. We characterise non-extendability to a positive game by the existence of a certificate and provide a description of the set of positive extensions using its extreme games. The results are then used to obtain explicit formulas for several classes of incomplete games with special structures. The second part deals with convexity. We begin with considering the case of non-negative minimal incomplete games. Then we survey existing results in the related theory of set functions, namely providing context to the problem of completing partial functions. We provide a characterisation of extendability and a full description of the set of symmetric convex extensions. The set serves as an approximation of the set of convex extensions. Finally, we outline an entirely new perspective on a connection between incomplete cooperative games and cooperative interval games.

We present an algorithm for computing a spectral decomposition of an interval matrix as an enclosure of spectral decompositions of particular realizations of interval matrices. The algorithm relies on tight outer estimations of eigenvalues and eigenvectors of corresponding interval matrices. We present a method for general interval matrices as well as its modification for symmetric interval matrices. As an illustration, we apply the spectral decomposition to computing powers of interval matrices. Numerical results suggest that a simple binary exponentiation is more efficient for smaller exponents, but our approach becomes better when computing higher powers or powers of a special type of matrices. In particular, we consider symmetric interval and circulant interval matrices. In both cases we utilize some properties of the corresponding classes of matrices to make the power computation more efficient.

We show that the independence number of a countably infinite HH-homogeneous graph that does not contain the Rado graph as a spanning subgraph is finite and present a classification of MB-homogeneous graphs up to bimorphism-equivalence as a consequence., Comment: 17 pages, 4 figures. To appear in the European Journal of Combinatorics

The radius of regularity sometimes spelled as the radius of nonsingularity is a measure providing the distance of a given matrix to the nearest singular one. Despite its possible application strength this measure is still far from being handled in an efficient way also due to findings of Poljak and Rohn providing proof that checking this property is NP-hard for a general matrix. To handle this we can either find approximation algorithms or making known bounds for radius of regularity tighter. Improvements of both have been recently shown by Hartman and Hladik (doi:10.1007/978-3-319-31769-4\_9) utilizing relaxation to semidefinite programming. These approaches consider general matrices without or with just mild assumptions about the original matrix. This work explores a process of regularity radius analysis and identifies useful properties enabling easier estimation of the corresponding radius values based on utilization of properties of special class of considered matrices. At first, checking finiteness of regularity radius is shown to be a polynomial problem along with determining a maximal bound on number of nonzero elements of the matrix to obtain infinite radius. Further, relationship between maximum (Chebyshev) norm and spectral norm is used to construct new bounds for the radius of regularity. A new method based on Jansson-Rohn algorithm for testing regularity of an interval matrix is presented which is not a priory exponential along with numerical experiments. For a situation where an input matrix has a special form, several results are provided such as exact formulas for several special classes of matrices, e.g., for totally positive and inverse non-negative, or approximation algorithms, e.g., rank-one radius matrices. For tridiagonal matrices, an algorithm by Bar-On, Codenotti and Leoncini is utilized to design a polynomial algorithm to compute the regularity radius.

In~\cite{Hartman:2014}, Hartman, Hubi\v cka and Ma\v sulovi\'c studied the hierarchy of morphism extension classes for finite $L$-colored graphs, that is, undirected graphs without loops where sets of colors selected from $L$ are assigned to vertices and edges. They proved that when $L$ is a linear order, the classes $MH_L$ and $HH_L$ coincide, and the same is true for vertex-uniform finite $L$-colored graphs when $L$ is a diamond. In this paper, we explore the same question for countably infinite $L$-colored graphs. We prove that $MH_L=HH_L$ if and only if $L$ is a linear order., Comment: 12 pages, 1 figure

Stock networks, constructed from stock price time series, are a well-established tool for the characterization of complex behavior in stock markets. Following Mantegna's seminal paper, the linear Pearson's correlation coefficient between pairs of stocks has been the usual way to determine network edges. Recently, possible effects of nonlinearity on the graph-theoretical properties of such networks have been demonstrated when using nonlinear measures such as mutual information instead of linear correlation. In this paper, we quantitatively characterize the nonlinearity in stock time series and the effect it has on stock network properties. This is achieved by a systematic multi-step approach that allows us to quantify the nonlinearity of coupling; correct its effects wherever it is caused by simple univariate non-Gaussianity; potentially localize in space and time any remaining strong sources of this nonlinearity; and, finally, study the effect nonlinearity has on global network properties. By applying this multi-step approach to stocks included in three prominent indices (NYSE100, FTSE100 and SP500), we establish that the apparent nonlinearity that has been observed is largely due to univariate non-Gaussianity. Furthermore, strong nonstationarity in a few specific stocks may play a role. In particular, the sharp decrease in some stocks during the global financial crisis of 2008 gives rise to apparent nonlinear dependencies among stocks.

The relational complexity, introduced by G. Cherlin, G. Martin, and D. Saracino, is a measure of ultrahomogeneity of a relational structure. It provides an information on minimal arity of additional invariant relations needed to turn given structure into an ultrahomogeneous one. The original motivation was group theory. This work focuses more on structures and provides an alternative approach. Our study is motivated by related concept of lift complexity studied by Hubicka and Nesetril., Comment: 18 pages, submitted to Mathematica Slovaca

Improving teacher quality in P-12 mathematics is a national need, and many universities and schools are working to address it. With the support of the National Science Foundation (NSF), twelve math and science institutes across the country are helping P-12 teachers strengthen their capacity to support students' learning. These NSF Institutes operate under the leadership of STEM university faculty, representing colleges of arts and science as well as colleges of education. The strategy is to build capacity by improving teachers' content knowledge, pedagogy, and leadership skills. One such venture is The Math in the Middle Institute Partnership (M2) at the University of Nebraska-Lincoln (UNL). As part of their efforts to understand the place of rural in M2, the research team systematically interviewed the 63 rural participants from the first three cohorts in summer 2006. During those 30-60 minute interviews they asked participants about the contexts in which they teach, their professional roles and responsibilities, and circumstances that influence their teaching. They soon found that teachers they called "rural" did not necessarily refer to themselves that way, and sometimes even teachers from the same town did not agree on whether or not to call themselves rural. (Contains 1 figure and 1 footnote.)

Quantification of relations between measured variables of interest by statistical measures of dependence is a common step in analysis of climate data. The term "connectivity" is used in the network context including the study of complex coupled dynamical systems. The choice of dependence measure is key for the results of the subsequent analysis and interpretation. The use of linear Pearson's correlation coefficient is widespread and convenient. On the other side, as the climate is widely acknowledged to be a nonlinear system, nonlinear connectivity quantification methods, such as those based on information-theoretical concepts, are increasingly used for this purpose. In this paper we outline an approach that enables well informed choice of connectivity method for a given type of data, improving the subsequent interpretation of the results. The presented multi-step approach includes statistical testing, quantification of the specific non-linear contribution to the interaction information, localization of nodes with strongest nonlinear contribution and assessment of the role of specific temporal patterns, including signal nonstationarities. In detail we study the consequences of the choice of a general nonlinear connectivity measure, namely mutual information, focusing on its relevance and potential alterations in the discovered dependence structure. We document the method by applying it on monthly mean temperature data from the NCEP/NCAR reanalysis dataset as well as the ERA dataset. We have been able to identify main sources of observed non-linearity in inter-node couplings. Detailed analysis suggested an important role of several sources of nonstationarity within the climate data. The quantitative role of genuine nonlinear coupling at this scale has proven to be almost negligible, providing quantitative support for the use of linear methods for this type of data.

Characterization of real-world complex systems increasingly involves the study of their topological structure using graph theory. Among global network properties, small-world property, consisting in existence of relatively short paths together with high clustering of the network, is one of the most discussed and studied. When dealing with coupled dynamical systems, links among units of the system are commonly quantified by a measure of pairwise statistical dependence of observed time series (functional connectivity). We argue that the functional connectivity approach leads to upwardly biased estimates of small-world characteristics (with respect to commonly used random graph models) due to partial transitivity of the accepted functional connectivity measures such as the correlation coefficient. In particular, this may lead to observation of small-world characteristics in connectivity graphs estimated from generic randomly connected dynamical systems. The ubiquity and robustness of the phenomenon is documented by an extensive parameter study of its manifestation in a multivariate linear autoregressive process, with discussion of the potential relevance for nonlinear processes and measures., Comment: The following article has been submitted to Chaos: An interdisciplinary journal of nonlinear science. After it is published, it will be found at http://chaos.aip.org/

A relational structure is homomorphism-homogeneous (HH-homogeneous for short) if every homomorphism between finite induced substructures of the structure can be extended to a homomorphism over the whole domain of the structure. Similarly, a structure is monomorphism-homogeneous (MH-homogeneous for short) if every monomorphism between finite induced substructures of the structure can be extended to a homomorphism over the whole domain of the structure. In this paper we consider L-colored graphs, that is, undirected graphs without loops where sets of colors selected from L are assigned to vertices and edges. A full classification of finite MH-homogeneous L-colored graphs where L is a chain is provided, and we show that the classes MH and HH coincide. When L is a diamond, that is, a set of pairwise incomparable elements enriched with a greatest and a least element, the situation turns out to be much more involved. We show that in the general case the classes MH and HH do not coincide., Comment: Submitted to European Journal of Combinatorics