Engineering Papers⌕ Search

SEARCH · Engineering Papers

Results for “random graphs”

Search indexed NASA NTRS and DOE OSTI research on propulsion, heat transfer, battery materials and energy systems. Follow report and document links to the original sources.

Quote a phrase for an exact phrase match. Source license links do not imply unrestricted reuse.

At least 37 records · Page 2
All sourcesNASA NTRSDOE OSTI
DOE OSTI2022

Opinion dynamics in financial markets via random networks

We investigate financial market dynamics by introducing a heterogeneous agent-based opinion formation model. In this work, we organize individuals in a financial market according to their trading strategy, namely, whether they are noise traders or fundamentalists. The opinion of a local majority compels the market exchanging behavior of noise traders, whereas the global behavior of the market influences the decisions of fundamentalist agents. We introduce a noise parameter, q , to represent the level of anxiety and perceived uncertainty regarding market behavior, enabling the possibility of adrift financial action. We place individuals as nodes in an Erdös-Rényi random graph, where the links represent their social interactions. At any given time, individuals assume one of two possible opinion states ±1 regarding buying or selling an asset. The model exhibits fundamental qualitative and quantitative real-world market features such as the distribution of logarithmic returns with fat tails, clustered volatility, and the long-term correlation of returns. We use Student’s t distributions to fit the histograms of logarithmic returns, showing a gradual shift from a leptokurtic to a mesokurtic regime depending on the fraction of fundamentalist agents. Furthermore, we compare our results with those concerning the distribution of the logarithmic returns of several real-world financial indices.

97 MATHEMATICS AND COMPUTING↗
DOE OSTI2025

Comparing three generations of D-Wave quantum annealers for minor embedded combinatorial optimization problems

Abstract Quantum annealing (QA) is a novel type of analog computation that aims to use quantum mechanical fluctuations to search for optimal solutions of Ising problems. QA in the transverse Ising model, implemented on D-Wave quantum processing units, are available as cloud computing resources. In this study we report concise benchmarks across three generations of D-Wave quantum annealers, consisting of four different devices, for the NP-hard discrete combinatorial optimization problems unweighted maximum clique and unweighted maximum cut on random graphs. The Ising, or equivalently quadratic unconstrained binary optimization, formulation of these problems do not require auxiliary variables for order reduction, and their overall structure and weights are not highly variable, which makes these problems simple test cases to understand the sampling capability of current D-Wave quantum annealers. All-to-all minor embeddings of size 52, with relatively uniform chain lengths, are used for a direct comparison across the Chimera, Pegasus, and Zephyr device topologies. A grid-search over annealing times and the minor embedding chain strengths is performed in order to determine the level of reasonable performance for each device and problem type. Experiment metrics that are reported are approximation ratios for non-broken chain samples, chain break proportions, and time-to-solution for the maximum clique problem instances. How fairly the quantum annealers sample optimal maximum cliques, for instances which contain multiple maximum cliques, is quantified using entropy of the measured ground state distributions. The newest generation of quantum annealing hardware, which has a Zephyr hardware connectivity, performed the best overall with respect to approximation ratios and chain break frequencies.

71 CLASSICAL AND QUANTUM MECHANICS, GENERAL PHYSIC↗
DOE OSTI2024

DLSIA: Deep Learning for Scientific Image Analysis

DLSIA (Deep Learning for Scientific Image Analysis) is a Python-based machine learning library that empowers scientists and researchers across diverse scientific domains with a range of customizable convolutional neural network (CNN) architectures for a wide variety of tasks in image analysis to be used in downstream data processing. DLSIA features easy-to-use architectures, such as autoencoders, tunable U-Nets and parameter-lean mixed-scale dense networks (MSDNets). Additionally, this article introduces sparse mixed-scale networks (SMSNets), generated using random graphs, sparse connections and dilated convolutions connecting different length scales. For verification, several DLSIA-instantiated networks and training scripts are employed in multiple applications, including inpainting for X-ray scattering data using U-Nets and MSDNets, segmenting 3D fibers in X-ray tomographic reconstructions of concrete using an ensemble of SMSNets, and leveraging autoencoder latent spaces for data compression and clustering. As experimental data continue to grow in scale and complexity, DLSIA provides accessible CNN construction and abstracts CNN complexities, allowing scientists to tailor their machine learning approaches, accelerate discoveries, foster interdisciplinary collaboration and advance research in scientific image analysis.

