Search NASA⌕ Search

SEARCH · Search NASA

Results for “graph theory”

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 19 records
All sourcesNASA NTRSDOE OSTI
DOE OSTI2024

Modern chemical graph theory

Abstract Graph theory has a long history in chemistry. Yet as the breadth and variety of chemical data is rapidly changing, so too do graph encoding methods and analyses that yield qualitative and quantitative insights. Using illustrative cases within a basic mathematical framework, we showcase modern chemical graph theory's utility in Chemists' analysis and model development toolkit. The encoding of both experimental and simulation data is discussed at various levels of granularity of information. This is followed by a discussion of the two major classes of graph theoretical analyses: identifying connectivity patterns and partitioning methods. Measures, metrics, descriptors, and topological indices are then introduced with an emphasis upon enhancing interpretability and incorporation into physical models. Challenging data cases are described that include strategies for studying time dependence. Throughout, we incorporate recent advancements in computer science and applied mathematics that are propelling chemical graph theory into new domains of chemical study. This article is categorized under: Molecular and Statistical Mechanics > Molecular Dynamics and Monte‐Carlo Methods Structure and Mechanism > Computational Materials Science Structure and Mechanism > Molecular Structures

Leite, Leonardo S. G.↗
DOE OSTI2019

Deformation pathway and defect generation in crystals: a combined group theory and graph theory description

The generation and motion of crystalline defects during plastic deformation are critical processes that determine the mechanical properties of a crystal. The types of defect generated are not only related to the symmetry of a crystal but also associated with the symmetry-breaking process during deformation. Proposed here is a new mathematical framework to capture the intrinsic coupling between crystal symmetry and deformation-induced symmetry breaking. Using a combination of group theory and graph theory, a general approach is demonstrated for the systematic determination of the types of crystalline defect induced by plastic deformation, through the construction of a crystal deformation group and a deformation pathway graph. The types of defect generated in the deformation of a face-centered cubic crystal are analyzed through the deformation pathway graph and compared with experimental observations.

36 MATERIALS SCIENCE↗
DOE OSTI2022

Thermal modeling of directed energy deposition additive manufacturing using graph theory

Purpose: The purpose of this paper is to develop, apply and validate a mesh-free graph theory–based approach for rapid thermal modeling of the directed energy deposition (DED) additive manufacturing (AM) process. Design/methodology/approach: Here, the authors develop a novel mesh-free graph theory–based approach to predict the thermal history of the DED process. Subsequently, the authors validated the graph theory predicted temperature trends using experimental temperature data for DED of titanium alloy parts (Ti-6Al-4V). Temperature trends were tracked by embedding thermocouples in the substrate. The DED process was simulated using the graph theory approach, and the thermal history predictions were validated based on the data from the thermocouples. Findings: The temperature trends predicted by the graph theory approach have mean absolute percentage error of approximately 11% and root mean square error of 23°C when compared to the experimental data. Moreover, the graph theory simulation was obtained within 4 min using desktop computing resources, which is less than the build time of 25 min. By comparison, a finite element–based model required 136 min to converge to similar level of error. Research limitations/implications: This study uses data from fixed thermocouples when printing thin-wall DED parts. In the future, the authors will incorporate infrared thermal camera data from large parts. Practical implications: The DED process is particularly valuable for near-net shape manufacturing, repair and remanufacturing applications. However, DED parts are often afflicted with flaws, such as cracking and distortion. In DED, flaw formation is largely governed by the intensity and spatial distribution of heat in the part during the process, often referred to as the thermal history. Accordingly, fast and accurate thermal models to predict the thermal history are necessary to understand and preclude flaw formation. Originality/value: This paper presents a new mesh-free computational thermal modeling approach based on graph theory (network science) and applies it to DED. The approach eschews the tedious and computationally demanding meshing aspect of finite element modeling and allows rapid simulation of the thermal history in additive manufacturing. Although the graph theory has been applied to thermal modeling of laser powder bed fusion (LPBF), there are distinct phenomenological differences between DED and LPBF that necessitate substantial modifications to the graph theory approach.

42 ENGINEERING↗
DOE OSTI2020

A Guide to Conquer the Biological Network Era Using Graph Theory

