Engineering Papers⌕ Search

SEARCH · Engineering Papers

Results for “small-world”

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

WSBP/NWBP small-world neural network and its performance for wind power forecasting

A small-world neural network has stronger generalization ability with high transfer efficiency than that of the regular neural networks. This paper presents two novel small-world neural networks, the Watts-Strogatz small-world based on a BP neural network (WSBP) and a Newman-Watts small-world neural network based on a BP neural network (NWBP), related to previous research of complex networks. The algorithms are developed separately by adopting WS and NW small-world networks as their topological structures, and their derivation and convergence criterion are progressively discussed. After that, the proposed models are subsequently tested by two typical nonlinear functions which confirm their significant improvement over the regular BP networks and other algorithms. Finally, a wind power prediction system is advanced to verify their generalization abilities, and show that the models are practically feasible and effective with improved accuracy and acceptable forecasting errors caused by wind fluctuation and randomness with a time scale up to 24 h.

17 WIND ENERGY↗

Quantum magnetism on small-world networks

While classical spin systems in random networks have been intensively studied, much less is known about quantum magnets in random graphs. In this work, we investigate interacting quantum spins on small-world networks, building on mean-field theory and extensive quantum Monte Carlo simulations. Starting from one-dimensional (1D) rings, we consider two situations: All-to-all interacting and long-range interactions randomly added. The effective infinite dimension of the lattice leads to a magnetic ordering at finite temperature Tc with mean-field criticality. Nevertheless, in contrast to the classical case, we find two distinct power-law behaviors for Tc versus the average strength of the extra couplings. This is controlled by a competition between a characteristic length scale of the random graph and the thermal correlation length of the underlying 1D system, thus challenging mean-field theories. We also investigate the fate of a gapped 1D spin chain against the small-world effect.

75 CONDENSED MATTER PHYSICS, SUPERCONDUCTIVITY AND↗

Potts Model in One-Dimension on Directed Small-World Networks

The critical properties of the Potts model with q=3 and 8 states in one-dimension on directed small-world networks are investigated. This disordered system is simulated by updating it with the Monte Carlo heat bath algorithm. The Potts model on these directed small-world networks presents in fact a second-order phase transition with a new set of critical exponents for q=3 considering a rewiring probability p=0.1. For q=8 the system exhibits only a first-order phase transition independent of p.

71 CLASSICAL AND QUANTUM MECHANICS, GENERAL PHYSIC↗

Three-state majority-vote model on small-world networks

Abstract In this work, we study the opinion dynamics of the three-state majority-vote model on small-world networks of social interactions. In the majority-vote dynamics, an individual adopts the opinion of the majority of its neighbors with probability 1- q , and a different opinion with chance q , where q stands for the noise parameter. The noise q acts as a social temperature, inducing dissent among individual opinions. With probability p , we rewire the connections of the two-dimensional square lattice network, allowing long-range interactions in the society, thus yielding the small-world property present in many different real-world systems. We investigate the degree distribution, average clustering coefficient and average shortest path length to characterize the topology of the rewired networks of social interactions. By employing Monte Carlo simulations, we investigate the second-order phase transition of the three-state majority-vote dynamics, and obtain the critical noise $$q_c$$ q c , as well as the standard critical exponents $$\beta /\nu$$ β / ν , $$\gamma /\nu$$ γ / ν , and $$1/\nu$$ 1 / ν for several values of the rewiring probability p . We conclude that the rewiring of the lattice enhances the social order in the system and drives the model to different universality classes from that of the three-state majority-vote model in two-dimensional square lattices.

99 GENERAL AND MISCELLANEOUS↗

Small-world complex network generation on a digital quantum processor

Abstract Quantum cellular automata (QCA) evolve qubits in a quantum circuit depending only on the states of their neighborhoods and model how rich physical complexity can emerge from a simple set of underlying dynamical rules. The inability of classical computers to simulate large quantum systems hinders the elucidation of quantum cellular automata, but quantum computers offer an ideal simulation platform. Here, we experimentally realize QCA on a digital quantum processor, simulating a one-dimensional Goldilocks rule on chains of up to 23 superconducting qubits. We calculate calibrated and error-mitigated population dynamics and complex network measures, which indicate the formation of small-world mutual information networks. These networks decohere at fixed circuit depth independent of system size, the largest of which corresponding to 1,056 two-qubit gates. Such computations may enable the employment of QCA in applications like the simulation of strongly-correlated matter or beyond-classical computational demonstrations.

97 MATHEMATICS AND COMPUTING↗

A generative graph model for electrical infrastructure networks

