Engineering Papers⌕ Search

SEARCH · Engineering Papers

Results for “Graph”

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 1,117 records · Page 62
All sourcesNASA NTRSDOE OSTI
DOE OSTI2022

Matching Complexes of Trees and Applications of the Matching Tree Algorithm

A matching complex of a simple graph G is a simplicial complex with faces given by the matchings of G. The topology of matching complexes is mysterious; there are few graphs for which the homotopy type is known. Marietti and Testa showed that matching complexes of forests are contractible or homotopy equivalent to a wedge of spheres. We study two specific families of trees. For caterpillar graphs, we give explicit formulas for the number of spheres in each dimension and for perfect binary trees we find a strict connectivity bound. We also use a tool from discrete Morse theory called the Matching Tree Algorithm to study the connectivity of honeycomb graphs, partially answering a question raised by Jonsson.

97 MATHEMATICS AND COMPUTING↗
DOE OSTI2024

Unifying Combinatorial and Graphical Methods in Artificial Intelligence

Recently, a new graph Laplacian, called the inner product Laplacian, was introduced which generalizes many existing Laplacians, including the normalized and combinatorial Laplacian and their weighted variants. The key observation behind the inner product Laplacian is that by defining appropriate inner product spaces on the vertices and edges, the standard Laplacians can be recovered as Hodge Laplacians over the simplicial complex formed by the edges and vertices. These inner product spaces form a natural way to incorporate non-combinatorial information into the definition of a domain-specific Laplacian. In particular, in contrast to current domain-specific weighting schemes which rely solely on edge weights, information regarding the similarity of non-adjacent vertices and arbitrary pairs of edges can be effectively incorporated into the Laplacian. In order to illustrate this approach we consider the problem of calculating the potential energy of an atomistic configuration using Graph Neural Networks. In comparison with start-of-the-art approaches, such as SchNet, our approach replaces a learned (via auto-encoder) representation of the atom types with an inner product space on atoms based on scientific knowledge (e.g., electronegativity). We will illustrate how this approach captures key chemical properties of the molecules and compare the energy calculations with state-of-the-art neural network approaches. However, to compute the resulting Laplacian involves a mixture of sparse and dense matrix computation and yields a dense matrix as the basis for the graph convolution. This dense convolutional kernel necessitates moving away from the standard message passing framework for graph neural networks and increases the computational cost of applying the kernel. In order to mitigate these costs we investigate means of leveraging the mixed sparse and dense computations to reduce the overall computational cost and how these approaches can be automatically transferred to energy efficient hardware (e.g., field programmable gate arrays (FPGAs)).

97 MATHEMATICS AND COMPUTING↗
DOE OSTI2022

ITeM: Independent temporal motifs to summarize and compare temporal networks

We report networks are a fundamental and flexible way of representing various complex systems. Many domains such as communication, citation, procurement, biology, social media, and transportation can be modeled as a set of entities and their relationships. Temporal networks are a specialization of general networks where every relationship occurs at a discrete time. The temporal evolution of such networks is as important to understand as the structure of the entities and relationships. We present the Independent Temporal Motif (ITeM) to characterize temporal graphs from different domains. ITeMs can be used to model the structure and the evolution of the graph. In contrast to existing work, ITeMs are edge-disjoint directed motifs that measure the temporal evolution of ordered edges within the motif. For a given temporal graph, we produce a feature vector of ITeM frequencies and the time it takes to form the ITeM instances. We apply this distribution to measure the similarity of temporal graphs. We show that ITeM has higher accuracy than other motif frequency-based approaches. We define various ITeM-based metrics that reveal salient properties of a temporal network. We also present importance sampling as a method to efficiently estimate the ITeM counts. We present a distributed implementation of the ITeM discovery algorithm using Apache Spark and GraphFrame. We evaluate our approach on both synthetic and real temporal networks.

97 MATHEMATICS AND COMPUTING↗
DOE OSTI2022

Efficient Topology Assessment for Integrated Transmission and Distribution Network with 10,000+ Inverter-based Resources