Networks are one of the most common ways to represent biological systems as complex sets of binary interactions or relations between different bioentities. In this article, we discuss the basic graph theory concepts and the various graph types, as well as the available data structures for storing and reading graphs. In addition, we describe several network properties and we highlight some of the widely used network topological features. We briefly mention the network patterns, motifs and models, and we further comment on the types of biological and biomedical networks along with their corresponding computer- and human-readable file formats. Finally, we discuss a variety of algorithms and metrics for network analyses regarding graph drawing, clustering, visualization, link prediction, perturbation, and network alignment as well as the current state-of-the-art tools. We expect this review to reach a very broad spectrum of readers varying from experts to beginners while encouraging them to enhance the field further.

59 BASIC BIOLOGICAL SCIENCES↗
DOE OSTI2021

Understanding Discrete Fracture Networks Through Spectral Graph Theory

Discrete Fracture Network models (DFNs) are used to simulate fluid flow and particle transport through fracture networks in low permeability rock. Understanding these processes are essential in many subsurface applications, such as environmental restoration of contaminated fractured media, CO 2 sequestration, detection of low-level nuclear tests, and hydrocarbon extraction. Compared with other models, DFNs allow for incorporation of a wider range of network characteristics but have substantially greater computation cost. These networks can be represented with graphs, allowing the use of graph theory tools to study the networks. I used Python to simulate flow and transport on a range of DFNs and analyzed these networks using methods from network analysis and spectral graph theory. My purpose was to find ways to gain insight about flow and transport on DFNs using these graph representations, bypassing the computationally intensive meshing typically required. My work is still in progress, but I have discovered several interesting trends and patterns that I believe could be useful towards my goal. If I am able to bring these results to fruition, they will aid subsurface geologists in extracting flow and transport information about fracture networks more efficiently.

54 ENVIRONMENTAL SCIENCES↗
DOE OSTI2026

Microstructure Validation of Graph Theory Model-Derived Cooling Rates in the Wire Arc Additive Manufacturing of ER70S-6 Steel

Wire arc additive manufacturing (WAAM) enables high-rate fabrication of large metallic components, but spatial variations in thermal history can lead to microstructural heterogeneity that requires efficient process models to evaluate. This study evaluates whether cooling rates extracted from a graph theory model (GTM)-based thermal simulation are consistent with the microstructural evolution observed in an ER70S-6 WAAM wall. Thermal histories from the model were analyzed at selected build heights, and cooling rates were extracted from the final thermal excursion through the austenite phase field. Microstructures at corresponding locations were characterized using electron backscatter diffraction (EBSD) to quantify grain size distributions, and pearlite interlamellar spacing was used as an additional indicator of cooling behavior. The modeled cooling rates were highest near the substrate and generally decreased with build height, consistent with the observed reduction in the fine grain fraction and the progressive shift in the grain size distribution as build height increased. Pearlite spacing trends also supported the modeled cooling rate variation. These results indicate that GTM-derived thermal histories can be post-processed into metallurgically meaningful cooling rate estimates for WAAM steel builds and linked to dataset specific empirical grain size distribution relationships for process–thermal history–microstructure assessment.

36 MATERIALS SCIENCE↗
DOE OSTI2026

Navigating Large Chemical Spaces Using Graph Theory and Integer Programming

Navigating and analyzing large chemical spaces are necessary to accelerate the design and discovery of new molecules and chemical processes. In this work, we introduce a computational framework that integrates graph theory and integer programming to enable the efficient navigation of large chemical spaces. Our framework represents the chemical space as a graph, wherein nodes represent molecules and edges represent the degree of similarity or connectivity based on domain-specific information. Using the graph representation, we identify representative molecules by computing the so-called minimum dominating set (MDS), which in our context is the minimum set of molecules that is connected to all other molecules. We present a suite of solution strategies for the MDS problem including heuristic and rigorous integer programming (IP) approaches. We show that these approaches allow us to capture physicochemical properties and domain-specific logic and constraints, facilitating the identification of molecules with the target properties. We demonstrate the effectiveness of the proposed approach by navigating the chemical space of per- and polyfluoroalkyl substances (PFAS); this comprises approximately 15,000 molecular structures. We compare our framework against traditional dimensionality reduction and clustering methods such as t-SNE and K-means clustering.

Chemical structure↗
DOE OSTI2020

Graph theory approach to determine configurations of multidentate and high coverage adsorbates for heterogeneous catalysis