We propose a generative graph model for electrical infrastructure networks that accounts for heterogeneity in both node and edge type. To inform the design of this model, we analyze the properties of power grid graphs derived from the U.S. Eastern Interconnection, Texas Interconnection, and Poland transmission system power grids. Across these datasets, we find subgraphs induced by nodes of the same voltage level exhibit shared structural properties atypical to small-world networks, including low local clustering, large diameter and large average distance. On the other hand, we find subgraphs induced by transformer edges linking nodes of different voltage types contain a more limited structure, consisting mainly of small, disjoint star graphs. The goal of our proposed model is to match both these inter and intra-network properties by proceeding in two phases: we first generate subgraphs for each voltage level and then generate transformer edges that connect these subgraphs. The first phase of the model adapts the Chung-Lu random graph model, taking desired vertex degrees and desired diameter as inputs, while the second phase of the model is based on a simpler random star graph generation process. We test the performance of our model by comparing its output across many runs to the aforementioned real data. In nearly all categories tested, we find our model is more accurate in reproducing the unusual mixture of properties apparent in the data than the Chung-Lu model. We also include graph visualization comparisons, as well as a brief analysis of edge-deletion resiliency. Ultimately, our model may be used to generate synthetic graph data, test hypotheses and algorithms at different scales, and serve as a baseline model on top of which further electrical network properties, device models, and interdependencies to other networks, may be appended.

24 POWER TRANSMISSION AND DISTRIBUTION↗

Improving Simulated Annealing by Replacing Its Variables with Game-Theoretic Utility Maximizers

The game-theory field of Collective INtelligence (COIN) concerns the design of computer-based players engaged in a non-cooperative game so that as those players pursue their self-interests, a pre-specified global goal for the collective computational system is achieved as a side-effect. Previous implementations of COIN algorithms have outperformed conventional techniques by up to several orders of magnitude, on domains ranging from telecommunications control to optimization in congestion problems. Recent mathematical developments have revealed that these previously developed algorithms were based on only two of the three factors determining performance. Consideration of only the third factor would instead lead to conventional optimization techniques like simulated annealing that have little to do with non-cooperative games. In this paper we present an algorithm based on all three terms at once. This algorithm can be viewed as a way to modify simulated annealing by recasting it as a non-cooperative game, with each variable replaced by a player. This recasting allows us to leverage the intelligent behavior of the individual players to substantially improve the exploration step of the simulated annealing. Experiments are presented demonstrating that this recasting significantly improves simulated annealing for a model of an economic process run over an underlying small-worlds topology. Furthermore, these experiments reveal novel small-worlds phenomena, and highlight the shortcomings of conventional mechanism design in bounded rationality domains.

Wolpert, David H.↗

Scale-free Graphs for General Aviation Flight Schedules

In the late 1990s a number of researchers noticed that networks in biology, sociology, and telecommunications exhibited similar characteristics unlike standard random networks. In particular, they found that the cummulative degree distributions of these graphs followed a power law rather than a binomial distribution and that their clustering coefficients tended to a nonzero constant as the number of nodes, n, became large rather than O(1/n). Moreover, these networks shared an important property with traditional random graphs as n becomes large the average shortest path length scales with log n. This latter property has been coined the small-world property. When taken together these three properties small-world, power law, and constant clustering coefficient describe what are now most commonly referred to as scale-free networks. Since 1997 at least six books and over 400 articles have been written about scale-free networks. In this manuscript an overview of the salient characteristics of scale-free networks. Computational experience will be provided for two mechanisms that grow (dynamic) scale-free graphs. Additional computational experience will be given for constructing (static) scale-free graphs via a tabu search optimization approach. Finally, a discussion of potential applications to general aviation networks is given.

Alexandov, Natalia M.↗

petal: Co-expression network modelling in R

