Engineering Papers⌕ Search

SEARCH · Engineering Papers

Results for “graph mining”

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 109 records · Page 6

Automating Network Node Behavior Characterization by Mining Communication Patterns

Enterprise networks of scale are complex, dynamic computing environments that respond to evolv- ing business objectives and requirements. Characteriz- ing system behaviors in these environments is essential for network management and cyber security operations. Characterization of system’s communication is typical and is supported using network flow information (NetFlow). Related work has characterized behavior using theoretical graph metrics; results are often difficult to interpret by enterprise staff. We propose a different approach, where flow information is mapped to sets of tags that contextualize the data in terms of network principals and enterprise concepts. Frequent patterns are then extracted and are expressed as behaviors. Behaviors can be com- pared, identifying systems expressing similar behaviors. We evaluate the approach using flow information collected by a third party.

cyber system modeling↗

Numerically approximating centrality for graph ranking guarantees

Many real-world datasets can be represented as graphs. Using iterative solvers to approximate graph centrality measures allows us to obtain a ranking vector on the nodes of the graph, consisting of a number for each vertex in the graph identifying its relative importance. In this study the centrality measures we use are Katz Centrality and PageRank. Given an approximate solution, we use the residual to accurately estimate how much of the ranking matches the ranking given by the exact solution. Using probabilistic matrix norms, we obtain bounds on the accuracy of the approximation compared to the exact solution with respect to the highly ranked nodes and apply numerical analysis to the computation of centrality with iterative methods. This relates the numerical accuracy of the linear solver to the data analysis accuracy of finding the correct ranking. In particular, we answer the question of which pairwise rankings are reliable given an approximate solution to the linear system. Experiments on many real-world undirected and directed networks up to several million vertices and several hundred million edges validate our theory and show that we are able to accurately estimate large portions of the approximation. We also analyze the difference between global centrality scores and personalized scores (w.r.t. specific seed vertices). By analyzing convergence error, we develop confidence in the ranking schemes of data mining. We show we are able to accurately guarantee ranking of vertices with an approximation to centrality metrics faster than current methods.

97 MATHEMATICS AND COMPUTING↗

I Can’t Read All That! Improving the Usability of Semantic Models Using Concise, Ontology-Agnostic, Building-Specific Schemas

Semantic ontologies have enabled the creation of formalized, machine-readable descriptions of heterogenous building systems by providing dictionaries of well defined concepts that can be applied to model them. Within a semantic model of a particular building, a subset of an ontology's concepts may be applied in different ways to represent a particular perspective of the building's systems. How the concepts were applied can only be understood by examining the large amount of instance data within a semantic model, which leads to usability challenges. We propose a concise, ontology-agnostic method for defining building-specific schema (b-schema) graphs that summarize the structure and content of a semantic model. This approach provides a queryable and concise representation of the model's contents, separate from the instance data within a model, that can mitigate the challenges posed by the size and complexity of semantic models in processes such as visualization, querying, validation, and the use of large language models (LLMs). We validate our approach on semantic models based on the Brick and ASHRAE S223 ontologies. Results demonstrate that b-schemas significantly reduce the complexity of visual interpretation, accelerate SPARQL queries and SHACL validation, and improve LLM-based knowledge graph question answering.

