Engineering Papers⌕ Search

SEARCH · Engineering Papers

Results for “community detection”

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

Direction-optimizing Label Propagation Framework for Structure Detection in Graphs: Design, Implementation, and Experimental Analysis

Label Propagation is not only a well-known machine learning algorithm for classification but also an effective method for discovering communities and connected components in networks. We propose a new Direction-optimizing Label Propagation Algorithm (DOLPA) framework that enhances the performance of the standard Label Propagation Algorithm (LPA), increases its scalability, and extends its versatility and application scope. As a central feature, the DOLPA framework relies on the use of frontiers and alternates between label push and label pull operations to attain high performance. It is formulated in such a way that the same basic algorithm can be used for finding communities or connected components in graphs by only changing the objective function used. Additionally, DOLPA has parameters for tuning the processing order of vertices in a graph to reduce the number of edges visited and improve the quality of solution obtained. We present the design and implementation of the enhanced algorithm as well as our shared-memory parallelization of it using OpenMP. We also present an extensive experimental evaluation of our implementations using the LFR benchmark and real-world networks drawn from various domains. Compared with an implementation of LPA for community detection available in a widely used network analysis software, we achieve at most five times the F-Score while maintaining similar runtime for graphs with overlapping communities. We also compare DOLPA against an implementation of the Louvain method for community detection using the same LFR-graphs and show that DOLPA achieves about three times the F-Score at just 10% of the runtime. For connected component decomposition, our algorithm achieves orders of magnitude speedups over the basic LP-based algorithm on large-diameter graphs, up to 13.2× speedup over the Shiloach-Vishkin algorithm, and up to 1.6× speedup over Afforest on an Intel Xeon processor using 40 threads.

97 MATHEMATICS AND COMPUTING↗
DOE OSTI2022

A differentiable approach to the maximum independent set problem using dataless neural networks

The success of machine learning solutions for reasoning about discrete structures has brought attention to its adoption within combinatorial optimization algorithms. Such approaches generally rely on supervised learning by leveraging datasets of the combinatorial structures of interest drawn from some distribution of problem instances. Reinforcement learning has also been employed to find such structures. Here, in this paper, we propose a different approach in that no data is required for training the neural networks that produce the solution. In this sense, what we present is not a machine learning solution, but rather one that is dependent on neural networks and where backpropagation is applied to a loss function defined by the structure of the neural network architecture as opposed to a training dataset. In particular, we reduce the popular combinatorial optimization problem of finding a maximum independent set to a neural network and employ a dataless training scheme to refine the parameters of the network such that those parameters yield the structure of interest. Additionally, we propose a universal graph reduction procedure to handle large-scale graphs. The reduction exploits community detection for graph partitioning and is applicable to any graph type and/or density. Experimental results on both real and synthetic graphs demonstrate that our proposed method performs on par or outperforms state-of-the-art learning-based methods in terms of the size of the found set without requiring any training data.

97 MATHEMATICS AND COMPUTING↗
DOE OSTI2021

Multilevel Combinatorial Optimization across Quantum Architectures

Emerging quantum processors provide an opportunity to explore new approaches for solving traditional problems in the post Moore’s law supercomputing era. However, the limited number of qubits makes it infeasible to tackle massive real-world datasets directly in the near future, leading to new challenges in utilizing these quantum processors for practical purposes. Furthermore, hybrid quantum-classical algorithms that leverage both quantum and classical types of devices are considered as one of the main strategies to apply quantum computing to large-scale problems. In this article, we advocate the use of multilevel frameworks for combinatorial optimization as a promising general paradigm for designing hybrid quantum-classical algorithms. To demonstrate this approach, we apply this method to two well-known combinatorial optimization problems, namely, the Graph Partitioning Problem, and the Community Detection Problem. We develop hybrid multilevel solvers with quantum local search on D-Wave’s quantum annealer and IBM’s gate-model based quantum processor. We carry out experiments on graphs that are orders of magnitude larger than the current quantum hardware size, and we observe results comparable to state-of-the-art solvers in terms of quality of the solution.

