Browse
Submit Data
Databases
API
Help

Dataset Information

18 Views

0 Connections

0 Citations

0 Reanalyses

0 Downloads

Omics score: 0

Bounded Asymmetry in Road Networks.

ABSTRACT: Road networks are a classical stage for applications in network science and graph theory. Meanwhile, many combinatorial problems that arise in road networks are computationally intractable. Thus, an attractive way of tackling them is through efficient heuristics with provable performance guarantees, better known as approximation algorithms. This motivates the intersection of algorithm design with the aforementioned fields. Specifically, identifying measures that characterize graphs and exploiting them in the design of algorithms may yield practical heuristics with rigorous mathematical justification. Herein, we propose a new graph measure, namely the asymmetry factor ?_G of a directed graph G, with immediate algorithmic results via a symmetrization procedure and the black box use of approximation algorithms for symmetric graphs. Crucially, we analyze the asymmetry factors of the road networks from a diverse set of twelve cities, providing empirical evidence that road networks exhibit low bounded asymmetry and thereby justifying the practical use of algorithms for symmetric graphs.

SUBMITTER: Martinez Mori JC

PROVIDER: S-EPMC6697698 | biostudies-literature | 2019 Aug

REPOSITORIES: biostudies-literature

ACCESS DATA

Json Xml

Publications

Bounded Asymmetry in Road Networks.

Martínez Mori Juan C JC Samaranayake Samitha S

Scientific reports 20190816 1

Road networks are a classical stage for applications in network science and graph theory. Meanwhile, many combinatorial problems that arise in road networks are computationally intractable. Thus, an attractive way of tackling them is through efficient heuristics with provable performance guarantees, better known as approximation algorithms. This motivates the intersection of algorithm design with the aforementioned fields. Specifically, identifying measures that characterize graphs and exploitin ...[more]

PMID: 31420564

Similar Datasets

The angular nature of road networks.

Project description:Road networks are characterised by several structural and geometrical properties. The topological structure determines partially the hierarchical arrangement of roads, but since these are networks that are spatially constrained, geometrical properties play a fundamental role in determining the network's behaviour, characterising the influence of each of the street segments on the system. In this work, we apply percolation theory to the UK's road network using the relative angle between street segments as the occupation probability. The appearance of the spanning cluster is marked by a phase transition, indicating that the system behaves in a critical way. Computing Shannon's entropy of the cluster sizes, different stages of the percolation process can be discerned, and these indicate that roads integrate to the giant cluster in a hierarchical manner. This is used to construct a hierarchical index that serves to classify roads in terms of their importance. The obtained classification is in very good correspondence with the official designations of roads. This methodology hence provides a framework to consistently extract the main skeleton of an urban system and to further classify each road in terms of its hierarchical importance within the system.

| S-EPMC5487334 | biostudies-literature

Encapsulating urban traffic rhythms into road networks.

Project description:Using road GIS (geographical information systems) data and travel demand data for two U.S. urban areas, the dynamical driver sources of each road segment were located. A method to target road clusters closely related to urban traffic congestion was then developed to improve road network efficiency. The targeted road clusters show different spatial distributions at different times of a day, indicating that our method can encapsulate dynamical travel demand information into the road networks. As a proof of concept, when we lowered the speed limit or increased the capacity of road segments in the targeted road clusters, we found that both the number of congested roads and extra travel time were effectively reduced. In addition, the proposed modeling framework provided new insights on the optimization of transport efficiency in any infrastructure network with a specific supply and demand distribution.

| S-EPMC3929915 | biostudies-literature

Elementary processes governing the evolution of road networks.

Project description:Urbanisation is a fundamental phenomenon whose quantitative characterisation is still inadequate. We report here the empirical analysis of a unique data set regarding almost 200 years of evolution of the road network in a large area located north of Milan (Italy). We find that urbanisation is characterised by the homogenisation of cell shapes, and by the stability throughout time of high-centrality roads which constitute the backbone of the urban structure, confirming the importance of historical paths. We show quantitatively that the growth of the network is governed by two elementary processes: (i) 'densification', corresponding to an increase in the local density of roads around existing urban centres and (ii) 'exploration', whereby new roads trigger the spatial evolution of the urbanisation front. The empirical identification of such simple elementary mechanisms suggests the existence of general, simple properties of urbanisation and opens new directions for its modelling and quantitative description.