97 MATHEMATICS AND COMPUTING↗
DOE OSTI2022

Interference Moral Hazard in Large Multihop Networks

Cooperation between network nodes is critical for supporting services in ad hoc networks. Cooperation, however, is an idealized assumption that may not always be present. This assumption can fail because of moral hazard, a scenario in part caused by misaligned incentives between the requesting node and supporting node. In this paper, we characterize a moral hazard that perversely incentivizes nodes to increase their routing payments by transmitting interference into the multi-hop network. We refer to this as the interference moral hazard (IMH) problem which is inherent to strategyproof mechanisms with low overpayments. We investigate IMH as a non-cooperative game played by network nodes on a random graph. For large networks, we show that IMH can be solved in the network design space. Finally, we provide sufficient conditions on the network distribution that guarantee an equilibrium path with interference-free play. This is achieved by 1) lower-bounding the number of nodes and 2) bounding the network density slightly above the 2-connectedness threshold and below a proposed upper-bound. Simulations suggest that density plays a fundamental role in IMH.

42 ENGINEERING↗
DOE OSTI2022

People who inject drugs in metropolitan Chicago: A meta-analysis of data from 1997-2017 to inform interventions and computational modeling toward hepatitis C microelimination

Progress toward hepatitis C virus (HCV) elimination in the United States is not on track to meet targets set by the World Health Organization, as the opioid crisis continues to drive both injection drug use and increasing HCV incidence. A pragmatic approach to achieving this is using a microelimination approach of focusing on high-risk populations such as people who inject drugs (PWID). Computational models are useful in understanding the complex interplay of individual, social, and structural level factors that might alter HCV incidence, prevalence, transmission, and treatment uptake to achieve HCV microelimination. However, these models need to be informed with realistic sociodemographic, risk behavior and network estimates on PWID. We conducted a meta-analysis of research studies spanning 20 years of research and interventions with PWID in metropolitan Chicago to produce parameters for a synthetic population for realistic computational models (e.g., agent-based models). We then fit an exponential random graph model (ERGM) using the network estimates from the meta-analysis in order to develop the network component of the synthetic population.

60 APPLIED LIFE SCIENCES↗
DOE OSTI2024

Compiling Quantum Circuits for Dynamically Field-Programmable Neutral Atoms Array Processors

Dynamically field-programmable qubit arrays (DPQA) have recently emerged as a promising platform for quantum information processing. In DPQA, atomic qubits are selectively loaded into arrays of optical traps that can be reconfigured during the computation itself. Leveraging qubit transport and parallel, entangling quantum operations, different pairs of qubits, even those initially far away, can be entangled at different stages of the quantum program execution. Such reconfigurability and non-local connectivity present new challenges for compilation, especially in the layout synthesis step which places and routes the qubits and schedules the gates. In this paper, we consider a DPQA architecture that contains multiple arrays and supports 2D array movements, representing cutting-edge experimental platforms. Within this architecture, we discretize the state space and formulate layout synthesis as a satisfiability modulo theories problem, which can be solved by existing solvers optimally in terms of circuit depth. For a set of benchmark circuits generated by random graphs with complex connectivities, our compiler OLSQ-DPQA reduces the number of two-qubit entangling gates on small problem instances by 1.7x compared to optimal compilation results on a fixed planar architecture. To further improve scalability and practicality of the method, we introduce a greedy heuristic inspired by the iterative peeling approach in classical integrated circuit routing. Using a hybrid approach that combined the greedy and optimal methods, we demonstrate that our DPQA-based compiled circuits feature reduced scaling overhead compared to a grid fixed architecture, resulting in 5.1X less two-qubit gates for 90 qubit quantum circuits. These methods enable programmable, complex quantum circuits with neutral atom quantum computers, as well as informing both future compilers and future hardware choices.

Physics↗
DOE OSTI2025

Diffusion Codes: Self-Correction from Small(er)-Set Expansion with Tunable Non-locality