97 MATHEMATICS AND COMPUTING↗
DOE OSTI2022

The ecological assembly of bacterial communities in Antarctic wetlands varies across levels of phylogenetic resolution

Summary As functional traits are conserved at different phylogenetic depths, the ability to detect community assembly processes can be conditional on the phylogenetic resolution; yet most previous work quantifying their influence has focused on a single level of phylogenetic resolution. Here, we have studied the ecological assembly of bacterial communities from an Antarctic wetland complex, applying null models across different levels of phylogenetic resolution (i.e. clustering ASVs into OTUs with decreasing sequence identity thresholds). We found that the relative influence of the community assembly processes varies with phylogenetic resolution. More specifically, selection processes seem to impose stronger influence at finer (100% sequence similarity ASV) than at coarser (99%–97% sequence similarity OTUs) resolution. We identified environmental features related with the ecological processes and propose a conceptual model for the bacterial community assembly in this Antarctic ecosystem. Briefly, eco‐evolutionary processes appear to be leading to different but very closely related ASVs in lotic, lentic and terrestrial environments. In all, this study shows that assessing community assembly processes at different phylogenetic resolutions is key to improve our understanding of microbial ecology. More importantly, a failure to detect selection processes at coarser phylogenetic resolution does not imply the absence of such processes at finer resolutions.

59 BASIC BIOLOGICAL SCIENCES↗
DOE OSTI2021

City-Wide Distributed Roof-Top Photovoltaic System Adoption Forecast, Grid Impact Simulation, & Neighborhood Microgrid Contribution Assessment

The adoption of distributed photovoltaic (PV) systems grew significantly in recent years. Market projections anticipate future growth for both residential and commercial installations. To understand grid impacts associated with distributed PV, useful hosting capacity studies require accurate representations of the spatial distribution of PV adoptions. Prediction of PV locations and numbers depends on median income data, building use zoning maps, and permit records to understand existing trends and predict future adoption rates and locations throughout an entire city. Using the PV adoption data, advanced and realistic simulations were performed to capture the distributed PV impacts on the grid. Also, using graph theory community detection hundreds of neighborhood microgrids can be discovered for the entire city by identifying densely connected loads that are sparsely connected to other communities. Then, based on the PV adoption predictions, this work identified the contribution of PV within each of the newly discovered graph theory defined microgrid communities.

24 POWER TRANSMISSION AND DISTRIBUTION↗
DOE OSTI2021

Feebly-interacting particles: FIPs 2020 workshop report

With the establishment and maturation of the experimental programs searching for new physics with sizeable couplings at the LHC, there is an increasing interest in the broader particle and astrophysics community for exploring the physics of light and feebly-interacting particles as a paradigm complementary to a New Physics sector at the TeV scale and beyond. FIPs 2020 has been the first workshop fully dedicated to the physics of feebly-interacting particles and was held virtually from 31 August to 4 September 2020. The workshop has gathered together experts from collider, beam dump, fixed target experiments, as well as from astrophysics, axions/ALPs searches, current/future neutrino experiments, and dark matter direct detection communities to discuss progress in experimental searches and underlying theory models for FIPs physics, and to enhance the cross-fertilisation across different fields. FIPs 2020 has been complemented by the topical workshop “Physics Beyond Colliders meets theory”, held at CERN from 7 June to 9 June 2020. This document presents the summary of the talks presented at the workshops and the outcome of the subsequent discussions held immediately after. It aims to provide a clear picture of this blooming field and proposes a few recommendations for the next round of experimental results.

72 PHYSICS OF ELEMENTARY PARTICLES AND FIELDS↗
DOE OSTI2023

Hunting Sub-GeV Dark Matter with Diamonds and Magnetic Microcalorimeters Principle

