Search

Influence propagation in social networks is a central problem in modern social network analysis, with important societal applications in politics and advertising. A large body of work has focused on cascading models, viral marketing, and finite-horizon diffusion. There is, however, a need for more developed, mathematically principled \emph{adversarial models}, in which multiple, opposed actors strategically select nodes whose influence will maximally sway the crowd to their point of view. In the present work, we develop and analyze such a model based on harmonic functions and linear diffusion. We prove that our general problem is NP-hard and that the objective function is monotone and submodular; consequently, we can greedily approximate the solution within a constant factor. Introducing and analyzing a convex relaxation, we show that the problem can be approximately solved using smooth optimization methods. We illustrate the effectiveness of our approach on a variety of example networks., Comment: 23 pages, 5 figures, comments welcome!!

Many empirical networks originate from correlational data, arising in domains as diverse as psychology, neuroscience, genomics, microbiology, finance, and climate science. Specialized algorithms and theory have been developed in different application domains for working with such networks, as well as in statistics, network science, and computer science, often with limited communication between practitioners in different fields. This leaves significant room for cross-pollination across disciplines. A central challenge is that it is not always clear how to best transform correlation matrix data into networks for the application at hand, and probably the most widespread method, i.e., thresholding on the correlation value to create either unweighted or weighted networks, suffers from multiple problems. In this article, we review various methods of constructing and analyzing correlation networks, ranging from thresholding and its improvements to weighted networks, regularization, dynamic correlation networks, threshold-free approaches, and more. Finally, we propose and discuss a variety of key open questions currently confronting this field., Comment: 1 figure

We analyze the performance of graph neural network (GNN) architectures from the perspective of random graph theory. Our approach promises to complement existing lenses on GNN analysis, such as combinatorial expressive power and worst-case adversarial analysis, by connecting the performance of GNNs to typical-case properties of the training data. First, we theoretically characterize the nodewise accuracy of one- and two-layer GCNs relative to the contextual stochastic block model (cSBM) and related models. We additionally prove that GCNs cannot beat linear models under certain circumstances. Second, we numerically map the recoverability thresholds, in terms of accuracy, of four diverse GNN architectures (GCN, GAT, SAGE, and Graph Transformer) under a variety of assumptions about the data. Sample results of this second analysis include: heavy-tailed degree distributions enhance GNN performance, GNNs can work well on strongly heterophilous graphs, and SAGE and Graph Transformer can perform well on arbitrarily noisy edge data, but no architecture handled sufficiently noisy feature data well. Finally, we show how both specific higher-order structures in synthetic data and the mix of empirical structures in real data have dramatic effects (usually negative) on GNN performance., Comment: 28 pages

Genealogical networks (i.e. family trees) are of growing interest, with the largest known data sets now including well over one billion individuals. Interest in family history also supports an 8.5 billion dollar industry whose size is projected to double within 7 years (FutureWise report HC1137). Yet little mathematical attention has been paid to the complex network properties of genealogical networks, especially at large scales. The structure of genealogical networks is of particular interest due to the practice of forming unions, e.g. marriages, that are typically well outside one's immediate family. In most other networks, including other social networks, no equivalent restriction exists on the distance at which relationships form. To study the effect this has on genealogical networks we use persistent homology to identify and compare the structure of 101 genealogical and 31 other social networks. Specifically, we introduce the notion of a network's persistence curve, which encodes the network's set of persistence intervals. We find that the persistence curves of genealogical networks have a distinct structure when compared to other social networks. This difference in structure also extends to subnetworks of genealogical and social networks suggesting that, even with incomplete data, persistent homology can be used to meaningfully analyze genealogical networks. Here we also describe how concepts from genealogical networks, such as common ancestor cycles, are represented using persistent homology. We expect that persistent homology tools will become increasingly important in genealogical exploration as popular interest in ancestry research continues to expand.

We provide a rearrangement based algorithm for fast detection of subgraphs of $k$ vertices with long escape times for directed or undirected networks. Complementing other notions of densest subgraphs and graph cuts, our method is based on the mean hitting time required for a random walker to leave a designated set and hit the complement. We provide a new relaxation of this notion of hitting time on a given subgraph and use that relaxation to construct a fast subgraph detection algorithm and a generalization to $K$-partitioning schemes. Using a modification of the subgraph detector on each component, we propose a graph partitioner that identifies regions where random walks live for comparably large times. Importantly, our method implicitly respects the directed nature of the data for directed graphs while also being applicable to undirected graphs. We apply the partitioning method for community detection to a large class of model and real-world data sets., Comment: 22 pages, 10 figures, 1 table, comments welcome!!