Paul, Lazlo [Lawrence Berkeley National Laboratory↗

MOFSimplify, machine learning models with extracted stability data of three thousand metal–organic frameworks

Abstract We report a workflow and the output of a natural language processing (NLP)-based procedure to mine the extant metal–organic framework (MOF) literature describing structurally characterized MOFs and their solvent removal and thermal stabilities. We obtain over 2,000 solvent removal stability measures from text mining and 3,000 thermal decomposition temperatures from thermogravimetric analysis data. We assess the validity of our NLP methods and the accuracy of our extracted data by comparing to a hand-labeled subset. Machine learning (ML, i.e. artificial neural network) models trained on this data using graph- and pore-geometry-based representations enable prediction of stability on new MOFs with quantified uncertainty. Our web interface, MOFSimplify, provides users access to our curated data and enables them to harness that data for predictions on new MOFs. MOFSimplify also encourages community feedback on existing data and on ML model predictions for community-based active learning for improved MOF stability models.

37 INORGANIC, ORGANIC, PHYSICAL, AND ANALYTICAL CH↗

COVID19 Disease Map, a computational knowledge repository of virus–host interaction mechanisms

We need to effectively combine the knowledge from surging literature with complex datasets to propose mechanistic models of SARS-CoV-2 infection, improving data interpretation and predicting key targets of intervention. Here, we describe a large-scale community effort to build an open access, interoperable and computable repository of COVID-19 molecular mechanisms. The COVID-19 Disease Map (C19DMap) is a graphical, interactive representation of disease-relevant molecular mechanisms linking many knowledge sources. Notably, it is a computational resource for graph-based analyses and disease modelling. To this end, we established a framework of tools, platforms and guidelines necessary for a multifaceted community of biocurators, domain experts, bioinformaticians and computational biologists. The diagrams of the C19DMap, curated from the literature, are integrated with relevant interaction and text mining databases. We demonstrate the application of network analysis and modelling approaches by concrete examples to highlight new testable hypotheses. This framework helps to find signatures of SARS-CoV-2 predisposition, treatment response or prioritisation of drug candidates. Such an approach may help deal with new waves of COVID-19 or similar pandemics in the long-term perspective.

59 BASIC BIOLOGICAL SCIENCES↗

Exploring the Role of Intrinsic Nodal Activation on the Spread of Influence in Complex Networks

In many complex networked systems such as online social networks, at any given time, activity originates at certain nodes and subsequently spreads on the network through influence. To model the spread of influence in such a scenario, we consider the problem of identification of influential entities in a complex network when nodal activation can happen through two different mechanisms. The first mode of activation is due mechanisms intrinsic to the node. The second mechanism is through the influence of connected neighbors. In this work, we present a simple probabilistic formulation that models such self-evolving systems where information diffusion occurs primarily because of the intrinsic activity of users and the spread of activity occurs due to influence. We provide an algorithm to mine for the influential seeds in such a scenario by modifying the well-known influence maximization framework with the independent cascade diffusion model. We provide small motivating examples to provide an intuitive understanding of the effect of including the intrinsic activation mechanism. We sketch a proof of the submodularity of the influence function under the new formulation and demonstrate the same with larger graphs. We then show by means of additional experiments on a real-world twitter dataset how the formulation can be applied to real-world social media datasets. Finally we derive a computationally efficient centrality metric that takes into account, both the mechanisms of activation and provides for an accurate as well as computationally efficient alternative approach to the problem of identifying influencers under intrinsic activation.

Visweswara Sathanur, Arun↗

Some physiochemical and heavy metal concentration in surface water streams of Tutuka in the Kenyasi mining catchment area

This research was conducted in the Akantansu stream of Tutuka in Kenyasi in the Brong Ahafo Region of Ghana in the months of October and November 2010 and January 2011. The major objectives of the study were to measure levels of pH, BOD (biochemical oxygen demand), lead, chromium, and arsenic in the Akantansu stream of Tutuka and to find ways that the community could ensure safe water use. To achieve the objectives of the study, sampling was done over a period of three months and data was collected and analyzed into graphs and ANOVA tables. The research revealed that the levels of arsenic and BOD were high as compared to the standards of WHO and EPA. If the people of Tutuka continue to use the stream, they may experience negative health effects (e.g., nausea, vomiting, diarrhea, etc.). The level of pH, chromium and lead was acceptable as compared to the standard of WHO and EPA. (authors)

12 MANAGEMENT OF RADIOACTIVE AND NON-RADIOACTIVE W↗

Accelerating the Mining of Influential Nodes in Complex Networks through Community Detection

Computing the set of influential nodes with a given size to ensure maximal spread of influence on a complex network is a challenging problem impacting multiple applications. A rigorous approach to influence maximization involves utilization of optimization routines that comes with a high computational cost. In this work, we propose to exploit the existence of communities in complex networks to accelerate the mining of influential seeds. We provide intuitive reasoning to explain why our approach should be able to provide speedups without significantly degrading the extent of the spread of influence when compared to the case of influence maximization without using the community information. Additionally, we have parallelized the complete workflow by leveraging an existing parallel implementation of the Louvain community detection algorithm. We then conduct a series of experiments on a dataset with three representative graphs to first verify our implementation and then demonstrate the speedups. Our method achieves speedups ranging from 3x - 28x for graphs with small number of communities while nearly matching or even exceeding the activation performance on the entire graph. Complexity analysis reveals that dramatic speedups are possible for larger graphs that contain a correspondingly larger number of communities. In addition to the speedups obtained from the utilization of the community structure, scalability results show up to 6.3x speedup on 20 cores relative to the baseline run on 2 cores. Finally, current limitations of the approach are outlined along with the planned next steps.

community detection↗

Computational Flame Diagnostics for Direct Numerical Simulations with Detailed Chemistry of Transportation Fuels

The goal of the proposed research is to create computational flame diagnostics (CFLD) that are rigorous numerical algorithms for systematic detection of critical flame features, such as ignition, extinction, and premixed and non-premixed flamelets, and to understand the underlying physicochemical processes controlling limit flame phenomena, flame stabilization, turbulence-chemistry interactions and pollutant emissions etc. The goal has been accomplished through an integrated effort on mechanism reduction, direct numerical simulations (DNS) of flames at engine conditions and a variety of turbulent flames with transport fuels, computational diagnostics, turbulence modeling, and DNS data mining and data reduction. The computational diagnostics are primarily based on the chemical explosive mode analysis (CEMA) and a recently developed bifurcation analysis using datasets from first-principle simulations of 0-D reactors, 1-D laminar flames, and 2-D and 3-D DNS (collaboration with J.H. Chen and S. Som at Argonne, and C.S. Yoo at UNIST). Non-stiff reduced mechanisms for transportation fuels amenable for 3-D DNS are developed through graph-based methods and timescale analysis. The flame structures, stabilization mechanisms, local ignition and extinction etc., and the rate controlling chemical processes are unambiguously identified through CFLD. CEMA is further employed to segment complex turbulent flames based on the critical flame features, such as premixed reaction fronts, and to enable zone-adaptive turbulent combustion modeling.

42 ENGINEERING↗

Bringing Water into an Integrated Assessment Framework

We developed a modeling capability to understand how water is allocated within a river basin and examined present and future water allocations among agriculture, energy production, other human requirements, and ecological needs. Water is an essential natural resource needed for food and fiber production, household and industrial uses, energy production, transportation, tourism and recreation, and the functioning of natural ecosystems. Anthropogenic climate change and population growth are anticipated to impose unprecedented pressure on water resources during this century. Pacific Northwest National Laboratory (PNNL) researchers have pioneered the development of integrated assessment (IA) models for the analysis of energy and economic systems under conditions of climate change. This Laboratory Directed Research and Development (LDRD) effort led to the development of a modeling capability to evaluate current and future water allocations between human requirements and ecosystem services. The Water Prototype Model (WPM) was built in STELLA®, a computer modeling package with a powerful interface that enables users to construct dynamic models to simulate and integrate many processes (biological, hydrological, economics, sociological). A 150,404-km2 basin in the United States (U.S.) Pacific Northwest region served as the platform for the development of the WPM. About 60% of the study basin is in the state of Washington with the rest in Oregon. The Columbia River runs through the basin for 874 km, starting at the international border with Canada and ending (for the purpose of the simulation) at The Dalles dam. Water enters the basin through precipitation and from streamflows originating from the Columbia River at the international border with Canada, the Spokane River, and the Snake River. Water leaves the basin through evapotranspiration, consumptive uses (irrigation, livestock, domestic, commercial, mining, industrial, and off-stream power generation), and streamflow through The Dalles dam. Water also enters the Columbia River via runoff from land. The model runs on a monthly timescale to account for the impact of seasonal variations of climate, streamflows, and water uses. Data for the model prototype were obtained from national databases and ecosystem model results. The WPM can be run from three sources: 1) directly from STELLA, 2) with the isee Player®, or 3) the web version of WPM constructed with NetSim® software. When running any of these three versions, the user is presented a screen with a series of buttons, graphs, and a table. Two of the buttons provide the user with background and instructions on how to run the model. Currently, there are five types of scenarios that can be manipulated alone or in combination using the Sliding Input Devices: 1) interannual variability (e.g., El Niño), 2) climate change, 3) salmon policy, 4) future population, and 5) biodiesel production. Overall, the WPM captured the effects of streamflow conditions on hydropower production. Under La Niña conditions, more hydropower is available during all months of the year, with a substantially higher availability during spring and summer. Under El Niño conditions, hydropower would be reduced, with a total decline of 15% from normal weather conditions over the year. A policy of flow augmentation to facilitate the spring migration of smolts to the ocean would also reduce hydropower supply. Modeled hydropower generation was 23% greater than the 81 TWh reported in the 1995 U.S. Geological Survey (USGS) database. The modeling capability presented here contains the essential features to conduct basin-scale analyses of water allocation under current and future climates. Due to its underlying data structure iv and conceptual foundation, the WPM should be appropriate to conduct IA modeling at national and global scales.