Abstract Heterogeneous catalysts constitute a crucial component of many industrial processes, and to gain an understanding of the atomic-scale features of such catalysts, ab initio density functional theory is widely employed. Recently, growing computational power has permitted the extension of such studies to complex reaction networks involving either high adsorbate coverages or multidentate adsorbates, which bind to the surface through multiple atoms. Describing all possible adsorbate configurations for such systems, however, is often not possible based on chemical intuition alone. To systematically treat such complexities, we present a generalized Python-based graph theory approach to convert atomic scale models into undirected graph representations. These representations, when combined with workflows such as evolutionary algorithms, can systematically generate high coverage adsorbate models and classify unique minimum energy multidentate adsorbate configurations for surfaces of low symmetry, including multi-elemental alloy surfaces, steps, and kinks. Two case studies are presented which demonstrate these capabilities; first, an analysis of a coverage-dependent phase diagram of absorbate NO on the Pt 3 Sn(111) terrace surface, and second, an investigation of adsorption energies, together with identifying unique minimum energy configurations, for the reaction intermediate propyne (CHCCH 3 *) adsorbed on a PdIn(021) step surface. The evolutionary algorithm approach reproduces high coverage configurations of NO on Pt 3 Sn(111) using only 15% of the number of simulations required for a brute force approach. Furthermore, the screening of potentially hundreds of multidentate adsorbates is shown to be possible without human intervention. The strategy presented is quite general and can be applied to a spectrum of complex atomic systems.

36 MATERIALS SCIENCE↗
DOE OSTI2019

Earthquake Arrival Association with Backprojection and Graph Theory

The association of seismic-wave arrivals with causative earthquakes becomes progressively more challenging as arrival detection methods become more sensitive, and particularly when earthquake rates are high. For instance, seismic waves arriving across a monitoring network from several sources may overlap in time, false arrivals may be detected, and some arrivals may be of unknown phase (e.g., P or S waves). We propose an automated method to associate arrivals with earthquake sources and obtain source locations applicable to such situations. To do so, we use a pattern detection metric based on the principle of back-projection to reveal candidate sources followed by graph-theory-based clustering and an integer linear optimization routine to associate arrivals with the minimum number of sources necessary to explain the data. We find that this method solves for all sources and phase assignments simultaneously, rather than in a sequential greedy procedure as is common in other association routines. We demonstrate our method on both synthetic and real data from the Integrated Plate Boundary Observatory Chile seismic network of northern Chile. For the synthetic tests, we report results for cases with varying complexity, including rates of 500 earthquakes/day and 500 false arrivals/station/day, for which we measure true positive detection accuracy of >95%. For the real data, we develop a new catalog between 1 January 2010 and 31 December 2017 containing 817,548 earthquakes, with detection rates on average 279 earthquakes/day and a magnitude-of-completion of M~1.8. A subset of detections are identified as sources related to quarry and industrial site activity, and we also detect thousands of foreshocks and aftershocks of the 1 April 2014 Mw 8.2 Iquique earthquake. During the highest rate of aftershock activity, >600 earthquakes/day are detected in the vicinity of the Iquique earthquake rupture zone.

58 GEOSCIENCES↗
DOE OSTI2023

Exploring NaCl-PuCl 3 molten salts with machine learning interatomic potentials and graph theory

Actinide molten salts are the basis of the liquid fuels used in molten salt reactors. Due to the inherent difficulties associated with high temperature and hazardous conditions, experimental investigations of fundamental properties of these materials are usually challenging. In this work, we describe the structure and transport of NaCl-PuCl 3 mixtures using computational techniques. Three compositions were considered (16, 25, and 36 mol% PuCl 3 ) over a temperature range (730 – 1257K) using ab initio molecular dynamics, which provided the necessary data sets for training machine learned interatomic potentials. Further, molecular dynamics simulations based on these potentials were then used to determine structure and transport properties. A substantial change was noted in the structure factor when increasing the PuCl 3 content from 25 to 36 mol%. This change is linked to the aggregation of larger Pu 3+ clusters. In addition, the similarity of the atomic environments of metal cations in molten salt systems to their solid states counterparts was investigated using an unsupervised learning technique. Finally, graph theory was employed to explore the structure and size of actinide networks. Consistent with the structure factor, a dense Pu 3+ intermolecular structure is observed within the 36 mol% PuCl 3 mixture. The structure of cation-cation inter-junctions is also discussed. In all cases, the diffusion of Pu 3+ is significantly lower than that of Na + and Cl - .

36 MATERIALS SCIENCE↗
DOE OSTI2020

Graph Theory and IC Component Design Analysis