Motivated by the COVID-19 pandemic, this paper explores the supply chain viability of medical equipment, an industry whose supply chain was put under a crucial test during the pandemic. This paper includes an empirical network-level analysis of supplier reachability under Random Failure Experiment (RFE) and Intelligent Attack Experiment (IAE). Specifically, this study investigates the effect of RFA and IAE across multiple tiers and scales. The global supply chain data was mined and analyzed from about 45,000 firms with about 115,000 intertwined relationships spanning across 10 tiers of the backward supply chain of medical equipment. This complex supply chain network was analyzed at four scales, namely: firm, country-industry, industry, and country. A notable contribution of this study is the application of a supply chain tier optimization tool to identify the lowest tier of the supply chain that can provide adequate resolution for the study of the supply chain pattern. We also developed data-driven-tools to identify the thresholds for breakdown and fragmentation of the medical equipment supply chain when faced with random failures or different intelligent attack scenarios. The novel network analysis tools utilized in the study can be applied to the study of supply chain reachability and viability in other industries., Comment: 47 pages

The shortest-path, commute time, and diffusion distances on undirected graphs have been widely employed in applications such as dimensionality reduction, link prediction, and trip planning. Increasingly, there is interest in using asymmetric structure of data derived from Markov chains and directed graphs, but few metrics are specifically adapted to this task. We introduce a metric on the state space of any ergodic, finite-state, time-homogeneous Markov chain and, in particular, on any Markov chain derived from a directed graph. Our construction is based on hitting probabilities, with nearness in the metric space related to the transfer of random walkers from one node to another at stationarity. Notably, our metric is insensitive to shortest and average walk distances, thus giving new information compared to existing metrics. We use possible degeneracies in the metric to develop an interesting structural theory of directed graphs and explore a related quotienting procedure. Our metric can be computed in $O(n^3)$ time, where $n$ is the number of states, and in examples we scale up to $n=10,000$ nodes and $\approx 38M$ edges on a desktop computer. In several examples, we explore the nature of the metric, compare it to alternative methods, and demonstrate its utility for weak recovery of community structure in dense graphs, visualization, structure recovering, dynamics exploration, and multiscale cluster detection., Comment: 26 pages, 9 figures, for associated code, visit https://github.com/zboyd2/hitting_probabilities_metric, accepted at SIAM J. Math. Data Sci

Intrafraction motion can play a pivotal role in the success of abdominal and thoracic radiation therapy. Hybrid magnetic resonance-guided radiotherapy systems have the potential to control for intrafraction motion. Recently, we introduced an MRI sequence capable of acquiring real-time cine imaging in two orthogonal planes (SOPI). We extend SOPI here to permit dynamic updating of slice positions in one plane while keeping the other plane position fixed. In this implementation, cine images from the static plane are used for motion monitoring and as image navigators to sort stepped images in the other plane, producing dynamic 4D image volumes for use in dose reconstruction. A custom 3D-printed target filled with radiochromic FXG gel was interfaced to a dynamic motion phantom. 4D-SOPI was acquired in a dynamic motion phantom driven by an actual patient respiratory waveform displaying amplitude/frequency variations and drifting and in a healthy volunteer. Unique 4D-MRI epochs were reconstructed from a time series of phantom motion. Dose from a static 4cmx15cm field was calculated on each 4D respiratory phase bin and epoch image, scaled by the time spent in each bin, and then rigidly accumulated. The phantom was then positioned on an Elekta MR Linac and irradiated while moving. Following irradiation, actual dose deposited to the FXG gel was determined by applying a R1 versus dose calibration curve to R1 maps of the phantom. The 4D-SOPI cine images produced a respiratory motion navigator that was highly correlated with the actual phantom motion (CC=0.9981). The mean difference between the accumulated and measured dose inside the target was 4.4% of the maximum prescribed dose. These results provide early validation that 4D-SOPI simultaneously enables real-time motion monitoring and truth-in-delivery analysis for integrated MR-guided radiation therapy (MR-gRT) systems., Comment: 26 pages, 12 figures, submitted to Physics in Medicine and Biology

Networks, which represent agents and interactions between them, arise in myriad applications throughout the sciences, engineering, and even the humanities. To understand large-scale structure in a network, a common task is to cluster a network's nodes into sets called "communities", such that there are dense connections within communities but sparse connections between them. A popular and statistically principled method to perform such clustering is to use a family of generative models known as stochastic block models (SBMs). In this paper, we show that maximum likelihood estimation in an SBM is a network analog of a well-known continuum surface-tension problem that arises from an application in metallurgy. To illustrate the utility of this relationship, we implement network analogs of three surface-tension algorithms, with which we successfully recover planted community structure in synthetic networks and which yield fascinating insights on empirical networks that we construct from hyperspectral videos., Comment: to appear in Journal of Nonlinear Science