| S-EPMC3291042 | biostudies-literature

Road networks predict human influence on Amazonian bird communities.

Project description:Road building can lead to significant deleterious impacts on biodiversity, varying from direct road-kill mortality and direct habitat loss associated with road construction, to more subtle indirect impacts from edge effects and fragmentation. However, little work has been done to evaluate the specific effects of road networks and biodiversity loss beyond the more generalized effects of habitat loss. Here, we compared forest bird species richness and composition in the municipalities of Santarém and Belterra in Pará state, eastern Brazilian Amazon, with a road network metric called 'roadless volume (RV)' at the scale of small hydrological catchments (averaging 3721 ha). We found a significant positive relationship between RV and both forest bird richness and the average number of unique species (species represented by a single record) recorded at each site. Forest bird community composition was also significantly affected by RV. Moreover, there was no significant correlation between RV and forest cover, suggesting that road networks may impact biodiversity independently of changes in forest cover. However, variance partitioning analysis indicated that RV has partially independent and therefore additive effects, suggesting that RV and forest cover are best used in a complementary manner to investigate changes in biodiversity. Road impacts on avian species richness and composition independent of habitat loss may result from road-dependent habitat disturbance and fragmentation effects that are not captured by total percentage habitat cover, such as selective logging, fire, hunting, traffic disturbance, edge effects and road-induced fragmentation.

| S-EPMC4213623 | biostudies-literature

Ocular Dominance and Functional Asymmetry in Visual Attention Networks.

Project description:PurposeThe dorsal attention network (DAN) and the ventral attention network (VAN) are known to support visual attention, but the influences of ocular dominance on the attention networks are unclear. We aimed to explore how visual cortical asymmetry of the attention networks correlate with neurophysiological oscillation and connectivity markers of attentional processes.MethodsAn oddball task with concentric circle stimuli of three different sizes (i.e., spot size of 5°, 20°, or 30° of visual angle) was used to vary task difficulty. Event-related oscillations and interareal communication were tested with an electroencephalogram-based visual evoked components as a function of ocular dominance in 30 healthy subjects.ResultsAccuracy rates were higher in the dominant eyes compared with the nondominant eyes. Compared with the nondominant eyes, the dominant eyes had higher theta, low-alpha, and low-beta powers and lower high-alpha powers within the nodes of VAN and DAN. Furthermore, visual information processed by the dominant and nondominant eye had different fates, that is, the dominant eyes mainly relied on theta and low-alpha connectivity within both the VAN and the DAN, whereas the nondominant eyes mainly relied on theta connectivity within the VAN and high-alpha connectivity within the DAN. The difference in accuracy rate between the two eyes was correlated with the low-alpha oscillations in the anterior DAN area and low-alpha connectivity of the left DAN.ConclusionsThe ocular dominance processing and interareal communication reveal a cortical asymmetry underlying attention, and this reflects a two-way modulatory mechanism within attention networks in the human brain.

| S-EPMC8039471 | biostudies-literature

Asymmetry between Activators and Deactivators in Functional Protein Networks.

Project description:Are "turn-on" and "turn-off" functions in protein-protein interaction networks exact opposites of each other? To answer this question, we implement a minimal model for the evolution of functional protein-interaction networks using a sequence-based mutational algorithm, and apply the model to study neutral drift in networks that yield oscillatory dynamics. We study the roles of activators and deactivators, two core components of oscillatory protein interaction networks, and find a striking asymmetry in the roles of activating and deactivating proteins, where activating proteins tend to be synergistic and deactivating proteins tend to be competitive.

| S-EPMC7311538 | biostudies-literature

Silk Road

Project description:Collection of isolated population coming from 8 countries of Central Asia

| PRJEB7469 | ENA

Local floods induce large-scale abrupt failures of road networks.