54 ENVIRONMENTAL SCIENCES↗

A Sparse Tensor Benchmark Suite for CPUs and GPUs

Tensor computations present significant performance chal- lenges that impact a wide spectrum of applications ranging from machine learning, healthcare analytics, social network analysis, data mining to quantum chemistry and signal processing. Efforts to improve the perfor- mance of tensor computations include exploring data layout, execution scheduling, and parallelism in common tensor kernels. This work presents a benchmark suite for arbitrary-order sparse tensor kernels using state- of-the-art tensor formats: coordinate (COO) and hierarchical coordinate (HiCOO) on CPUs and GPUs. It presents a set of reference tensor kernel implementations that are compatible with real-world tensors and power law tensors extended from synthetic graph generation techniques. We also propose Roofline performance models for these kernels to provide insights of computer platforms from sparse tensor view. This benchmark suite along with the synthetic tensor generator is publicly available.

Li, Jiajia↗

NIBBS-Search for Fast and Accurate Prediction of Phenotype-Biased Metabolic Systems

Understanding of genotype-phenotype associations is important not only for furthering our knowledge on internal cellular processes, but also essential for providing the foundation necessary for genetic engineering of microorganisms for industrial use (e.g., production of bioenergy or biofuels). However, genotype-phenotype associations alone do not provide enough information to alter an organism’s genome to either suppress or exhibit a phenotype. It is important to look at the phenotype-related genes in the context of the genome-scale network to understand how the genes interact with other genes in the organism. Identification of metabolic subsystems involved in the expression of the phenotype is one way of placing the phenotype-related genes in the context of the entire network. A metabolic system refers to a metabolic network subgraph; nodes are compounds and edges labels are the enzymes that catalyze the reaction. The metabolic subsystem could be part of a single metabolic pathway or span parts of multiple pathways. Arguably, comparative genome-scale metabolic network analysis is a promising strategy to identify these phenotype-related metabolic subsystems. Network Instance-Based Biased Subgraph Search (NIBBS) is a graph-theoretic method for genome-scale metabolic network comparative analysis that can identify metabolic systems that are statistically biased toward phenotypeexpressing organismal networks. We set up experiments with target phenotypes like hydrogen production, TCA expression, and acid-tolerance. We show via extensive literature search that some of the resulting metabolic subsystems are indeed phenotype-related and formulate hypotheses for other systems in terms of their role in phenotype expression. NIBBS is also orders of magnitude faster than MULE, one of the most efficient maximal frequent subgraph mining algorithms that could be adjusted for this problem. Also, the set of phenotype-biased metabolic systems output by NIBBS comes very close to the set of phenotype-biased subgraphs output by an exact maximally-biased subgraph enumeration algorithm ( MBS-Enum ). The code (NIBBS and the module to visualize the identified subsystems) is available at http:// freescience.org/cs/NIBBS.