The renewable energy proliferation calls upon the grid operators and planners to systematically evaluate the potential impacts of distributed energy resources (DERs). Considering the significant differences between various inverter-based resources (IBRs), especially the different capabilities between grid-forming inverters and grid-following inverters, it is crucial to develop an efficient and effective assessment procedure besides available co-simulation framework with high computation burdens. This paper presents a streamlined graph-based topology assessment for the integrated power system transmission and distribution networks. Graph analyses were performed based on the integrated graph of modified miniWECC grid model and IEEE 8500-node test feeder model, high performance computing platform with 40 nodes and total 2400 CPUs has been utilized to process this integrated graph, which has 100,000+ nodes and 10,000+ IBRs. The node ranking results not only verified the applicability of the proposed method, but also revealed the potential of distributed grid forming (GFM) and grid following (GFL) inverters interacting with the centralized power plants.

Graph Analysis, Topology evaluation, Infrastructur↗
DOE OSTI2021

Trust: Triangle Counting Reloaded on GPUs

Triangle counting is a building block for a wide range of graph applications. Here, traditional wisdom suggests that i) hashing is not suitable for triangle counting, ii) edge-centric triangle counting beats vertex-centric design, and iii) communication-free and workload balanced graph partitioning is a grand challenge for triangle counting. On the contrary, we advocate that i) hashing can help the key operations for scalable triangle counting on Graphics Processing Units (GPUs), i.e., list intersection and graph partitioning, ii) vertex-centric option reduces both hash table construction cost and memory consumption, which is limited on GPUs. In addition, iii) we exploit graph and workload collaborative, and hash-based 2D partitioning to scale vertex-centric triangle counting over 1,000 GPUs with sustained scalability. In this work, we present TRUST, which performs triangle counting with the hash operation and vertex-centric paradigm. To the best of our knowledge, TRUST is the first work that achieves over one trillion Traversed Edges Per Second (TEPS) rate for triangle counting.

97 MATHEMATICS AND COMPUTING↗
DOE OSTI2022

A Block-Based Triangle Counting Algorithm on Heterogeneous Environments

Triangle counting is a fundamental building block in graph algorithms. In this article, we propose a block-based triangle counting algorithm to reduce data movement during both sequential and parallel execution. Our block-based formulation makes the algorithm naturally suitable for heterogeneous architectures. The problem of partitioning the adjacency matrix of a graph is well-studied. Our task decomposition goes one step further: it partitions the set of triangles in the graph. By streaming these small tasks to compute resources, we can solve problems that do not fit on a device. We demonstrate the effectiveness of our approach by providing an implementation on a compute node with multiple sockets, cores and GPUs. The current state-of-the-art in triangle enumeration processes the Friendster graph in 2.1 seconds, not including data copy time between CPU and GPU. Using that metric, our approach is 20 percent faster. When copy times are included, our algorithm takes 3.2 seconds. This is 5.6 times faster than the fastest published CPU-only time.

97 MATHEMATICS AND COMPUTING↗
DOE OSTI2025

G-Mapper: Learning a Cover in the Mapper Construction

The Mapper algorithm is a visualization technique in topological data analysis (TDA) that outputs a graph reflecting the structure of a given dataset. However, the Mapper algorithm requires tuning several parameters in order to generate a “nice” Mapper graph. This paper focuses on selecting the cover parameter. We present an algorithm that optimizes the cover of a Mapper graph by splitting a cover repeatedly according to a statistical test for normality. Our algorithm is based on G-means clustering, which searches for the optimal number of clusters in 𝑘-means by iteratively applying the Anderson–Darling test. Our splitting procedure employs a Gaussian mixture model to carefully choose the cover according to the distribution of the given data. In conclusion, experiments for synthetic and real-world datasets demonstrate that our algorithm generates covers so that the Mapper graphs retain the essence of the datasets, while also running significantly faster than a previous iterative method.

G-means clustering↗
DOE OSTI2021

Directional Laplacian Centrality for Cyber Situational Awareness

Cyber operations is drowning in diverse, high-volume, multi-source data. To get a full picture of current operations and identify malicious events and actors, analysts must see through data generated by a mix of human activity and benign automated processes. Although many monitoring and alert systems exist, they typically use signature-based detection methods. We introduce a general method rooted in spectral graph theory to discover patterns and anomalies without a priori knowledge of signatures. We derive and propose a new graph-theoretic centrality measure based on the derivative of the graph Laplacian matrix in the direction of a vertex. To build intuition about our measure, we show how it identifies the most central vertices in standard network datasets and compare to other graph centrality measures. Finally, we focus our attention on studying its effectiveness in identifying important IP addresses in network flow data. Using both real and synthetic network flow data, we conduct several experiments to test our measure’s sensitivity to two types of injected attack profiles and show that vertices participating in injected attack profiles exhibit noticeable changes in our centrality measures, even when the injected anomalies are relatively small, and in the presence of simulated network dynamics.