Background: Networks provide effective models to study complex biological systems, such as gene and protein interaction networks. With the advent of new sequencing technologies, many life scientists are grasping for user-friendly methods and tools to examine biological components at the whole-systems level. Gene co-expression network analysis approaches are frequently used to successfully associate genes with biological processes and demonstrate great potential to gain further insights into the functionality of genes, thus becoming a standard approach in Systems Biology. Here the objective is to construct biologically meaningful and statistically strong co-expression networks, the identification of research dependent subnetworks, and the presentation of self-contained results. Results: We introduce petal, a novel approach to generate gene co-expression network models based on experimental gene expression measures. petal focuses on statistical, mathematical, and biological characteristics of both, input data and output network models. Often over-looked issues of current co-expression analysis tools include the assumption of data normality, which is seldom the case for hight-throughput expression data obtained from RNA-seq technologies. petal does not assume data normality, making it a statistically appropriate method for RNA-seq data. Also, network models are rarely tested for their known typical architecture: scale-free and small-world. petal explicitly constructs networks based on both these characteristics, thereby generating biologically meaningful models. Furthermore, many network analysis tools require a number of user-defined input variables, these often require tuning and/or an understanding of the underlying algorithm; petal requires no user input other than experimental data. This allows for reproducible results, and simplifies the use of petal. Lastly, this approach is specifically designed for very large high-throughput datasets; this way, petal’s network models represent as much of the entire system as possible to provide a whole-system approach. Conclusion: petal is a novel tool for generating co-expression network models of whole-genomics experiments. It is implemented in R and available as a library. Its application to several whole-genome experiments has generated novel meaningful results and has lead the way to new testing hypothesizes for further biological investigation.

59 BASIC BIOLOGICAL SCIENCES↗

Parallelizing Single Source Shortest Path with OpenSHMEM

Single Source Shortest Path (SSSP) is one of the widely occurring graph problems where the paths are discovered from an origin vertex to all other vertices in the graph. In this paper, we discuss our experience parallelizing SSSP using OpenSHMEM. We start with the serial Dijkstra and Bellman-Ford algorithms, parallelize these algorithms, and adapt them to the Partitioned Global Address Space (PGAS) programming model. We implement the parallel algorithms using OpenSHMEM and introduce a series of optimizations to achieve higher scaling and performance characteristics. The implementation is evaluated on Titan with various graphs including synthetic Recursive Matrix (R-MAT) and small-world network graphs as well as real-world graphs from Facebook, Twitter, LiveJournal, and the road maps of California and Texas.

97 MATHEMATICS AND COMPUTING↗

Uncovering transcription factor and microRNA risk regulatory pathways associated with osteoarthritis by network analysis

Osteoarthritis (OA) is the most common form of joint disease. The development of inflammation have been considered to play a key role during the progression of OA. Regulatory pathways are known to play crucial roles in many pathogenic processes. Thus, deciphering these risk regulatory pathways is critical for elucidating the mechanisms underlying OA. We constructed an OA-specific regulatory network by integrating comprehensive curated transcription and post-transcriptional resource involving transcription factor (TF) and microRNA (miRNA). To deepen our understanding of underlying molecular mechanisms of OA, we developed an integrated systems approach to identify OA-specific risk regulatory pathways. In this study, we identified 89 significantly differentially expressed genes between normal and inflamed areas of OA patients. We found the OA-specific regulatory network was a standard scale-free network with small-world properties. It significant enriched many immune response-related functions including leukocyte differentiation, myeloid differentiation and T cell activation. Finally, 141 risk regulatory pathways were identified based on OA-specific regulatory network, which contains some known regulator of OA. The risk regulatory pathways may provide clues for the etiology of OA and be a potential resource for the discovery of novel OA-associated disease genes.

60 APPLIED LIFE SCIENCES↗

Local rewiring algorithms to increase clustering and grow a small world

Abstract Many real-world networks have high clustering among vertices: vertices that share neighbours are often also directly connected to each other. A network’s clustering can be a useful indicator of its connectedness and community structure. Algorithms for generating networks with high clustering have been developed, but typically rely on adding or removing edges and nodes, sometimes from a completely empty network. Here, we introduce algorithms that create a highly clustered network by starting with an existing network and rearranging edges, without adding or removing them; these algorithms can preserve other network properties even as the clustering increases. They rely on local rewiring rules, in which a single edge changes one of its vertices in a way that is guaranteed to increase clustering. This greedy step can be applied iteratively to transform a random network into a form with much higher clustering. Additionally, the algorithms presented grow a network’s clustering faster than they increase its path length, meaning that network enters a regime of comparatively high clustering and low path length: a small world. These algorithms may be a basis for how real-world networks rearrange themselves organically to achieve or maintain high clustering and small-world structure.

97 MATHEMATICS AND COMPUTING↗

NeuroCoreX: An Open-Source FPGA-Based Spiking Neural Network Emulator with On-Chip Learning