Optimal constructions of classical LDPC codes can be obtained by choosing the Tanner graph uniformly at random among biregular graphs. We introduce a class of codes that we call ``diffusion codes'', defined by placing each edge connecting bits and checks on some graph, and acting on that graph with a random SWAP network. By tuning the depth of the SWAP network, we can tune a tradeoff between the amount of randomness -- and hence the optimality of code parameters -- and locality with respect to the underlying graph. For diffusion codes defined on the cycle graph, if the SWAP network has depth $\sim Tn$ with $T> n^{2β}$ for arbitrary $β>0$, then we prove that almost surely the Tanner graph is a lossless ``smaller set'' vertex expander for small sets up size $δ\sim \sqrt T \sim n^β$, with bounded bit and check degree. At the same time, the geometric size of the largest stabilizer is bounded by $\sqrt T$ in graph distance. We argue, based on physical intuition, that this result should hold more generally on arbitrary graphs. By taking hypergraph products of these classical codes we obtain quantum LDPC codes defined on the torus with smaller-set boundary and co-boundary expansion and the same expansion/locality tradeoffs as for the classical codes. These codes are self-correcting and admit single-shot decoding, while having the geometric size of the stabilizer growing as an arbitrarily small power law. Our proof technique establishes mixing of a random SWAP network on small subsystems at times scaling with only the subsystem size, which may be of independent interest.

Combinatorics (math.CO)↗
DOE OSTI2021

Hierarchical effects facilitate spreading processes on synthetic and empirical multilayer networks

In this paper we consider the effects of corporate hierarchies on innovation spread across multilayer networks, modeled by an elaborated SIR framework. We show that the addition of management layers can significantly improve spreading processes on both random geometric graphs and empirical corporate networks. Additionally, we show that utilizing a more centralized working relationship network rather than a strict administrative network further increases overall innovation reach. In fact, this more centralized structure in conjunction with management layers is essential to both reaching a plurality of nodes and creating a stable adopted community in the long time horizon. Further, we show that the selection of seed nodes affects the final stability of the adopted community, and while the most influential nodes often produce the highest peak adoption, this is not always the case. In some circumstances, seeding nodes near but not in the highest positions in the graph produces larger peak adoption and more stable long-time adoption.

97 MATHEMATICS AND COMPUTING↗
DOE OSTI2021

Preventing Failures By Dataset Shift Detection in Safety-Critical Graph Applications

Dataset shift refers to the problem where the input data distribution may change over time (e.g., between training and test stages). Since this can be a critical bottleneck in several safety-critical applications such as healthcare, drug-discovery, etc., dataset shift detection has become an important research issue in machine learning. Though several existing efforts have focused on image/video data, applications with graph-structured data have not received sufficient attention. Therefore, in this paper, we investigate the problem of detecting shifts in graph structured data through the lens of statistical hypothesis testing. Specifically, we propose a practical two-sample test based approach for shift detection in large-scale graph structured data. Our approach is very flexible in that it is suitable for both undirected and directed graphs, and eliminates the need for equal sample sizes. Using empirical studies, we demonstrate the effectiveness of the proposed test in detecting dataset shifts. We also corroborate these findings using real-world datasets, characterized by directed graphs and a large number of nodes.

97 MATHEMATICS AND COMPUTING↗
DOE OSTI2022

Randomized Cholesky Preconditioning for Graph Partitioning Applications

A graph is a mathematical representation of a network; we say it consists of a set of vertices, which are connected by edges. Graphs have numerous applications in various fields, as they can model all sorts of connections, processes, or relations. For example, graphs can model intricate transit systems or the human nervous system. However, graphs that are large or complicated become difficult to analyze. This is why there is an increased interest in the area of graph partitioning, reducing the size of the graph into multiple partitions. For example, partitions of a graph representing a social network might help identify clusters of friends or colleagues. Graph partitioning is also a widely used approach to load balancing in parallel computing. The partitioning of a graph is extremely useful to decompose the graph into smaller parts and allow for easier analysis. There are different ways to solve graph partitioning problems. For this work, we focus on a spectral partitioning method which forms a partition based upon the eigenvectors of the graph Laplacian (details presented in Acer, et. al.). This method uses the LOBPCG algorithm to compute these eigenvectors. LOBPCG can be accelerated by an operator called a preconditioner. For this internship, we evaluate a randomized Cholesky (rchol) preconditioner for its effectiveness on graph partitioning problems with LOBPCG. We compare it with two standard preconditioners: Jacobi and Incomplete Cholesky (ichol). This research was conducted from August to December 2021 in conjunction with Sandia National Laboratories.

