Memory and communication efficient algorithm for decentralized counting of nodes in networks
Ontology highlight
ABSTRACT:
SUBMITTER: Saha A
PROVIDER: S-EPMC8608303 | biostudies-literature |
REPOSITORIES: biostudies-literature
Similar Datasets
Project description:Understanding structural controllability of a complex network requires to identify a Minimum Input nodes Set (MIS) of the network. Finding an MIS is known to be equivalent to computing a maximum matching of the network, where the unmatched nodes constitute an MIS. However, maximum matching is often not unique for a network, and finding all possible input nodes, the union of all MISs, may provide deep insights to the controllability of the network. Here we present an efficient enumerative algorithm for the problem. The main idea is to modify a maximum matching algorithm to make it efficient for finding all possible input nodes by computing only one MIS. The algorithm can also output a set of substituting nodes for each input node in the MIS, so that any node in the set can replace the latter. We rigorously proved the correctness of the new algorithm and evaluated its performance on synthetic and large real networks. The experimental results showed that the new algorithm ran several orders of magnitude faster than an existing method on large real networks.
| S-EPMC5587595 | biostudies-literature
Project description:Limited communication resources have gradually become a critical factor toward efficiency of decentralized large scale multi-agent coordination when both system scales up and tasks become more complex. In current researches, due to the agent's limited communication and observational capability, an agent in a decentralized setting can only choose a part of channels to access, but cannot perceive or share global information. Each agent's cooperative decision is based on the partial observation of the system state, and as such, uncertainty in the communication network is unavoidable. In this situation, it is a major challenge working out cooperative decision-making under uncertainty with only a partial observation of the environment. In this paper, we propose a decentralized approach that allows agents cooperatively search and independently choose channels. The key to our design is to build an up-to-date observation for each agent's view so that a local decision model is achievable in a large scale team coordination. We simplify the Dec-POMDP model problem, and each agent can jointly work out its communication policy in order to improve its local decision utilities for the choice of communication resources. Finally, we discuss an implicate resource competition game, and show that, there exists an approximate resources access tradeoff balance between agents. Based on this discovery, the tradeoff between real-time decision-making and the efficiency of cooperation using these channels can be well improved.
| S-EPMC4699651 | biostudies-literature
Project description:We present an analytical framework that allows the quantitative study of statistical dynamic properties of networks with adaptive nodes that have memory and is used to examine the emergence of oscillations in networks with response failures. The frequency of the oscillations was quantitatively found to increase with the excitability of the nodes and with the average degree of the network and to decrease with delays between nodes. For networks of networks, diverse cluster oscillation modes were found as a function of the topology. Analytical results are in agreement with large-scale simulations and open the horizon for understanding network dynamics composed of finite memory nodes as well as their different phases of activity.
| S-EPMC5457433 | biostudies-literature
Project description:Lighter is a fast, memory-efficient tool for correcting sequencing errors. Lighter avoids counting k-mers. Instead, it uses a pair of Bloom filters, one holding a sample of the input k-mers and the other holding k-mers likely to be correct. As long as the sampling fraction is adjusted in inverse proportion to the depth of sequencing, Bloom filter size can be held constant while maintaining near-constant accuracy. Lighter is parallelized, uses no secondary storage, and is both faster and more memory-efficient than competing approaches while achieving comparable accuracy.
| S-EPMC4248469 | biostudies-literature
Project description:Energy conservation in wireless sensor networks (WSNs) is a vital consideration when designing wireless networking protocols. In this paper, we propose a Decentralized Fuzzy Clustering Protocol, named DCFP, which minimizes total network energy dissipation to promote maximum network lifetime. The process of constructing the infrastructure for a given WSN is performed only once at the beginning of the protocol at a base station, which remains unchanged throughout the network's lifetime. In this initial construction step, a fuzzy C-means algorithm is adopted to allocate sensor nodes into their most appropriate clusters. Subsequently, the protocol runs its rounds where each round is divided into a CH-Election phase and a Data Transmission phase. In the CH-Election phase, the election of new cluster heads is done locally in each cluster where a new multicriteria objective function is proposed to enhance the quality of elected cluster heads. In the Data Transmission phase, the sensing and data transmission from each sensor node to their respective cluster head is performed and cluster heads in turn aggregate and send the sensed data to the base station. Simulation results demonstrate that the proposed protocol improves network lifetime, data delivery, and energy consumption compared to other well-known energy-efficient protocols.
| S-EPMC4138945 | biostudies-other
Project description:Often derived from partial correlations or many pairwise analyses, covariance networks represent the inter-relationships among regions and can reveal important topological structures in brain measures from healthy and pathological subjects. However both approaches are not consistent network estimators and are sensitive to the value of the tuning parameters. Here, we propose a consistent covariance network estimator by maximising the network likelihood (MNL) which is robust to the tuning parameter. We validate the consistency of our algorithm theoretically and via a simulation study, and contrast these results against two well-known approaches: the graphical LASSO (gLASSO) and Pearson pairwise correlations (PPC) over a range of tuning parameters. The MNL algorithm had a specificity equal to and greater than 0.94 for all sample sizes in the simulation study, and the sensitivity was shown to increase as the sample size increased. The gLASSO and PPC demonstrated a specificity-sensitivity trade-off over a range of values of tuning parameters highlighting the discrepancy in the results for misspecified values. Application of the MNL algorithm to the case study data showed a loss of connections between healthy and impaired groups, and improved ability to identify between lobe connectivity in contrast to gLASSO networks. In this work, we propose the MNL algorithm as an effective approach to find covariance brain networks, which can inform the organisational features in brain-wide analyses, particularly for large sample sizes.
| S-EPMC6042721 | biostudies-literature
Project description:BackgroundGene networks in living cells can change depending on various conditions such as caused by different environments, tissue types, disease states, and development stages. Identifying the differential changes in gene networks is very important to understand molecular basis of various biological process. While existing algorithms can be used to infer two gene networks separately from gene expression data under two different conditions, and then to identify network changes, such an approach does not exploit the similarity between two gene networks, and it is thus suboptimal. A desirable approach would be clearly to infer two gene networks jointly, which can yield improved estimates of network changes.ResultsIn this paper, we developed a proximal gradient algorithm for differential network (ProGAdNet) inference, that jointly infers two gene networks under different conditions and then identifies changes in the network structure. Computer simulations demonstrated that our ProGAdNet outperformed existing algorithms in terms of inference accuracy, and was much faster than a similar approach for joint inference of gene networks. Gene expression data of breast tumors and normal tissues in the TCGA database were analyzed with our ProGAdNet, and revealed that 268 genes were involved in the changed network edges. Gene set enrichment analysis identified a significant number of gene sets related to breast cancer or other types of cancer that are enriched in this set of 268 genes. Network analysis of the kidney cancer data in the TCGA database with ProGAdNet also identified a set of genes involved in network changes, and the majority of the top genes identified have been reported in the literature to be implicated in kidney cancer. These results corroborated that the gene sets identified by ProGAdNet were very informative about the cancer disease status. A software package implementing the ProGAdNet, computer simulations, and real data analysis is available as Additional file 1.ConclusionWith its superior performance over existing algorithms, ProGAdNet provides a valuable tool for finding changes in gene networks, which may aid the discovery of gene-gene interactions changed under different conditions.
| S-EPMC6498668 | biostudies-literature
Project description:The spiking neural networks (SNNs) are the third generation of neural networks and perform remarkably well in cognitive tasks such as pattern recognition. The spike emitting and information processing mechanisms found in biological cognitive systems motivate the application of the hierarchical structure and temporal encoding mechanism in spiking neural networks, which have exhibited strong computational capability. However, the hierarchical structure and temporal encoding approach require neurons to process information serially in space and time respectively, which reduce the training efficiency significantly. For training the hierarchical SNNs, most existing methods are based on the traditional back-propagation algorithm, inheriting its drawbacks of the gradient diffusion and the sensitivity on parameters. To keep the powerful computation capability of the hierarchical structure and temporal encoding mechanism, but to overcome the low efficiency of the existing algorithms, a new training algorithm, the Normalized Spiking Error Back Propagation (NSEBP) is proposed in this paper. In the feedforward calculation, the output spike times are calculated by solving the quadratic function in the spike response model instead of detecting postsynaptic voltage states at all time points in traditional algorithms. Besides, in the feedback weight modification, the computational error is propagated to previous layers by the presynaptic spike jitter instead of the gradient decent rule, which realizes the layer-wised training. Furthermore, our algorithm investigates the mathematical relation between the weight variation and voltage error change, which makes the normalization in the weight modification applicable. Adopting these strategies, our algorithm outperforms the traditional SNN multi-layer algorithms in terms of learning efficiency and parameter sensitivity, that are also demonstrated by the comprehensive experimental results in this paper.
| S-EPMC4820126 | biostudies-literature
Project description:Recently, wireless sensor network (WSN) applications have seen an increase in interest. In search and rescue, battlefield reconnaissance, and some other such applications, so that a survey of the area of interest can be made collectively, a set of mobile nodes is deployed. Keeping the network nodes connected is vital for WSNs to be effective. The provision of connectivity can be made at the time of startup and can be maintained by carefully coordinating the nodes when they move. However, if a node suddenly fails, the network could be partitioned to cause communication problems. Recently, several methods that use the relocation of nodes for connectivity restoration have been proposed. However, these methods have the tendency to not consider the potential coverage loss in some locations. This paper addresses the concerns of both connectivity and coverage in an integrated way so that this gap can be filled. A novel algorithm for simultaneous-node repositioning is introduced. In this approach, each neighbour of the failed node, one by one, moves in for a certain amount of time to take the place of the failed node, after which it returns to its original location in the network. The effectiveness of this algorithm has been verified by the simulation results.
| S-EPMC4134831 | biostudies-other
Project description:This trial examines cancer communication within Hispanic social networks. Hispanics have the lowest colorectal cancer screening rate of any major ethnic group and health interventions are crucially needed among Hispanics. Patient decision aids are health communication interventions designed to provide patients with targeted health information and have shown to improve colorectal cancer screening rates among Hispanics. The goal of this study is to investigate, in a sample of Hispanics, how a colorectal cancer decision aid aimed at increasing individuals’ colorectal cancer screening behavior has effects on their alters’ intention to get screened for colorectal cancer.
| 2343521 | ecrin-mdr-crc