37 INORGANIC, ORGANIC, PHYSICAL, AND ANALYTICAL CH↗

Scalable Computational Methods for the Analysis of High-Throughput Biological Data

This primary focus of this research project is elucidating genetic regulatory mechanisms that control an organism's responses to low-dose ionizing radiation. Although low doses (at most ten centigrays) are not lethal to humans, they elicit a highly complex physiological response, with the ultimate outcome in terms of risk to human health unknown. The tools of molecular biology and computational science will be harnessed to study coordinated changes in gene expression that orchestrate the mechanisms a cell uses to manage the radiation stimulus. High performance implementations of novel algorithms that exploit the principles of fixed-parameter tractability will be used to extract gene sets suggestive of co-regulation. Genomic mining will be performed to scrutinize, winnow and highlight the most promising gene sets for more detailed investigation. The overall goal is to increase our understanding of the health risks associated with exposures to low levels of radiation.

59 BASIC BIOLOGICAL SCIENCES↗

A Visual Analytics Approach to Structured Data Analysis to Enhance Nonproliferation and Arms Control Verification Activities

Analysis activities for Nonproliferation and Arms Control verification require the use of many types of data. Tabular structured data, such as Excel spreadsheets and relational databases, have traditionally been used for data mining activities, where specific queries are issued against data to look for matching results. The application of visual analytics tools to structured data enables further exploration of datasets to promote discovery of previously unknown results. This paper discusses the application of a specific visual analytics tool to datasets related to the field of Arms Control and Nonproliferation to promote the use of visual analytics more broadly in this domain. Visual analytics focuses on analytical reasoning facilitated by interactive visual interfaces (Wong and Thomas 2004). It promotes exploratory analysis of data, and complements data mining technologies where known patterns can be mined for. Also with a human in the loop, they can bring in domain knowledge and subject matter expertise. Visual analytics has not widely been applied to this domain. In this paper, we will focus on one type of data: structured data, and show the results of applying a specific visual analytics tool to answer questions in the Arms Control and Nonproliferation domain. We chose to use the T.Rex tool, a visual analytics tool developed at PNNL, which uses a variety of visual exploration patterns to discover relationships in structured datasets, including a facet view, graph view, matrix view, and timeline view. The facet view enables discovery of relationships between categorical information, such as countries and locations. The graph tool visualizes node-link relationship patterns, such as the flow of materials being shipped between parties. The matrix visualization shows highly correlated categories of information. The timeline view shows temporal patterns in data. In this paper, we will use T.Rex with two different datasets to demonstrate how interactive exploration of the data can aid an analyst with arms control and nonproliferation verification activities. Using a dataset from PIERS (PIERS 2014), we will show how container shipment imports and exports can aid an analyst in understanding the shipping patterns between two countries. We will also use T.Rex to examine a collection of research publications from the IAEA International Nuclear Information System (IAEA 2014) to discover collaborations of concern. We hope this paper will encourage the use of visual analytics structured data analytics in the field of nonproliferation and arms control verification. Our paper outlines some of the challenges that exist before broad adoption of these kinds of tools can occur and offers next steps to overcome these challenges.