Project description:The adverse effect of climate change continues to expand, and the risks of flooding are increasing. Despite advances in network science and risk analysis, we lack a systematic mathematical framework for road network percolation under the disturbance of flooding. The difficulty is rooted in the unique three-dimensional nature of a flood, where altitude plays a critical role as the third dimension, and the current network-based framework is unsuitable for it. Here we develop a failure model to study the effect of floods on road networks; the result covers 90.6% of road closures and 94.1% of flooded streets resulting from Hurricane Harvey. We study the effects of floods on road networks in China and the United States, showing a discontinuous phase transition, indicating that a small local disturbance may lead to a large-scale systematic malfunction of the entire road network at a critical point. Our integrated approach opens avenues for understanding the resilience of critical infrastructure networks against floods.

| S-EPMC6520386 | biostudies-literature

Bio-ModelChecker: Using Bounded Constraint Satisfaction to Seamlessly Integrate Observed Behavior With Prior Knowledge of Biological Networks.

Project description:The in silico study and reverse engineering of regulatory networks has gained in recognition as an insightful tool for the qualitative study of biological mechanisms that underlie a broad range of complex illness. In the creation of reliable network models, the integration of prior mechanistic knowledge with experimentally observed behavior is hampered by the disparate nature and widespread sparsity of such measurements. The former challenges conventional regression-based parameter fitting while the latter leads to large sets of highly variable network models that are equally compliant with the data. In this paper, we propose a bounded Constraint Satisfaction (CS) based model checking framework for parameter set identification that readily accommodates partial records and the exponential complexity of this problem. We introduce specific criteria to describe the biological plausibility of competing multi-valued regulatory networks that satisfy all the constraints and formulate model identification as a multi-objective optimization problem. Optimization is directed at maximizing structural parsimony of the regulatory network by mitigating excessive control action selectivity while also favoring increased state transition efficiency and robustness of the network's dynamic response. The framework's scalability, computational time and validity is demonstrated on several well-established and well-studied biological networks.

| S-EPMC6443719 | biostudies-literature

DEMA: a distance-bounded energy-field minimization algorithm to model and layout biomolecular networks with quantitative features.

Project description:SummaryIn biology, graph layout algorithms can reveal comprehensive biological contexts by visually positioning graph nodes in their relevant neighborhoods. A layout software algorithm/engine commonly takes a set of nodes and edges and produces layout coordinates of nodes according to edge constraints. However, current layout engines normally do not consider node, edge or node-set properties during layout and only curate these properties after the layout is created. Here, we propose a new layout algorithm, distance-bounded energy-field minimization algorithm (DEMA), to natively consider various biological factors, i.e., the strength of gene-to-gene association, the gene's relative contribution weight and the functional groups of genes, to enhance the interpretation of complex network graphs. In DEMA, we introduce a parameterized energy model where nodes are repelled by the network topology and attracted by a few biological factors, i.e., interaction coefficient, effect coefficient and fold change of gene expression. We generalize these factors as gene weights, protein-protein interaction weights, gene-to-gene correlations and the gene set annotations-four parameterized functional properties used in DEMA. Moreover, DEMA considers further attraction/repulsion/grouping coefficient to enable different preferences in generating network views. Applying DEMA, we performed two case studies using genetic data in autism spectrum disorder and Alzheimer's disease, respectively, for gene candidate discovery. Furthermore, we implement our algorithm as a plugin to Cytoscape, an open-source software platform for visualizing networks; hence, it is convenient. Our software and demo can be freely accessed at http://discovery.informatics.uab.edu/dema.Supplementary informationSupplementary data are available at Bioinformatics online.

| S-EPMC9235497 | biostudies-literature

OmicsDI is part of the ELIXIR infrastructure

OmicsDI is an Elixir interoperability service. Learn more ›

OmicsDI Databases

PRIDE
PeptideAtlas
MassIVE
JPOST Repository
Physiome Model Repository

EGA
EVA
ENA
LINCS
PAXDB
Cell Collective

MetaboLights
Metabolomics Workbench
MetabolomeExpress
GNPS
BioModels
FAIRDOMHub

ArrayExpress
dbGaP
ExpressionAtlas
GEO
NODE

Information

Databases
Help
API
Contact us
Code on GitHub
Terms of use
Submit Data