45 MILITARY TECHNOLOGY, WEAPONRY, AND NATIONAL DEF↗
DOE OSTI2020

A Block-Based Triangle Counting Algorithm on Heterogeneous Environments

Triangle counting is a fundamental building block in graph algorithms. In this paper, we propose a block-based triangle counting algorithm to reduce data movement during both sequential and parallel execution. Our block-based formulation makes the algorithm naturally suitable for heterogeneous architectures. The problem of partitioning the adjacency matrix of a graph is well-studied. Our task decomposition goes one step further: it partitions the set of triangles in the graph. By streaming these small tasks to compute resources, we can solve problems that do not fit on a device. We demonstrate the effectiveness of our approach by providing an implementation on a compute node with multiple sockets, cores and GPUs. The current state-of-the-art in triangle enumeration processes the Friendster graph in 2.1 seconds, not including data copy time between CPU and GPU. Using that metric, our approach is 20 percent faster. When copy times are included, our algorithm takes 3.2 seconds. This is 5.6 times faster than the fastest published CPU-only time.

97 MATHEMATICS AND COMPUTING↗
NASA NTRSDate not supplied

Cooperative Clustering Techniques For Space Network Scalability

Routing in the space internet must face many unique challenges - from unplanned disconnections and interruptions to predictable intermittent connectivity due to high network mobility and long propagation delays. NASA’s current approach to such routing is Contact Graph Routing (CGR), using a graph formed of prescheduled communication contacts to compute routes through the network. While this approach manages to tackle issues of connectivity and propagation delays, it is a global approach that requires continuous knowledge of the entire network. In a potential future Solar Space Internet (SSI) such an approach on its own cannot scale to large networks with thousands of members. In this paper we propose clustering as a solution to CGR scalability. Clustering has been used in many networking problems as a way to subdivide the network and allow for localized routing and better scalability. Using techniques from graph theory and game theory, we explore various existing clustering algorithms and adapt them to the Contact Graph Routing setting. We propose a way to combine multiple algorithms to create a Delay Tolerant Clustering Protocol (DTCP). In addition, we explore the underlying networking mechanisms such as multicast, neighbor discovery, and software defined networking that may be used to enable DTCP.

Delay Tolerant Networking↗
NASA NTRSDate not supplied

Human Systems Risk Network - A Ranking Analysis of Risks

INTRODUCTION The Human Systems Risk Board (HSRB) is responsible for understanding, managing, and mitigating the risks associated with spaceflight. For a particular mission, the HSRB assigns each human system risk a rating on a 5x5 grid assessing its likelihood and consequence, which is ultimately used to compare and rank the risks. The HSRB approaches risk management by primarily establishing the context of each human system risk individually with the understanding that mitigating one risk might affect the likelihood, consequence, and mitigation approaches of another. To support this effort the HSRB, subject matter experts, and risk custodian teams created directed acyclic graphs (DAG), often called a causal graph, for the twenty-nine risks. In this presentation, we propose a new ranking algorithm for the risks which includes the downstream influence of each risk according to the information in the DAGs and provide an application of graph theoretic tools. METHODS In 2014, Mindock and Klaus proposed a taxonomy for human system risk influences which we have adopted to categorize the nodes in each DAG. Analyzing the nodes that correspond to the risks in this taxonomy allows us to analyze and understand how each risk influences the others. We construct an auxiliary network, which we call the Primary Risk Network (PRN), where the nodes are the twenty-nine space flight risks and, a directed edge connects Risk A to Risk B if Risk A has some influence on the likelihood or consequence of Risk B as described in the DAGS. We perform a variety of graph theoretic ranking methods on the nodes (or risks) in the PRN, including Katz centrality. RESULTS We rank the nodes in the PRN using the Katz centrality score. The ten risks with the highest score are pictured in Figure 1, colored (light to dark) according to their score. We analyze other centrality measures like betweenness centrality, eigenvector centrality, and the Estrada index, and provide the meaning of the corresponding rankings in terms of the risks. Future work includes analyzing the other categories in the taxonomy defined by Mindock and Klaus [1]. For example, we are interested in analyzing the nodes that are labeled as countermeasures or capabilities and perform similar analysis to measure their effect on certain medical conditions.

dag↗
DOE OSTI2025