This project is to study feasibility of a new concept for the sub-GeV dark matter (DM) detection using diamond crystals and magnetic microcalorimeters (MMCs). Diamond crystals are made of low mass carbon constituent that maximize kinetic energy of nuclear recoils from sub-GeV DM scattering due to their relatively similar masses. MMC is employed as a sensitive phonon sensor to measure athermal phonons that are produced by DM scattering in diamond crystals with 100 ns timing resolution and ~10 eV energy resolution. MMC’s fast timing resolution allows high precision phonon pulse shape analysis to separate out unwanted background or noise signals in the low energy region at E < 1 keV. Especially, the low energy excess (LEE) problems have been reported in the dark matter detection community and the proposed diamond-MMC detector might be able to provide important information to understand the origins of LEE signals in DM detectors. In this project a diamond-MMC detector has been built for proof-of-concept experiments and athermal phonon collection efficiencies have been investigated for single crystal and poly-crystal chemical-vapour-diamonds (SC and PC CVDs) as well as reference sapphire crystals are tested in the same geometries to quatify athermal phonon propagation and their collection to the MMC phonon sensors. Athermal phonon collection efficiencies and their lifetime in the diamond and sapphire crystals are successfully measured in the same geometry and experimental setup for comparison. SC CVD crystals exhibit poorer performance than the sapphire reference crystals in athermal phonon collection, while the PC CVD crystal exhibit better result than the sapphire. PC CVD with MMC phonon sensors would be feasible for sub GeV DM detection.

72 PHYSICS OF ELEMENTARY PARTICLES AND FIELDS↗
DOE OSTI2020

Multifrontal Non-negative Matrix Factorization

Non-negative matrix factorization (Nmf) is an important tool in high-performance large scale data analytics with applications ranging from community detection, recommender system, feature detection and linear and non-linear unmixing. While traditional Nmf works well when the data set is relatively dense, however, it may not extract sufficient structure when the data is extremely sparse. Specifically, traditional Nmf fails to exploit the structured sparsity of the large and sparse data sets resulting in dense factors. We propose a new algorithm for performing Nmf on sparse data that we call multifrontal Nmf (Mf-Nmf) since it borrows several ideas from the multifrontal method for unconstrained factorization (e.g. LU and QR). We also present an efficient shared memory parallel implementation of Mf-Nmf and discuss its performance and scalability. We conduct several experiments on synthetic and realworld datasets and demonstrate the usefulness of the algorithm by comparing it against standard baselines. We obtain a speedup of 1.2x to 19.5x on 24 cores with an average speed up of 10.3x across all the real world datasets.

Sao, Piyush↗
DOE OSTI2025

Toward computing bounds for Ramsey numbers using quantum annealing

Quantum annealing is a powerful tool for solving and approximating combinatorial optimization problems, such as graph partitioning, community detection, centrality, routing problems, and more. In this paper we explore the use of quantum annealing as a tool for use in exploring combinatorial mathematics research problems. We consider the monochromatic triangle problem and the Ramsey number problem, both examples of graph coloring. Conversion to quadratic unconstrained binary optimization (QUBO) form is required to run on quantum hardware. While the monochromatic triangle problem is quadratic by nature, the Ramsey number problem requires the use of order reduction methods for a quadratic formulation. The goal is to provide a method for producing special colorings of graphs which if successful would provide lower bounds for certain Ramsey numbers. We discuss implementations, limitations, and results when running on the D-Wave Advantage quantum annealer.

97 MATHEMATICS AND COMPUTING↗
DOE OSTI2022

Avalanche gain and its effect on energy resolution in GEM-based detectors