97 MATHEMATICS AND COMPUTING↗
DOE OSTI2022

Randomized Cholesky Preconditioning for Graph Partitioning Applications

Graph partitioning has emerged as an area of interest due to its use in various applications in computational research. One way to partition a graph is to solve for the eigenvectors of the corresponding graph Laplacian matrix. This project focuses on the eigensolver LOBPCG and the evaluation of a new preconditioner: Randomized Cholesky Factorization (rchol). This proconditioner was tested for its speed and accuracy against other well-known preconditioners for the method. After experiments were run on several known test matrices, rchol appears to be a better preconditioner for structured matrices. This research was sponsored by National Nuclear Security Administration Minority Serving Institutions Internship Program (NNSA-MSIIP) and completed at host facility Sandia National Laboratories. As such, after discussion of the research project itself, this report contains a brief reflection on experience gained as a result of participating in the NNSA-MSIIP.

97 MATHEMATICS AND COMPUTING↗
DOE OSTI2024

Understanding random-walk dynamical phase coexistence through waiting times

We study the appearance of first-order dynamical phase transitions (DPTs) as “intermittent” coexisting phases in the fluctuations of random walks on graphs. We show that the diverging timescale leading to critical behavior is the waiting time to jump from one phase to another. This timescale is crucial for observing the system's relaxation to stationarity and demonstrate ergodicity of the system at criticality. We illustrate these results through three analytical examples which provide insights into random walks exploring random graphs. Published by the American Physical Society 2024

Stuhrmann, David C. (ORCID:0009000726916649)↗
DOE OSTI2023

Solving MaxCut with quantum imaginary time evolution

We introduce a method to solve the MaxCut problem efficiently based on quantum imaginary time evolution (QITE). We employ a linear Ansatz for unitary updates and an initial state involving no entanglement, as well as an imaginary-time-dependent Hamiltonian interpolating between a given graph and a subgraph with two edges excised. We apply the method to thousands of randomly selected graphs with up to fifty vertices. We show that our algorithm exhibits a 93% and above performance converging to the maximum solution of the MaxCut problem for all considered graphs. Our results compare favorably with the performance of classical algorithms, such as the greedy and Goemans–Williamson algorithms. We also discuss the overlap of the final state of the QITE algorithm with the ground state as a performance metric, which is a quantum feature not shared by other classical algorithms.

97 MATHEMATICS AND COMPUTING↗
DOE OSTI2025

A framework to evaluate machine learning crystal stability predictions

The rapid adoption of machine learning in various scientific domains calls for the development of best practices and community agreed-upon benchmarking tasks and metrics. We present Matbench Discovery as an example evaluation framework for machine learning energy models, here applied as pre-filters to first-principles computed data in a high-throughput search for stable inorganic crystals. We address the disconnect between (1) thermodynamic stability and formation energy and (2) retrospective and prospective benchmarking for materials discovery. Alongside this paper, we publish a Python package to aid with future model submissions and a growing online leaderboard with adaptive user-defined weighting of various performance metrics allowing researchers to prioritize the metrics they value most. To answer the question of which machine learning methodology performs best at materials discovery, our initial release includes random forests, graph neural networks, one-shot predictors, iterative Bayesian optimizers and universal interatomic potentials. We highlight a misalignment between commonly used regression metrics and more task-relevant classification metrics for materials discovery. Accurate regressors are susceptible to unexpectedly high false-positive rates if those accurate predictions lie close to the decision boundary at 0 eV per atom above the convex hull. The benchmark results demonstrate that universal interatomic potentials have advanced sufficiently to effectively and cheaply pre-screen thermodynamic stable hypothetical materials in future expansions of high-throughput materials databases.

Riebesell, Janosh↗
DOE OSTI2025

Graph-based design of irregular metamaterials