System Engineers and Decisions: It?s All about Knowledge

In order to guarantee that a system meets adequate levels of reliability and availability, system performances are continuously monitored and analyzed thanks to the technological advancements driving the Industry 4.0 revolution. An Industry 4.0 approach is typically based on advanced statistical, big data mining, machine learning, and internet-of-things methods designed to detect anomalies in the behavior of system, detect the most likely failure modes, and provide indications to system engineers on when maintenance activities should be performed before system performance are deemed unacceptable (which can be generated by diagnostic and prognostic methods). However, these analyses, which are designed to automatize and increase the efficacy of the system maintenance program, require large amount of data which can come in various forms: numeric, textual, images, sounds etc. Such data constitutes the historic knowledge benchmark to track system performances and support system engineer decisions. Here we claim that data is not sufficient to support this kind of analyses when applied to systems characterized by complex architectures and behaviors. Robust system engineer decisions require the ability to understand the system operational context that lies behind the observed data elements. In this respect, system models are in fact necessary to “put data in context” and capture relationships between data elements. Industry 4.0 methods require in fact contextual knowledge as a basis upon which hypotheses can be generated and assumptions tested. In our view, for complex systems, model-based system engineering (MBSE) models can afford this contextual knowledge, as they are typically used to describe systems architecture and dynamic behaviors. System knowledge is here intended as the blending of collected data and system architecture which takes the form of a “knowledge graph”. A knowledge graph is a database which consists of a large set of nodes (in our case an entity can be either a data or an MBSE element) which are linked to each other. The types of nodes and links follow a pre-defined topology, sometimes also refers as an ontology, that is designed to fit the actual decisions that needs to be performed. We show here how a knowledge graph can be defined to support system engineer maintenance decisions and how the same graph can be built based on system MBSE models and pre-processed data from numeric (through anomaly detections and diagnostic methods) and textual elements (through technical language processing TLP).

97 - MATHEMATICS AND COMPUTING↗
DOE OSTI2024

Landau singularities of the 7-point ziggurat. Part II

We solve the Landau equations to find the singularities of nine three-loop 7-point graphs that arise as relaxations of the graph studied in [22]. Along the way we establish that Y – Δ equivalence fails for certain branches of solutions to the Landau equations. We find two graphs with singularities outside the heptagon symbol alphabet; in particular they are not cluster variables of Gr(4, 7). We compare maximal residues of scalar graphs exhibiting these singularities to those in $\mathcal{N}$ = 4 super-Yang-Mills theory in order to probe their cancellation from its amplitudes.

72 PHYSICS OF ELEMENTARY PARTICLES AND FIELDS↗
DOE OSTI2026

Exploring the holographic entropy cone via reinforcement learning

We develop a reinforcement learning algorithm to study the holographic entropy cone. Given a target entropy vector, our algorithm searches for a graph realization whose min-cut entropies match the target vector. If the target vector does not admit such a graph realization, it must lie outside the cone, in which case the algorithm finds a graph whose corresponding entropy vector most nearly approximates the target and allows us to probe the location of the facets. For the N = 3 cone, we confirm that our algorithm successfully rediscovers monogamy of mutual information beginning with a target vector outside the holographic entropy cone. We then apply the algorithm to the N = 6 cone, analyzing the 6 mystery extreme rays of the subadditivity cone from [1] that satisfy all known holographic entropy inequalities yet lacked graph realizations. We found realizations for 3 of them, proving they are genuine extreme rays of the holographic entropy cone, while providing evidence that the remaining 3 are not realizable, implying unknown holographic inequalities exist for N = 6.

AdS-CFT correspondence↗
DOE OSTI2025

Differential equations for cosmological correlators

Cosmological fluctuations retain a memory of the physics that generated them in their spatial correlations. The strength of correlations varies smoothly as a function of external kinematics, which is encoded in differential equations satisfied by cosmological correlation functions. In this work, we provide a broader perspective on the origin and structure of these differential equations. As a concrete example, we study conformally coupled scalar fields in a power-law cosmology. The wavefunction coefficients in this model have integral representations, with the integrands being the product of the corresponding flat-space results and “twist factors” that depend on the cosmological evolution. Similar twisted integrals arise for loop amplitudes in dimensional regularization, and their recent study has led to the discovery of rich mathematical structures and powerful new tools for computing multi-loop Feynman integrals in quantum field theory. The integrals of interest in cosmology are also part of a finite-dimensional basis of master integrals, which satisfy a system of first-order differential equations. We develop a formalism to derive these differential equations for arbitrary tree graphs. The results can be represented in graphical form by associating the singularities of the differential equations with a set of graph tubings. Upon differentiation, these tubings grow in a local and predictive fashion. In fact, a few remarkably simple rules allow us to predict — by hand — the equations for all tree graphs. While the rules of this “kinematic flow” are defined purely in terms of data on the boundary of the spacetime, they reflect the physics of bulk time evolution. We also study the analogous structures in tr ϕ 3 theory, and see some glimpses of hidden structure in the sum over planar graphs. This suggests that there is an autonomous combinatorial or geometric construction from which cosmological correlations, and the associated spacetime, emerge.