arms control↗

Data mining for materials design: A computational study of single molecule magnet

We develop a method that combines data mining and first principles calculation to guide the designing of distorted cubane Mn{sup 4+} Mn {sub 3}{sup 3+} single molecule magnets. The essential idea of the method is a process consisting of sparse regressions and cross-validation for analyzing calculated data of the materials. The method allows us to demonstrate that the exchange coupling between Mn{sup 4+} and Mn{sup 3+} ions can be predicted from the electronegativities of constituent ligands and the structural features of the molecule by a linear regression model with high accuracy. The relations between the structural features and magnetic properties of the materials are quantitatively and consistently evaluated and presented by a graph. We also discuss the properties of the materials and guide the material design basing on the obtained results.

36 MATERIALS SCIENCE↗

Final Report: Sampling-Based Algorithms for Estimating Structure in Big Data.

The purpose of this project was to develop sampling-based algorithms to discover hidden struc- ture in massive data sets. Inferring structure in large data sets is an increasingly common task in many critical national security applications. These data sets come from myriad sources, such as network traffic, sensor data, and data generated by large-scale simulations. They are often so large that traditional data mining techniques are time consuming or even infeasible. To address this problem, we focus on a class of algorithms that do not compute an exact answer, but instead use sampling to compute an approximate answer using fewer resources. The particular class of algorithms that we focus on are streaming algorithms , so called because they are designed to handle high-throughput streams of data. Streaming algorithms have only a small amount of working storage - much less than the size of the full data stream - so they must necessarily use sampling to approximate the correct answer. We present two results: * A streaming algorithm called HyperHeadTail , that estimates the degree distribution of a graph (i.e., the distribution of the number of connections for each node in a network). The degree distribution is a fundamental graph property, but prior work on estimating the degree distribution in a streaming setting was impractical for many real-world application. We improve upon prior work by developing an algorithm that can handle streams with repeated edges, and graph structures that evolve over time. * An algorithm for the task of maintaining a weighted subsample of items in a stream, when the items must be sampled according to their weight, and the weights are dynamically changing. To our knowledge, this is the first such algorithm designed for dynamically evolving weights. We expect it may be useful as a building block for other streaming algorithms on dynamic data sets.

