Two betweenness centrality measures based on Randomized Shortest Paths.
Ontology highlight
ABSTRACT:
SUBMITTER: Kivimaki I
PROVIDER: S-EPMC4738330 | biostudies-other | 2016
REPOSITORIES: biostudies-other
Similar Datasets
Project description:Betweenness centrality is one of the key measures of the node importance in a network. However, it is computationally intractable to calculate the exact betweenness centrality of nodes in large-scale networks. To solve this problem, we present an efficient CBCA (Centroids based Betweenness Centrality Approximation) algorithm based on progressive sampling and shortest paths approximation. Our algorithm firstly approximates the shortest paths by generating the network centroids according to the adjacency information entropy of the nodes; then constructs an efficient error estimator using the Monte Carlo Empirical Rademacher averages to determine the sample size which can achieve a balance with accuracy; finally, we present a novel centroid updating strategy based on network density and clustering coefficient, which can effectively reduce the computation burden of updating shortest paths in dynamic networks. The experimental results show that our CBCA algorithm can efficiently output high-quality approximations of the betweenness centrality of a node in large-scale complex networks.
| S-EPMC10564764 | biostudies-literature
Project description:The shortest path problem is one of the most fundamental networks optimization problems. Nowadays, individuals interact in extraordinarily numerous ways through their offline and online life (e.g., co-authorship, co-workership, or retweet relation in Twitter). These interactions have two key features. First, they have a heterogeneous nature, and second, they have different strengths that are weighted based on their degree of intimacy, trustworthiness, service exchange or influence among individuals. These networks are known as multiplex networks. To our knowledge, none of the previous shortest path definitions on social interactions have properly reflected these features. In this work, we introduce a new distance measure in multiplex networks based on the concept of Pareto efficiency taking both heterogeneity and weighted nature of relations into account. We then model the problem of finding the whole set of paths as a form of multiple objective decision making and propose an exact algorithm for that. The method is evaluated on five real-world datasets to test the impact of considering weights and multiplexity in the resulting shortest paths. As an application to find the most influential nodes, we redefine the concept of betweenness centrality based on the proposed shortest paths and evaluate it on a real-world dataset from two-layer trade relation among countries between years 2000 and 2015.
| S-EPMC5438413 | biostudies-literature
Project description:Clustering is a technique to analyze empirical data, with a major application for biomedical research. Essentially, clustering finds groups of related points in a dataset. However, results depend on both metrics for point-to-point similarity and rules for point-to-group association. Non-appropriate metrics and rules can lead to artifacts, especially in case of multiple groups with heterogeneous structure. In this work, we propose a clustering algorithm that evaluates the properties of paths between points (rather than point-to-point similarity) and solves a global optimization problem, finding solutions not obtainable by methods relying on local choices. Moreover, our algorithm is trainable. Hence, it can be adapted and adopted for specific datasets and applications by providing examples of valid and invalid paths to train a path classifier. We demonstrate its applicability to identify heterogeneous groups in challenging synthetic datasets, segment highly nonconvex immune cells in confocal microscopy images, and classify arrhythmic heartbeats in electrocardiographic signals.
| S-EPMC7051829 | biostudies-literature
Project description:Motivation:We introduce a formulation for the general task of finding diverse shortest paths between two end-points. Our approach is not linked to a specific biological problem and can be applied to a large variety of images thanks to its generic implementation as a user-friendly ImageJ/Fiji plugin. It relies on the introduction of additional layers in a Viterbi path graph, which requires slight modifications to the standard Viterbi algorithm rules. This layered graph construction allows for the specification of various constraints imposing diversity between solutions. Results:The software allows obtaining a collection of diverse shortest paths under some user-defined constraints through a convenient and user-friendly interface. It can be used alone or be integrated into larger image analysis pipelines. Availability and implementation:http://bigwww.epfl.ch/algorithms/diversepathsj. Contact:michael.unser@epfl.ch or fred.hamprecht@iwr.uni-heidelberg.de. Supplementary information:Supplementary data are available at Bioinformatics online.
| S-EPMC5860364 | biostudies-literature
Project description:Numerous centrality measures have been developed to quantify the importances of nodes in time-independent networks, and many of them can be expressed as the leading eigenvector of some matrix. With the increasing availability of network data that changes in time, it is important to extend such eigenvector-based centrality measures to time-dependent networks. In this paper, we introduce a principled generalization of network centrality measures that is valid for any eigenvector-based centrality. We consider a temporal network with N nodes as a sequence of T layers that describe the network during different time windows, and we couple centrality matrices for the layers into a supra-centrality matrix of size NT × NT whose dominant eigenvector gives the centrality of each node i at each time t. We refer to this eigenvector and its components as a joint centrality, as it reflects the importances of both the node i and the time layer t. We also introduce the concepts of marginal and conditional centralities, which facilitate the study of centrality trajectories over time. We find that the strength of coupling between layers is important for determining multiscale properties of centrality, such as localization phenomena and the time scale of centrality changes. In the strong-coupling regime, we derive expressions for time-averaged centralities, which are given by the zeroth-order terms of a singular perturbation expansion. We also study first-order terms to obtain first-order-mover scores, which concisely describe the magnitude of nodes' centrality changes over time. As examples, we apply our method to three empirical temporal networks: the United States Ph.D. exchange in mathematics, costarring relationships among top-billed actors during the Golden Age of Hollywood, and citations of decisions from the United States Supreme Court.
| S-EPMC5643020 | biostudies-literature
Project description:We present a framework to simulate SIR processes on networks using weighted shortest paths. Our framework maps the SIR dynamics to weights assigned to the edges of the network, which can be done for Markovian and non-Markovian processes alike. The weights represent the propagation time between the adjacent nodes for a particular realization. We simulate the dynamics by constructing an ensemble of such realizations, which can be done by using a Markov Chain Monte Carlo method or by direct sampling. The former provides a runtime advantage when realizations from all possible sources are computed as the weighted shortest paths can be re-calculated more efficiently. We apply our framework to three empirical networks and analyze the expected propagation time between all pairs of nodes. Furthermore, we have employed our framework to perform efficient source detection and to improve strategies for time-critical vaccination.
| S-EPMC5920074 | biostudies-literature
Project description:Genome-wide association studies (GWASs) commonly use marginal association tests for each single-nucleotide polymorphism (SNP). Because these tests treat SNPs as independent, their power will be suboptimal for detecting SNPs hidden by linkage disequilibrium (LD). One way to improve power is to use a multiple regression model. However, the large number of SNPs preclude simultaneous fitting with multiple regression, and subset regression is infeasible because of an exorbitant number of candidate subsets. We therefore propose a new method for detecting hidden SNPs having significant yet weak marginal association in a multiple regression model. Our method begins by constructing a bidirected graph locally around each SNP that demonstrates a moderately sized marginal association signal, the focal SNPs. Vertexes correspond to SNPs, and adjacency between vertexes is defined by an LD measure. Subsequently, the method collects from each graph all shortest paths to the focal SNP. Finally, for each shortest path the method fits a multiple regression model to all the SNPs lying in the path and tests the significance of the regression coefficient corresponding to the terminal SNP in the path. Simulation studies show that the proposed method can detect susceptibility SNPs hidden by LD that go undetected with marginal association testing or with existing multivariate methods. When applied to real GWAS data from the Alzheimer's Disease Neuroimaging Initiative (ADNI), our method detected two groups of SNPs: one in a region containing the apolipoprotein E (APOE) gene, and another in a region close to the semaphorin 5A (SEMA5A) gene.
| S-EPMC5849262 | biostudies-literature
Project description:MotivationAdverse events resulting from drug-drug interactions (DDI) pose a serious health issue. The ability to automatically extract DDIs described in the biomedical literature could further efforts for ongoing pharmacovigilance. Most of neural networks-based methods typically focus on sentence sequence to identify these DDIs, however the shortest dependency path (SDP) between the two entities contains valuable syntactic and semantic information. Effectively exploiting such information may improve DDI extraction.ResultsIn this article, we present a hierarchical recurrent neural networks (RNNs)-based method to integrate the SDP and sentence sequence for DDI extraction task. Firstly, the sentence sequence is divided into three subsequences. Then, the bottom RNNs model is employed to learn the feature representation of the subsequences and SDP, and the top RNNs model is employed to learn the feature representation of both sentence sequence and SDP. Furthermore, we introduce the embedding attention mechanism to identify and enhance keywords for the DDI extraction task. We evaluate our approach using the DDI extraction 2013 corpus. Our method is competitive or superior in performance as compared with other state-of-the-art methods. Experimental results show that the sentence sequence and SDP are complementary to each other. Integrating the sentence sequence with SDP can effectively improve the DDI extraction performance.Availability and implementationThe experimental data is available at https://github.com/zhangyijia1979/hierarchical-RNNs-model-for-DDI-extraction.Contactzhyj@dlut.edu.cn or michel.dumontier@maastrichtuniversity.nl.Supplementary informationSupplementary data are available at Bioinformatics online.
| S-EPMC6030919 | biostudies-literature
Project description:The recently emerging Influenza A/H7N9 virus is reported to be able to infect humans and cause mortality. However, viral and host factors associated with the infection are poorly understood. It is suggested by the "guilt by association" rule that interacting proteins share the same or similar functions and hence may be involved in the same pathway. In this study, we developed a computational method to identify Influenza A/H7N9 virus infection-related human genes based on this rule from the shortest paths in a virus-human protein interaction network. Finally, we screened out the most significant 20 human genes, which could be the potential infection related genes, providing guidelines for further experimental validation. Analysis of the 20 genes showed that they were enriched in protein binding, saccharide or polysaccharide metabolism related pathways and oxidative phosphorylation pathways. We also compared the results with those from human rhinovirus (HRV) and respiratory syncytial virus (RSV) by the same method. It was indicated that saccharide or polysaccharide metabolism related pathways might be especially associated with the H7N9 infection. These results could shed some light on the understanding of the virus infection mechanism, providing basis for future experimental biology studies and for the development of effective strategies for H7N9 clinical therapies.
| S-EPMC4052153 | biostudies-literature
Project description:MOTIVATION: Inferring the underlying regulatory pathways within a gene interaction network is a fundamental problem in Systems Biology to help understand the complex interactions and the regulation and flow of information within a system-of-interest. Given a weighted gene network and a gene in this network, the goal of an inference algorithm is to identify the potential regulatory pathways passing through this gene. RESULTS: In a departure from previous approaches that largely rely on the random walk model, we propose a novel single-source k-shortest paths based algorithm to address this inference problem. An important element of our approach is to explicitly account for and enhance the diversity of paths discovered by our algorithm. The intuition here is that diversity in paths can help enrich different functions and thereby better position one to understand the underlying system-of-interest. Results on the yeast gene network demonstrate the utility of the proposed approach over extant state-of-the-art inference algorithms. Beyond utility, our algorithm achieves a significant speedup over these baselines. AVAILABILITY: All data and codes are freely available upon request.
| S-EPMC3371844 | biostudies-literature