Here, we present avalanche gain and associated resolution measurements recorded with a 4 He:CO 2 (70:30) gas mixture and pure SF 6 , a Negative Ion (NI) gas. SF 6 is of particular interest to the directional dark matter detection community, as its low thermal diffusion helps to retain recoil ionization track features over long drift lengths. With the aid of a general form of the reduced first Townsend coefficient (RFTC), multiple GEM-based detector data sets are used to study the high-gain behavior of the 4 He:CO 2 gas mixture. The high-gain data is well described purely in terms of the reduced electric field strength and the number of GEMs, and the robust relationship between the RFTC and the average, reduced, electric field strength across the GEMs is emphasized. The associated (pulse-height) resolution measurements are used to discuss the variance of the avalanche distribution and to describe and estimate the lower limits of energy resolution one should expect to measure using a simple relationship with the RFTC. In the end, a description of avalanche gain, its effect on energy resolution, and the contributing experimental parameters in GEM-based detectors is developed over a broad parameter space for further use.

46 INSTRUMENTATION RELATED TO NUCLEAR SCIENCE AND ↗
DOE OSTI2023

Network Analysis of Academic Medical Center Websites in the United States

Healthcare resources are published annually in repositories such as the AHA Annual Survey Database TM . However, these data repositories are created via manual surveying techniques which are cumbersome in collection and not updated as frequently as website information of the respective hospital systems represented. Also, this resource is not widely available to patients in an easy-to-use format. Network analysis techniques have the potential to create topological maps which serve to aid in pathfinding for patients in their search for healthcare services. This study explores the topological structure of forty United States academic health center websites. Network analysis is utilized to analyze and visualize 48,686 webpages. Several elements of network structure are examined including basic network properties, and centrality measures distributions. The Louvain community detection algorithm is used to examine the extent to which these techniques allow identification of healthcare resources within networks. The results indicate that websites with related healthcare services tend to form observable clusters useful in mapping key resources within a hospital system.

97 MATHEMATICS AND COMPUTING↗
DOE OSTI2021

Topological data analysis of task-based fMRI data from experiments on schizophrenia

We use methods from computational algebraic topology to study functional brain networks, in which nodes represent brain regions and weighted edges represent similarity of fMRI time series from each region. With these tools, which allow one to characterize topological invariants such as loops in high-dimensional data, we are able to gain understanding into low-dimensional structures in networks in a way that complements traditional approaches based on pairwise interactions. In the present paper, we analyze networks constructed from task-based fMRI data from schizophrenia patients, healthy controls, and healthy siblings of schizophrenia patients using persistent homology, which allows us to explore the persistence of topological structures such as loops at different scales in the networks. We use persistence landscapes, persistence images, and Betti curves to create output summaries from our persistent-homology calculations, and we study the persistence landscapes and images using k-means clustering and community detection. Based on our analysis of persistence landscapes, we find that the members of the sibling cohort have topological features (specifically, their 1-dimensional loops) that are distinct from the other two cohorts. From the persistence images, we are able to distinguish all three subject groups and to determine the brain regions in the loops (with four or more edges) that allow us to make these distinctions.

60 APPLIED LIFE SCIENCES↗
DOE OSTI2023

Neutrino signatures of 100 2D Axisymmetric Core-Collapse Supernova Simulations

ABSTRACT We present in this paper a public data release of an unprecedentedly large set of core-collapse supernova (CCSN) neutrino emission models, comprising 100 detailed 2D axisymmetric radiation-hydrodynamic simulations evolved out to as late as ∼5 s post-bounce and spanning an extensive range of massive-star progenitors. The motivation for this paper is to provide a physically and numerically uniform benchmark data set to the broader neutrino detection community to help it characterize and optimize subsurface facilities for what is likely to be a once-in-a-lifetime galactic supernova burst event. With this release, we hope to (1) help the international experiment and modelling communities more efficiently optimize the retrieval of physical information about the next galactic CCSN, (2) facilitate the better understanding of core-collapse theory and modelling among interested experimentalists, and (3) help further integrate the broader supernova neutrino community.

Astronomy & Astrophysics↗
DOE OSTI2023

Measuring the Migdal effect in semiconductors for dark matter detection