Cosmological models↗
DOE OSTI2023

The sequence of prime gaps is graphic

Let us call a simple graph on $n$ ≥ 2 vertices a prime gap graph if its vertex degrees are 1 and the first $n$ - 1 prime gaps. We show that such a graph exists for every large n, and in fact for every $n$ ≥ 2 if we assume the Riemann hypothesis. Moreover, an infinite sequence of prime gap graphs can be generated by the so-called degree preserving growth process. This is the first time a naturally occurring infinite sequence of positive integers is identified as graphic. That is, we show the existence of an interesting, and so far unique, infinite combinatorial object.

97 MATHEMATICS AND COMPUTING↗
DOE OSTI2021

Empirical performance bounds for quantum approximate optimization

The quantum approximate optimization algorithm (QAOA) has been put forth as a method for near-term quantum computers to solve optimization problems. However, assessments of QAOA performance have mostly focused on small structured problem instances while performance on more general instances is less clear. Here, we numerically simulate QAOA pure state dynamics for every instance of MaxCut on non-isomorphic unweighted graphs with nine or fewer vertices with depth parameters p ≤ 3. We find the approximation ratios and optimized circuit parameters concentrate across graphs of a given size and empirically show increases in concentration as graph size increases. The parameter concentration leads to two median-angle heuristics that overcome difficulties in QAOA parameter optimization and obtain mean approximation ratios within 3% and 0.2% of the optimal. We also analyze the probability to measure an optimal solution and find increasing variations between graphs as depth increases, in stark contrast to the approximation ratios which concentrate as depth increases. Furthermore, the resulting benchmark data set gives empirical bounds for on-going experimental realizations and lays groundwork for theoretical extensions to greater problem sizes and depths where QAOA may prove important for practically relevant problems.

79 ASTRONOMY AND ASTROPHYSICS↗
DOE OSTI2021

An automated procedure built on MTEX for reconstructing deformation twin hierarchies from electron backscattered diffraction datasets of heavily twinned microstructures

Here we present a set of algorithms built on the MTEX and MATLAB graph toolboxes for automatic reconstruction of deformation twin hierarchies from Electron Backscatter Diffraction (EBSD) datasets with a focus on developing methods for heavily twinned microstructures (twin fractions >0.5). The algorithms address key issues arising at large strains, mainly: missing twin relationships, grouping of heavily deformed grain fragments into families of similar orientation originating from a single initial grain, identification of parent fragments for large twin volume fractions, and classification of families having twin relationships with multiple families. To facilitate the development of these algorithms, large-grained ultra-high purity α-Ti deformed in compression along two directions is investigated. Graphs are utilized to handle non-local geometric merging and to represent relationships throughout the reconstruction process. When determining if a grain fragment is from the undeformed microstructure, the combined metrics of the fragment's orientation volume fraction in the initial texture and the directed graph centrality measure of out-closeness (the number of nodes reached in a graph from a given node) are essential. To address automation in reconstructing the sequence of twinning and relating fragments originating from a single grain in the initial microstructure, the twin family tree is formulated as a minimum spanning tree emanating from the initial grain family. A scheme constructing the distances associated with twin relationship comprising the spanning tree is developed, and a novel quasi-directional Prim spanning tree algorithm is used to determine the twin family tree. The procedure is demonstrated to significantly improve the level of automation in reconstructing twin hierarchies in heavily twinned microstructure compared to other methodologies in literature. The procedure can readily be applied to analyses of twinning in metals, as well as provide an approach for routinely extracting twin statistics at larger deformation levels than previously possible. Significantly, the procedure is demonstrated to be capable of identifying third generation twinning in α-Ti microstructures.

36 MATERIALS SCIENCE↗