97 MATHEMATICS AND COMPUTING↗

Fast katz and commuters : efficient estimation of social relatedness in large networks.

Motivated by social network data mining problems such as link prediction and collaborative filtering, significant research effort has been devoted to computing topological measures including the Katz score and the commute time. Existing approaches typically approximate all pairwise relationships simultaneously. In this paper, we are interested in computing: the score for a single pair of nodes, and the top-k nodes with the best scores from a given source node. For the pairwise problem, we apply an iterative algorithm that computes upper and lower bounds for the measures we seek. This algorithm exploits a relationship between the Lanczos process and a quadrature rule. For the top-k problem, we propose an algorithm that only accesses a small portion of the graph and is related to techniques used in personalized PageRank computing. To test the scalability and accuracy of our algorithms we experiment with three real-world networks and find that these algorithms run in milliseconds to seconds without any preprocessing.

99 GENERAL AND MISCELLANEOUS↗

Fast Katz and commuters : efficient estimation of social relatedness.

Motivated by social network data mining problems such as link prediction and collaborative filtering, significant research effort has been devoted to computing topological measures including the Katz score and the commute time. Existing approaches typically approximate all pairwise relationships simultaneously. In this paper, we are interested in computing: the score for a single pair of nodes, and the top-k nodes with the best scores from a given source node. For the pairwise problem, we apply an iterative algorithm that computes upper and lower bounds for the measures we seek. This algorithm exploits a relationship between the Lanczos process and a quadrature rule. For the top-k problem, we propose an algorithm that only accesses a small portion of the graph and is related to techniques used in personalized PageRank computing. To test the scalability and accuracy of our algorithms we experiment with three real-world networks and find that these algorithms run in milliseconds to seconds without any preprocessing.

99 GENERAL AND MISCELLANEOUS↗