The Migdal effect has received much attention from the dark matter direct detection community, in particular due to its power in setting leading limits on sub-GeV particle dark matter. However, it is crucial to obtain experimental confirmation of the Migdal effect through nuclear scattering using Standard Model probes. In this work, we extend existing calculations of the Migdal effect to the case of neutron-nucleus scattering, with a particular focus on neutron scattering angle distributions in silicon. We identify kinematic regimes wherein the assumptions present in current calculations of the Migdal effect hold for neutron scattering and demonstrate that these include viable neutron calibration schemes. We then apply this framework to propose an experimental strategy to measure the Migdal effect in cryogenic silicon detectors using an upgrade to the NEXUS facility at Fermilab.

46 INSTRUMENTATION RELATED TO NUCLEAR SCIENCE AND ↗
DOE OSTI2023

A Data Processing Pipeline for Socio-Technical Network Analysis [Slides]

With the rapid adoption of emerging technologies, there is a need to catalog and model sociotechnical interdependencies that have been historically used to influence the operation of Critical Infrastructure networks including the impacts of mergers and acquisitions, hostile takeovers, and foreign investment. Our research intends to address this need with two primary contributions. First, we have developed a data curation and processing pipeline to generate sociotechnical networks extracted from a variety of data sources including SEC filings and infrastructure asset databases. The pipeline, implemented in Apache Airflow, extracts and normalizes the representation of entities and relations, specified within ontologies. Second, networks produced by our pipeline enable the development of graph-theoretic metrics that consider the properties of network components in addition to its topology. Measures of network complexity, such as degree distribution, reachability analyses, temporal analysis, and community detection may be adapted to indicate adversarial organizational influence. Our intent is to provide an extensible, machine-actionable approach to quickly communicate such models, reproduce previous results, and adapt them to new, unanticipated situations.

97 MATHEMATICS AND COMPUTING↗
DOE OSTI2023

Use of Graph Theory and Neural Networks for Microstructural Classification

Recent advances in materials data analytics have provided new avenues for determining process-structure-property (PSP) linkages in a variety of materials. Machine learning techniques including few-shot learning have increased the efficiency of classifying microscopy images for the purposes of material characterization. Modifications in segmentation also show potential in improving the accuracy of our current pyCHIP classifier. Replacing previous encoders trained on ImageNet with those trained on microscopy images like MicroNet has initially shown better performance at classifying images of irradiated samples. Additionally, different normalization approaches were tested to show no discernable effect on classification. The Louvain method for community detection is analyzed on a set of irradiated samples with different parameters to determine which proved beneficial under what circumstances. We suggest that microscopy experiments be automated in the future using a combination of these techniques to enable high-throughput analyses.

36 MATERIALS SCIENCE↗
DOE OSTI2020

Vertex Reordering for Real-world Graphs and Applications: An Empirical Evaluation

Vertex reordering is a way to improve locality in graph computations. Given an input (or ``natural'') order, reordering aims to compute an alternate permutation of the vertices that is aimed at maximizing a locality-based objective. Given decades of research on this topic, there are tens of graph reordering schemes, and there are also several linear arrangement ``gap'' measures for treatment as objectives. However, a comprehensive empirical analysis of the efficacy of the ordering schemes against the different gap measures, and against real-world applications is currently lacking. In this study, we present an extensive empirical evaluation of up to 11 ordering schemes, taken from different classes of approaches, on a set of 34 real-world graphs emerging from different application domains. Our study is presented in two parts: a) a thorough comparative evaluation of the different ordering schemes on their effectiveness to optimize different linear arrangement gap measures, relevant to preserving locality; and b) extensive evaluation of the impact of the ordering schemes on two real-world, parallel graph applications, namely, community detection and influence maximization. Our studies show a significant divergence among the ordering schemes (up to $40\times$ between the best and the poor) in their effectiveness to reduce the gap measures; and a wide ranging impact of the ordering schemes on various aspects including application runtime (up to $4\times$), memory and cache use, load balancing, and parallel work and efficiency. The comparative study also help reveal the nuances of a parallel environment (compared to serial) on the ordering schemes and their role in optimizing applications.

Barik, Reet↗