Previous work has shown that the one-dimensional (1D) inviscid compressible flow (Euler) equations admit a wide variety of scale-invariant solutions (including the famous Noh, Sedov, and Guderley shock solutions) when the included equation of state (EOS) closure model assumes a certain scale-invariant form. However, this scale-invariant EOS class does not include even simple models used for shock compression of crystalline solids, including many broadly applicable representations of Mie-Gr\"uneisen EOS. Intuitively, this incompatibility naturally arises from the presence of multiple dimensional scales in the Mie-Gr\"uneisen EOS, which are otherwise absent from scale-invariant models that feature only dimensionless parameters (such as the adiabatic index in the ideal gas EOS). The current work extends previous efforts intended to rectify this inconsistency, by using a scale-invariant EOS model to approximate a Mie- Gr\"uneisen EOS form. To this end, the adiabatic bulk modulus for the Mie-Gr\"uneisen EOS is constructed, and its key features are used to motivate the selection of a scale-invariant approximation form. The remaining surrogate model parameters are selected through enforcement of the Rankine-Hugoniot jump conditions for an infinitely strong shock in a Mie-Gr\"uneisen material. Finally, the approximate EOS is used in conjunction with the 1D inviscid Euler equations to calculate a semi-analytical, Guderley-like imploding shock solution in a metal sphere, and to determine if and when the solution may be valid for the underlying Mie-Gr\"uneisen EOS., Comment: 28 pages, 5 figures, Submitted to Physics of Fluids

As modern hydrodynamic codes increase in sophistication, the availability of realistic test problems becomes increasingly important. In gas dynamics, one common unrealistic aspect of most test problems is the ideal gas assumption, which is unsuited to many real applications, especially those involving high pressure and speed metal deformation. Our work considers the collapsing cavity and converging shock test problems, showing to what extent the ideal gas assumption can be removed from their specification. It is found that while most materials simply do not admit simple (i.e. scaling) solutions in this context, there are infinite-dimensional families of materials which do admit such solutions. We characterize such materials, derive the appropriate ordinary differential equations, and analyze the associated nonlinear eigenvalue problem. It is shown that there is an inherent tension between boundedness of the solution, boundedness of its derivatives, and the entropy condition. The special case of a constant-speed cavity collapse is considered and found to be heuristically possible, contrary to common intuition. Finally, we give an example of a concrete non-ideal collapsing cavity scaling solution based on a recently proposed pseudo-Mie-Gruneisen equation of state., Comment: 20 pages, 3 figures, accepted at Qu. J. Mech. Appl. Math

Networks capture pairwise interactions between entities and are frequently used in applications such as social networks, food networks, and protein interaction networks, to name a few. Communities, cohesive groups of nodes, often form in these applications, and identifying them gives insight into the overall organization of the network. One common quality function used to identify community structure is modularity. In Hu et al. [SIAM J. App. Math., 73(6), 2013], it was shown that modularity optimization is equivalent to minimizing a particular nonconvex total variation (TV) based functional over a discrete domain. They solve this problem, assuming the number of communities is known, using a Merriman, Bence, Osher (MBO) scheme. We show that modularity optimization is equivalent to minimizing a convex TV-based functional over a discrete domain, again, assuming the number of communities is known. Furthermore, we show that modularity has no convex relaxation satisfying certain natural conditions. We therefore, find a manageable non-convex approximation using a Ginzburg Landau functional, which provably converges to the correct energy in the limit of a certain parameter. We then derive an MBO algorithm with fewer hand-tuned parameters than in Hu et al. and which is 7 times faster at solving the associated diffusion equation due to the fact that the underlying discretization is unconditionally stable. Our numerical tests include a hyperspectral video whose associated graph has 2.9x10^7 edges, which is roughly 37 times larger than was handled in the paper of Hu et al., Comment: 25 pages, 3 figures, 3 tables, submitted to SIAM J. App. Math

We extend Guderley's problem of finding a self-similar scaling solution for a converging cylindrical or spherical shock wave from the ideal gas case to the case of flows with an arbitrary equation of state closure model, giving necessary conditions for the existence of a solution. The necessary condition is a thermodynamic one, namely that the adiabatic bulk modulus, $K_S$, of the fluid be of the form $pf(\rho)$ where $p$ is pressure, $\rho$ is mass density, and $f$ is an arbitrary function. Although this condition has appeared in the literature before, here we give a more rigorous and extensive treatment. Of particular interest is our novel analysis of the governing ordinary differential equations (ODEs), which shows that, in general, the Guderley problem is always an eigenvalue problem. The need for an eigenvalue arises from basic shock stability principles -- an interesting connection to the existing literature on the relationship between self-similarity of the second kind and stability. We also investigate a special case, usually neglected by previous authors, where assuming constant shock velocity yields a reduction to ODEs for every material, but those ODEs never have a bounded, differentiable solution. This theoretical work is motivated by the need for more realistic test problems in the verification of inviscid compressible flow codes that simulate flows in a variety of non-ideal gas materials., Comment: 18 pages, 0 figures, in press at Qu. J. Mech. and Appl. Math