We develop a theory to measure the variance and covariance of probability distributions defined on the nodes of a graph, which takes into account the distance between nodes. Our approach generalizes the usual (co)variance to the setting of weighted graphs and retains many of its intuitive and desired properties. As a particular application, we define the maximum-variance problem on graphs with respect to the effective resistance distance, and characterize the solutions to this problem both numerically and theoretically. We show how the maximum-variance distribution can be interpreted as a core-periphery measure, illustrated by the fact that these distributions are supported on the leaf nodes of tree graphs, low-degree nodes in a configuration-like graph and boundary nodes in random geometric graphs. Our theoretical results are supported by a number of experiments on a network of mathematical concepts, where we use the variance and covariance as analytical tools to study the (co-)occurrence of concepts in scientific papers with respect to the (network) relations between these concepts. Finally, I will draw connections to related notion of assortativity on networks, a network analogue of correlation used to describe how the presence and absence of edges covaries with the properties of nodes.

https://arxiv.org/abs/2008.09155

(joint work with T. Kania, Academy of Sciences of the Czech Republic, Prague)
In this talk we discuss our recent result on the inverse eigenvalue problem for symmetric doubly stochastic matrices. 
Namely, we provide a new sufficient condition for a list of real numbers to be the spectrum of a symmetric doubly stochastic matrix. 
In our construction of such matrices, we employ the eigenvectors of the transition probability matrix of a simple symmetric random walk on the circle. 
We also demonstrate a simple algorithm for generating random doubly stochastic matrices based on our construction. Examples will be provided.

In this new session a speaker tells us about how their area of mathematics can be used in different applications.

In this talk, Yuji Nakatsukasa tells us about how random matrix theory can be used in numerical linear algebra. 

Abstract

Randomized SVD is a topic in numerical linear algebra that draws heavily from random matrix theory. It has become an extremely successful approach for efficiently computing a low-rank approximation of matrices. In particular the paper by Halko, Martinsson, and Tropp (SIREV 2011) contains extensive analysis, and has made it a very popular method. The classical Nystrom method is much faster, but only applicable to positive semidefinite matrices. This work studies a generalization of Nystrom's method applicable to general matrices, and shows that (i) it has near-optimal approximation quality comparable to competing methods, (ii) the computational cost is the near-optimal O(mnlog n+r^3) for a rank-r approximation of dense mxn matrices, and (iii) crucially, it can be implemented in a numerically stable fashion despite the presence of an ill-conditioned pseudoinverse. Numerical experiments illustrate that generalized Nystrom can significantly outperform state-of-the-art methods. In this talk I will highlight the crucial role played by a classical result in random matrix theory, namely the Marchenko-Pastur law, and also briefly mention its other applications in least-squares problems and compressed sensing.

After a review of Batalin-Vilkovisky formalism and homotopy algebras, we discuss how these structures emerge in quantum field theory and gravity. We focus then on the application of these sophisticated mathematical tools to scattering amplitudes (both tree- and loop-level) and to the understanding of the dualities between gauge theories and gravity, highlighting generalizations of old results and presenting new ones.

In this talk, I will give a brief introduction to level-set methods for image analysis. I will then describe an application of level-sets to the construction of filtrations for persistent homology computations. I will present several case studies with various spatial data sets using this construction, including applications to voting, analyzing urban street patterns, and spiderwebs. I will conclude by discussing the types of data which I might imagine such methods to be suitable for analyzing and suggesting a few potential future applications of level-set based computations.

In this talk, I will present the theory of combinatorial multivector fields for finite topological spaces, the main subject of my thesis. The idea of combinatorial vector fields came from Forman and emerged naturally from discrete Morse theory. Lately, Mrozek generalized it to the multivector fields theory for Lefschetz complexes. In our work, we simplified and extended it to the finite topological spaces settings. We developed a combinatorial counterpart for dynamical objects, such as isolated invariant sets, isolating neighbourhoods, Conley index, limit sets, and Morse decomposition. We proved the additivity property of the Conley index and the Morse inequalities. Furthermore, we applied persistence homology to study the evolution and the stability of Morse decomposition. In the last part of the talk, I will show numerical results and potential future directions from a data-analysis perspective. 

Systems with lattice geometry can be renormalized exploiting their embedding in metric space, which naturally defines the coarse-grained nodes. By contrast, complex networks defy the usual techniques because of their small-world character and lack of explicit metric embedding. Current network renormalization approaches require strong assumptions (e.g. community structure, hyperbolicity, scale-free topology), thus remaining incompatible with generic graphs and ordinary lattices. Here we introduce a graph renormalization scheme valid for any hierarchy of coarse-grainings, thereby allowing for the definition of block-nodes across multiple scales. This approach reveals a necessary and specific dependence of network topology on an additive hidden variable attached to nodes, plus optional dyadic factors. Renormalizable networks turn out to be consistent with a unique specification of the fitness model, while they are incompatible with preferential attachment, the configuration model or the stochastic blockmodel. These results highlight a deep conceptual distinction between scale-free and scale-invariant networks, and provide a geometry-free route to renormalization. If the hidden variables are annealed, the model spontaneously leads to realistic scale-free networks with cut-off. If they are quenched, the model can be used to renormalize real-world networks with node attributes and distance-dependence or communities. As an example we derive an accurate multiscale model of the International Trade Network applicable across arbitrary geographic resolutions.

https://arxiv.org/abs/2009.11024 (23 sept.)

Modular and hierarchical structures are pervasive in real-world complex systems. A great deal of effort has gone into trying to detect and study these structures. Important theoretical advances in the detection of modular, or "community", structures have included identifying fundamental limits of detectability by formally defining community structure using probabilistic generative models. Detecting hierarchical community structure introduces additional challenges alongside those inherited from community detection. Here we present a theoretical study on hierarchical community structure in networks, which has thus far not received the same rigorous attention. We address the following questions: 1) How should we define a valid hierarchy of communities? 2) How should we determine if a hierarchical structure exists in a network? and 3) how can we detect hierarchical structure efficiently? We approach these questions by introducing a definition of hierarchy based on the concept of stochastic externally equitable partitions and their relation to probabilistic models, such as the popular stochastic block model. We enumerate the challenges involved in detecting hierarchies and, by studying the spectral properties of hierarchical structure, present an efficient and principled method for detecting them.

https://arxiv.org/abs/2009.07196 (15 sept.)

A link for this talk will be sent to our mailing list a day or two in advance.  If you are not on the list and wish to be sent a link, please send email to @email.