Spiking Neural Networks (SNNs) are computational models inspired by the event-driven communication and connectivity patterns of biological neural circuits. They enable high energy efficiency and natural support for diverse architectures ranging from layered networks to small-world and graphstructured topologies. In this work, we introduce NeuroCoreX, an open-source, FPGA-based spiking neural network emulator that provides real-time, on-chip learning and flexible network organization. NeuroCoreX supports both feedforward sensory inputs streamed directly from sensors or PCs via UART and recurrent on-chip connectivity, enabling simultaneous processing and learning from external stimuli and internal network dynamics-capabilities rarely available in existing FPGA SNN platforms. The system implements a Leaky Integrate-and-Fire (LIF) neuron model with current-based synapses and supports pair-based STDP learning on both feedforward and recurrent synapses. A lightweight Python interface enables interactive configuration, live monitoring, weight read-back, and experiment control. Importantly, NeuroCoreX is tightly integrated with the SuperNeuroMAT simulator, allowing SNN models to be transferred seamlessly from software to hardware for hardware-in-the-loop development. By combining real-time plasticity, flexible connectivity, and an open-source VHDL implementation, NeuroCoreX provides an extensible and accessible platform for neuromorphic research, algorithm-hardware co-design, and energy-efficient edge intelligence.

Gautam, Ashish [ORNL]↗

Trust based attachment

In social systems subject to indirect reciprocity, a positive reputation is key for increasing one’s likelihood of future positive interactions. The flow of gossip can amplify the impact of a person’s actions on their reputation depending on how widely it spreads across the social network, which leads to a percolation problem. To quantify this notion, we calculate the expected number of individuals, the “audience”, who find out about a particular interaction. For a potential donor, a larger audience constitutes higher reputational stakes, and thus a higher incentive, to perform “good” actions in line with current social norms. For a receiver, a larger audience therefore increases the trust that the partner will be cooperative. This idea can be used for an algorithm that generates social networks, which we call trust based attachment (TBA). TBA produces graphs that share crucial quantitative properties with real-world networks, such as high clustering, small-world behavior, and powerlaw degree distributions. We also show that TBA can be approximated by simple friend-of-friend routines based on triadic closure, which are known to be highly effective at generating realistic social network structures. Therefore, our work provides a new justification for triadic closure in social contexts based on notions of trust, gossip, and social information spread. These factors are thus identified as potential significant influences on how humans form social ties.

59 BASIC BIOLOGICAL SCIENCES↗

Graph Sampling for Visual Analytics

Effectively visualizing large graphs and capturing the statistical properties are two challenging tasks. To aid in these two tasks, many sampling approaches for graph simplification have been proposed, falling into three categories: node sampling, edge sampling, and traversal-based sampling. It is still unknown which approach is the best. We evaluate commonly used graph sampling methods through a combined visual and statistical comparison of graphs sampled at various rates. We conduct our evaluation on three graph models: random graphs, small-world graphs, and scale-free graphs. Initial results indicate that the effectiveness of a sampling method is dependent on the graph model, the size of the graph, and the desired statistical property. This benchmark study can be used as a guideline in choosing the appropriate method for a particular graph sampling task, and the results presented can be incorporated into graph visualization and analysis tools.

97 MATHEMATICS AND COMPUTING↗

Improving Search Algorithms by Using Intelligent Coordinates

We consider algorithms that maximize a global function G in a distributed manner, using a different adaptive computational agent to set each variable of the underlying space. Each agent eta is self-interested; it sets its variable to maximize its own function g (sub eta). Three factors govern such a distributed algorithm's performance, related to exploration/exploitation, game theory, and machine learning. We demonstrate how to exploit alI three factors by modifying a search algorithm's exploration stage: rather than random exploration, each coordinate of the search space is now controlled by a separate machine-learning-based player engaged in a noncooperative game. Experiments demonstrate that this modification improves simulated annealing (SA) by up to an order of magnitude for bin packing and for a model of an economic process run over an underlying network. These experiments also reveal interesting small-world phenomena.

Wolpert, David H.↗

A Comparison of Geographic Information Systems, Complex Networks, and Other Models for Analyzing Transportation Network Topologies

This report reviews six classes of models that are used for studying transportation network topologies. The report is motivated by two main questions. First, what can the "new science" of complex networks (scale-free, small-world networks) contribute to our understanding of transport network structure, compared to more traditional methods? Second, how can geographic information systems (GIS) contribute to studying transport networks? The report defines terms that can be used to classify different kinds of models by their function, composition, mechanism, spatial and temporal dimensions, certainty, linearity, and resolution. Six broad classes of models for analyzing transport network topologies are then explored: GIS; static graph theory; complex networks; mathematical programming; simulation; and agent-based modeling. Each class of models is defined and classified according to the attributes introduced earlier. The paper identifies some typical types of research questions about network structure that have been addressed by each class of model in the literature.

Alexandrov, Natalia↗