Graph analysis in large integrated circuit (IC) designs is an essential tool for verifying design logic and timing via dynamic timing analysis (DTA). IC designs resemble graphs with each logic gate as a vertex and the conductive connections between gates as edges. Using DTA digital statistical correlations, graph condensation, and graph partitioning, it is possible to identify high-entropy component centers and paths within an IC design. Identification of high-entropy component centers (HECC) enables focused DTA, effectively lowering the computational complexity of DTA on large integrated circuit graphs. In this paper, a devised methodology termed IC layout subgraph component center identification (CCI) is used to identify described. CCI lowers DTA computationally complexity by condensing IC graphs into reduced subgraphs in which dominant logic functions are verified.

42 ENGINEERING↗
DOE OSTI2022

Quantifying the atomistic free-volume morphology of materials with graph theory

Here, we introduce a new computational methodology for the identification and characterization of free volume within/around atomistic configurations. This scheme employs a three-stage workflow, by which spheres are iteratively grown inside of voxels, and ultimately converted to planar graphs, which are then characterized via a graph-based order parameter. Our approach is computationally efficient, physically intuitive, and universally transferable to any material system. Validation of our methodology is performed on several sets of materials problems: (1) classification of unique free volumes in various crystal phases, (2) autonomous detection and classification of complex surface defects during epitaxial growth simulations, (3) characterization of free volume defects in metals/alloys, and (4) quantification of the spatio-temporal behavior of nano-scale free volume morphologies as a function of both temperature and free-volume size. Our method accurately identifies and characterizes unique free volumes over a multitude of systems and length scales, indicating its potential for future use in understanding the relationship between free volume morphology and material properties under both static and dynamic conditions.

36 MATERIALS SCIENCE↗
DOE OSTI2019

Memristive networks: From graph theory to statistical physics

In this work, we provide an introduction to a very specific toy model of memristive networks, for which an exact differential equation for the internal memory which contains the Kirchhoff laws is known. In particular, we highlight how the circuit topology enters the dynamics via an analysis of directed graph. We try to highlight in particular the connection between the asymptotic states of memristors and the Ising model, and the relation to the dynamics and statics of disordered systems.

71 CLASSICAL AND QUANTUM MECHANICS, GENERAL PHYSIC↗
DOE OSTI2022

Graph theory and nighttime imagery based microgrid design

Reducing the duration and frequency of blackouts in remote communities poses an engineering challenge for grid operators. Outage effects can also be mitigated locally through microgrids. This paper develops a systematic procedure to account for these challenges by creating microgrids prioritizing high value assets within vulnerable communities. Nighttime satellite imagery is used to identify vulnerable communities. Using an asset classification and rating system, multi-asset clusters within these communities are prioritized. Infrastructure data, geographic information systems, satellite imagery, and spectral clustering are used to form and rank microgrid candidates. A microgrid sizing algorithm is included to guide through the microgrid design process. Finally, an application of the methodology is presented using real event, location, and asset data.

24 POWER TRANSMISSION AND DISTRIBUTION↗
DOE OSTI2019

A Graph Theory Method for Identification of a Minimum Breakpoint Set for Directional Relay Coordination

The energy grid becomes more complex with increasing penetration of renewable resources, distributed energy storage, distributed generators, and more diverse loads such as electric vehicle charging stations. The presence of distributed energy resources (DERs) requires directional protection due to the added potential for energy to flow in both directions down the line. Additionally, contingency requirements for critical loads within a microgrid may result in looped or meshed systems. Computation speeds of iterative methods required to coordinate loops are improved by starting with a minimum breakpoint set (MBPS) of relays. A breakpoint set (BPS) is a set of breakers such that, when opened, breaks all loops in a mesh grid creating a radial system. A MBPS is a BPS that consists of the minimum possible number of relays required to accomplish this goal. In this paper, a method is proposed in which a minimum spanning tree is computed to indirectly break all loops in the system, and a set difference is used to identify the MBPS. The proposed method is found to minimize the cardinality of the BPS to achieve a MBPS.

24 POWER TRANSMISSION AND DISTRIBUTION↗
DOE OSTI2019

Graph Theory Approach to High-Throughput Surface Adsorption Structure Generation

We present a methodology for graph based enumeration of surfaces and unique chemical adsorption structures bonded to those surfaces. Utilizing the graph produced from a bulk structure, we create a unique graph representation for any general slab cleave and further extend that representation to include a large variety of catalytically relevant adsorbed molecules. Here, we also demonstrate simple geometric procedures to generate 3D initial guesses of these enumerated structures. While generally useful for generating a wide variety of structures used in computational surface science and heterogeneous catalysis, these techniques are also key to facilitating an informatics approach to the high-throughput search for more effective catalysts.

37 INORGANIC, ORGANIC, PHYSICAL, AND ANALYTICAL CH↗