In the field of metamaterial research, random structures offer a novel and less conventional approach compared to traditional periodic designs. Designing random metamaterials is challenging when it comes to ensuring intercon- nectivity, which is essential for manufacturability. This study introduces an innovative framework for generating random metamaterials using graph al- gorithms, ensuring connectivity and adaptability across various base shapes, including cylinders, triangles, pyramids, and cubes. By employing graph algorithms, our framework enhances the intuitiveness and efficiency of de- sign representation and manipulation, streamlining the design process. The framework generates families of designs that exhibit a wide range of prop- erty magnitudes that can be adjusted intuitively by modifying the input parameters. The rapid design process allows many designs to be generated, offering the user a multitude of solutions around the target property range. The designs can be effectively implemented in various fields and subjected to diverse analytical studies, including static, dynamic, and eigenfrequency assessments. We illustrate computational results for two key properties (stiff- ness and acoustic impedance), showcasing the method’s effectiveness through examples ranging from rod-based to cube-based designs. Here, the framework not only advances metamaterial research but also creates new opportunities for innovation in fields requiring customized material properties.

36 MATERIALS SCIENCE↗
DOE OSTI2023

Efficient QAOA Optimization using Directed Restarts and Graph Lookup

Variational Quantum Algorithms (VQA) aim to enhance the capabilities of Noisy Intermediate-Scale Quantum (NISQ) devices. These algorithms utilize parameterized circuits and classical optimizers to iteratively execute circuits with varying parameters. However, VQA faces computational overheads due to repeated iterations and random restarts. Prior work suggests using basic sub-graphs to transfer parameters for the input graph, reducing optimizer overheads but limiting applicability to structured regular graphs. In real-world applications, random irregular graphs are common, and existing methods are not scalable or practical for such graphs. This paper presents a framework that aims to improve random irregular graphs in VQA. The framework uses graph similarity and important features like total edge counts, average edge counts, and variance. It follows an iterative process to choose basis sub-graphs from a small database and adjust parameters accordingly. Classical optimizers then utilize these parameters to determine when to restart and perform gradient descent. This approach increases the chances of reaching global maximum points.

Wang, Meng↗
DOE OSTI2023

Degree-preserving graph dynamics: a versatile process to construct random networks

Real-world networks evolve over time via the addition or removal of vertices and edges. In current network evolution models, vertex degree varies or grows arbitrarily. A recently introduced degree-preserving network growth (DPG) family of models preserves vertex degree, resulting in structures significantly different from and more diverse than previous models. Despite its degree preserving property, the DPG model is able to replicate the output of several well-known real-world network growth models. Simulations showed that many real-world networks can also be constructed from small seed graphs via the DPG process. Here, we start the development of a rigorous mathematical theory underlying the DPG family of network growth models. We prove that the degree sequence of the output of some of the well-known, real-world network growth models can be reconstructed via the DPG process, using proper parametrization. We also show that the general problem of deciding whether a simple graph can be obtained via the DPG process from a small seed (DPG feasibility) is, however, NP-complete. In conclusion, it is an intriguing open problem to uncover whether there is a structural reason behind the DPG-constructability of real-world networks.

97 MATHEMATICS AND COMPUTING↗
DOE OSTI2024

Graph neural networks for CO 2 solubility predictions in Deep Eutectic Solvents

Deep Eutectic Solvents (DESs) are a promising class of solvents for CO 2 capture. DESs are complex mixtures that can be designed to optimize CO solubility and overall capture process efficiency. However, the vast design landscape of DES mixtures makes experimental investigation prohibitive; as such, there is a need for computational models that can quickly and efficiently navigate the design space and inform data collection efforts. In this work, we propose Graph Neural Network (GNN) models for predicting CO 2 solubility for DESs; the GNN leverages a mixture graph representation that captures the molecular structure of the DES components as well as their intermolecular interactions. Here, we compare the GNN framework against alternative architectures (neural networks, graph convolution networks, and random forests) and data representations (molecular fingerprints, sigma profiles, and graphs). We show that the proposed approach offers superior predictive performance; specifically, we show that solubility can be predicted reliably directly from molecular structure (without the need of using sigma profiles as proposed in previous studies). This result is important, as obtaining sigma profiles requires expensive density functional theory computations. We also explored the ability of GNNs to predict solubility for new DES mixtures and operating conditions. We found that the model extrapolates across temperature reliably. However, we also found deficiencies in the ability of the model to predict solubility for DES mixtures, pressures, and molar ratio not included in the training sets; we show that this is due to an inherent lack of chemical diversity in datasets available in the literature. The proposed computational capabilities can thus help navigate the design space of DES and inform data collection efforts. Our models, data, and benchmarks are shared as Python code implemented in Jupyter notebooks.

37 INORGANIC, ORGANIC, PHYSICAL, AND ANALYTICAL CH↗