MS05: Interactions among analysis, optimization and network science
Organizers:
- Pietro Poggi-Corradini, Kansas State University
- Nathan Albin, Kansas State University
- Dominique Zosso, Montana State University
- Lukas Geyer, Montana State University
Session A: Oct.1, 10:40am-12:00pm, Classroom Building 103
Session B: Oct.1, 3:10pm-4:30pm, Classroom Building 103
Session C: Oct.1, 5:00pm-6:20pm, Classroom Building 103
Session D: Oct.2, 10:30Am-11:50am, Classroom Building 103
MS05-A-1 |
Tom Alberts, |
Random Matrix Theory for Homogenization of Composites |
I will discuss the random matrix theory behind two-component random resistor networks on general graphs. This involves random submatrices of the graph's Gamma projection operator, with the particular realization of the submatrix determined by the disorder of the conductances. Certain combinations of graph symmetries together with different models for the random conductances lead to exactly computable spectral statistics. I will discuss recent results for spectral statistics of a percolation model on the diamond hierarchical lattice. Joint work with Ken Golden, Elena Cherkaev, Ben Murphy, Han Le, Loren Santana. |
||
MS05-A-2 11:00am-11:20am (Oct 1) CLB 103 |
Vivian Healey, Texas State University |
The Resampling Property of Multiple Radial SLE |
Schramm-Loewner evolution (SLE) is a conformally-invariant process that describes the scaling limit of many statistical physics models in which an interface (random curve) appears at criticality. The radial version of this process generates a random curve in the disk from the boundary to an interior point. I will discuss the resampling property of the multiple-curve version of this process (as constructed in Healey-Lawler ’21). Joint work with Yilin Wang. |
||
MS05-A-3 11:20am-11:40am (Oct 1) CLB 103 |
Joan Lind, University of Tennessee Knoxville |
The scaling limit of fair Peano paths |
Random spanning trees on planar grids determine random Peano paths. We are interested in studying the limiting behavior of random Peano paths that arise in the context of spanning tree modulus. In contrast to the case for uniform spanning trees, where the scaling limit of the associated Peano paths is SLE(8), we show that the scaling limit of the Peano paths in our context is deterministic. This is joint work with Nathan Albin and Pietro Poggi-Corradini. |
||
MS05-A-4 11:40am-12:00pm (Oct 1) CLB 103 |
Lizaveta Ihnatsyeva, Kansas State University |
Riesz capacities and density conditions in metric space |
It is well known that the classical Newtonian capacity of a subset of the Euclidean space can be characterized as the minimum of an energy functional in terms of the weak gradient on the Sobolev space. This characterization has led to extensions of the notion of capacity in several directions and, in particular, to the development of a theory of capacities related to Riesz and Bessel potentials. In many cases the different definitions lead to comparable capacities. For instance, the Riesz (b,p)-capacity is comparable to the classical Newtonian capacity when b=1 and p=2. In out talk we consider Riesz capacities and the capacities defined in terms of Hajlasz gradients in the setting of a metric measure space. Our main goal is to clarify the connections between these two different notions. First, we prove a comparability result for the Riesz (b,p)-capacity and the relative Hajlasz (b,p)-capacity, for 0<b<=1 and p>1, under a suitable kernel estimate related to the Riesz potential. Then we show that in geodesic spaces the corresponding capacity density conditions are equivalent even without assuming the kernel estimate. The talk is based on a joint work with Javier Canto, Juha Lehrbäck and Antti V. Vähäkangas. |
||
MS05-B-1 3:10pm-3:30pm (Oct 1) CLB 103 |
Dominique Zosso, Montana State University |
From Convex Geometry to Convex Optimization |
In this talk we present an entirely geometric proof of the well-established Lagrange- and KKT-theorems for first order optimality conditions in the case of convex objectives and constraints. We largely refrain from using calculus and linear algebra concepts, and provide all the geometric definitions and tools in a visually accessible, self-contained form, instead. Our work makes extensive use of convex geometry elements such as tangent cones, normal cones, and hyperplanes of support, to define the objective function's properties such as convexity and sub-gradient. As a result, we provide an illustrative approach to convex optimization, accessible to students before formal calculus, for example. This is joint work with Alexandra Emmons, Henry Fessler, and Ryan Grady. |
||
MS05-B-2 3:30pm-3:50pm (Oct 1) CLB 103 |
Adriana M. Ortiz Aquino, Kansas State University |
An Approximation of the Modulus of the Family of Edge Covers |
Modulus on graphs is a very flexible and general tool for measuring the richness of families of objects defined on a graph. It has been shown that the modulus of special families generalizes classical network theoretic quantities such as shortest path, max flow/min cut, and effective resistance. Our focus is on the p-modulus of the families of edge covers, specifically on the family of fractional edge covers on an unweighted, undirected graph. Direct computation of the modulus can be expensive because these families tend to be exponentially large, leading to a large number of constraints for the modulus problem. Furthermore, computing the modulus of edge covers is difficult (no known efficient algorithm), but if we could compute the modulus of fractional edge covers we obtain an upper bound for the modulus of edge covers. Through the theory of Fulkerson blocking duality, every family of objects has a corresponding dual family, whose modulus is closely related to the modulus of the original family. Our results show that the dual family of fractional edge covers is the family of stars, which greatly reduces the number of constraints for the p-modulus problem. With this we give an approximation for the modulus of edge covers using the modulus of fractional edge covers, and study the complexity of calculating the modulus over the family of stars compared to the family of edge covers. |
||
MS05-B-3 3:50pm-4:10pm (Oct 1) CLB 103 |
Mike Higgins, Kansas State University |
Estimation of causal effects under K-nearest neighbors interference |
In causal inference, an experiment exhibits treatment interference when the treatment status of one unit affects the response of other units. While traditional causal inference methods often assume no interference between units, there has been a recent abundance of work on the design and analysis of experiments under treatment interference—for example, those conducted on social networks. We develop properties for the K-nearest neighbors interference model (KNNIM)---a model of treatment interference where the response of a unit depends only on its treatment status and the statuses of units within its K-neighborhood. We define causal estimands for direct and indirect effects under KNNIM and propose Horvitz-Thompson (HT) unbiased estimators for these estimands. We then derive properties and provide conservative variance estimators for the proposed HT estimators. We show the efficacy of our estimators using a simulation study and a study on the efficacy of an anti-conflict program from a randomized experiment among middle school students in New Jersey. |
||
MS05-B-4 4:10pm-4:30pm (Oct 1) CLB 103 |
Nethali Fernando, University of Texas Arlington |
Identifying graph-derived features of trained neuronal networks via machine learning |
Neuronal circuits are plastic. Neurons can modulate their connections to form new connections and adjust the strength of current connections to learn new tasks. Among the multiple proposed mechanisms for network training, the full-FORCE model presents a target-based method for modifying the connectivity matrix of a recurrent network to train it to learn temporally complex signals. In this study, we investigate the relationship between the network architecture and the learning that occurs in these neuronal networks. Specifically, we simulate full-FORCE networks learning different types of periodic signals and keep track of the plasticity adjacency matrices of the trained networks. These matrices are pre-processed and then fed into a graph metrics wrapper which provides an ensemble of graph features related to the trained network. We apply an ensemble of machine learning methods to disambiguate the different signals using these graph features. The highest balanced accuracy that we have achieved is 79\%. This demonstrates that trained networks have graph features that imprints information of their original signals. Among the commonly selected graph features were, average degree connectivity, edge betweenness centrality, degree centrality and core number of the graphs. |
||
MS05-C-1 5:00pm-5:20pm (Oct 1) CLB 103 |
Braxton Osting,
University of Utah |
Extremal graph realizations and graph Laplacian eigenvalues |
For a regular polyhedron (or polygon) centered at the origin, the coordinates of the vertices are eigenvectors of the graph Laplacian for the skeleton of that polyhedron (or polygon) associated with the first (non-trivial) eigenvalue. In this talk, I'll discuss a generalization of this relationship. For a given graph, we study the eigenvalue optimization problem of maximizing the first (non-trivial) eigenvalue of the graph Laplacian over non-negative edge weights. We show that the spectral realization of the graph using the eigenvectors corresponding to the solution of this problem, under certain assumptions, is a centered, unit-distance graph realization that has maximal total variance. This result gives a new method for generating unit-distance graph realizations and is based on convex duality. A drawback of this method is that the dimension of the realization is given by the multiplicity of the extremal eigenvalue, which is typically unknown prior to solving the eigenvalue optimization problem. Our results are illustrated with a number of examples. |
||
MS05-C-2 5:20pm-5:40pm (Oct 1) |
Xavier Perez Gimenez, University of Nebraska Lincoln |
The Phase Transition of Discrepancy in Random Hypergraphs |
The discrepancy of a hypergraph is a well-studied parameter which measures how well we can color the vertices with 2 colors so that the edges are as balanced as possible. A famous conjecture of Beck and Fiala states that every hypergraph of maximum degree d has discrepancy O(d^{1/2}). In recent years, there has been a significant effort to prove this conjecture (which still remains open) and also characterize the discrepancy of several families of deterministic and random hypergraphs. In this talk, we will describe some of our recent results, which provide nearly tight lower bounds on the discrepancy of two natural models of random hypergraphs. The proofs include both probabilistic and algorithmic ingredients. (This is joint work with Calum MacRury, Tomas Masarik and Leilani Pai.) |
||
MS05-C-3 |
Pietro Poggi-Corradini, Kansas State University |
p-Modulus on orthodiagonal maps |
Orthodiagonal maps are a type of quadrangulation of plane domains that arise in numerical analysis in the context of Delaunay triangulations and Voronoi graphs, but also in the theory of circle packings, and have been studied previously in the literature, by Skopenkov, Werness, Gurel-Gurevich, Jerison and Nachmias, et al. We show that, for p > 1, discrete p-modulus on orthodiagonal maps converges to the analog p-modulus in the continuum, as the mesh size of the map tends to zero. This is joint work with Nathan Albin, Joan Lind, and Pekka Pankka. |
||
MS05-D-1 10:30am-10:50am (Oct 2) |
Tyrrell McAllister, University of Wyoming |
Ehrhart polynomials of pseudo-reflexive polygons |
The problem of determining which polynomials are the Ehrhart polynomials of convex rational polytopes is open and unlikely to be resolved soon. Even just in dimension 2, this problem has been solved only for convex lattice polygons. However, not all Ehrhart polynomials come from lattice polytopes. More generally, a pseudo-integral polytope is a rational polytope P such that, as with lattice polytopes, the Ehrhart counting function t → |tP ∩ Z| is a polynomial function of t ∈ Z_{>=1}. In particular, P is pseudo-reflexive if its polar dual P^{*} is a lattice polytope. We extend the classification of Ehrhart polynomials to include the Ehrhart polynomials of all pseudo-reflexive triangles. Our approach generalizes techniques developed by Hille & Skarke (2002) to study lattice points in reflexive (lattice) polygons. These techniques exploit a particular presentation of the group SL_{2}(Z). In the case of pseudo-reflexive triangles, this approach reduces to studying the positive integer solutions to a certain nonlinear Diophantine equation. |
||
MS05-D-2 10:50am-11:10am (Oct 2) |
Huy Truong, Kansas State University |
Fulkerson duality for spanning trees and partitions |
We describe Fulkerson duality for spanning trees, the proof uses a result of Nash and Tutte. Then, we study the modulus problem for this dual family. In particular, we introduce the notion of fair feasible partitions. Among those fair feasible partitions, there are two that are very important: they represent the strength and the maximum denseness of arbitrary graphs. They also give rise to two reversed deflation processes that identify a hierarchical structure of general graphs. |
||
MS05-D-3 11:10am-11:30am (Oct 2) |
Aram Vajdi, Kansas State University |
A Non-Markovian networked spreading model to assess the effectiveness of contact tracing |
Compartmental spreading models traditionally assume exponential distributions for the states’ sojourn times. This is in contrast to the data regarding the COVID-19 infectious and quarantine periods. To model COVID-19 spreading and assess the effectiveness of contact tracing we have developed a non-Markovian network-based spreading model that allows non-exponential distributions for the states’ sojourn times. Using the mean-field approximation we have derived an expression for the epidemic threshold, which guaranties the exponential die-out of the infection in a population. We also applied the model to a real-world COVID-19 spreading and we found that contact tracing can be an effective outbreak mitigation measure by reducing the epidemic size by more than three-fold. |