Label-based routing for a family of small-world Farey graphs.
Ontology highlight
ABSTRACT:
SUBMITTER: Zhai Y
PROVIDER: S-EPMC4863731 | biostudies-other | 2016
REPOSITORIES: biostudies-other
Similar Datasets
Project description:The brain's connectivity is locally dense and globally sparse, forming a small-world graph-a principle prevalent in the evolution of various species, suggesting a universal solution for efficient information routing. However, current artificial neural network circuit architectures do not fully embrace small-world neural network models. Here, we present the neuromorphic Mosaic: a non-von Neumann systolic architecture employing distributed memristors for in-memory computing and in-memory routing, efficiently implementing small-world graph topologies for Spiking Neural Networks (SNNs). We've designed, fabricated, and experimentally demonstrated the Mosaic's building blocks, using integrated memristors with 130 nm CMOS technology. We show that thanks to enforcing locality in the connectivity, routing efficiency of Mosaic is at least one order of magnitude higher than other SNN hardware platforms. This is while Mosaic achieves a competitive accuracy in a variety of edge benchmarks. Mosaic offers a scalable approach for edge systems based on distributed spike-based computing and in-memory routing.
| S-EPMC10761708 | biostudies-literature
Project description:The increasing demands in security and reliability of infrastructures call for the optimal design of their embedded complex networks topologies. The following question then arises: what is the optimal layout to fulfill best all the demands? Here we present a general solution for this problem with scale-free networks, like the Internet and airline networks. Precisely, we disclose a way to systematically construct networks which are robust against random failures. Furthermore, as the size of the network increases, its shortest path becomes asymptotically invariant and the density of links goes to zero, making it ultra-small world and highly sparse, respectively. The first property is ideal for communication and navigation purposes, while the second is interesting economically. Finally, we show that some simple changes on the original network formulation can lead to an improved topology against malicious attacks.
| S-EPMC4357991 | biostudies-other
Project description:The hypothesis, that cortical dynamics operates near criticality also suggests, that it exhibits universal critical exponents which marks the Kuramoto equation, a fundamental model for synchronization, as a prime candidate for an underlying universal model. Here, we determined the synchronization behavior of this model by solving it numerically on a large, weighted human connectome network, containing 836733 nodes, in an assumed homeostatic state. Since this graph has a topological dimension d?<?4, a real synchronization phase transition is not possible in the thermodynamic limit, still we could locate a transition between partially synchronized and desynchronized states. At this crossover point we observe power-law-tailed synchronization durations, with ?t???1.2(1), away from experimental values for the brain. For comparison, on a large two-dimensional lattice, having additional random, long-range links, we obtain a mean-field value: ?t???1.6(1). However, below the transition of the connectome we found global coupling control-parameter dependent exponents 1?<??t???2, overlapping with the range of human brain experiments. We also studied the effects of random flipping of a small portion of link weights, mimicking a network with inhibitory interactions, and found similar results. The control-parameter dependent exponent suggests extended dynamical criticality below the transition point.
| S-EPMC6928153 | biostudies-literature
Project description:The 1-2-3 Conjecture states that every nice graph G (without component isomorphic to We study proper labellings of graphs with the extra requirement that the sum of assigned labels must be as small as possible. That is, given a graph G, we are looking for a locally irregular multigraph We investigate several aspects of this problem. We prove that the problem of designing proper labellings with minimum label sum is
| S-EPMC7254921 | biostudies-literature
Project description:More than 60 Rab GTPases exist in the human genome to regulate vesicle trafficking between organelles. Rab GTPases are members of the Ras GTPase superfamily that broadly control budding, uncoating, motility and fusion of vesicles in most cell types. Rab proteins interconvert between active, GTP-bound form and inactive, GDP-bound form. In their active conformation, they interact with various effector molecules to carry out diverse functions. Rab GTPases are usually small containing only a GTPase domain with a C-terminal prenylation site for membrane anchoring. Recently, we identified a large G protein, CRACR2A (CRAC channel regulator 2A), which uncovers novel functions of Rab GTPases. First, CRACR2A encodes a large Rab GTPase containing multiple functional domains contrary to small Rab GTPases. Second, CRACR2A plays an unexpected role in regulating intracellular signaling pathways important for T cell activation, unlike the canonical role of small Rab GTPases. Vesicles containing CRACR2A bud out from the proximal Golgi area and translocate into the immunological synapse to activate these signaling pathways. Third, instead of recycling, CRACR2A is consumed by a unidirectional pathway. These events are sequentially regulated by prenylation, GTP binding, protein interaction with a signaling adaptor Vav1, and degradation. Together, our findings reveal a novel function of a large Rab GTPase in intracellular signaling pathways, which may be shared by other large Rab GTPases, Rab44 and Rab45.
| S-EPMC5331893 | biostudies-literature
Project description:We have exhaustively enumerated all simple, connected graphs of a finite order and have computed a selection of invariants over this set. Integer sequences were constructed from these invariants and checked against the Online Encyclopedia of Integer Sequences (OEIS). 141 new sequences were added and six sequences were extended. From the graph database, we were able to programmatically suggest relationships among the invariants. It will be shown that we can readily visualize any sequence of graphs with a given criteria. The code has been released as an open-source framework for further analysis and the database was constructed to be extensible to invariants not considered in this work.
| S-EPMC4809059 | biostudies-literature
Project description:Graph models are standard for representing mutual relationships between sets of entities. Often, graphs deal with a large number of entities with a small number of connections (e.g. social media relationships, infectious disease spread). The distances or similarities between such large graphs are known to be well established by the Graphlet Correlation Distance (GCD). This paper deals with small graphs (with potentially high densities of connections) that have been somewhat neglected in the literature but that concern important fora like sociology, ecology and fisheries, to mention some examples. First, based on numerical experiments, we study the conditions under which Erdős-Rényi, Fitness Scale-Free, Watts-Strogatz small-world and geometric graphs can be distinguished by a specific GCD measure based on 11 orbits, the GCD11. This is done with respect to the density and the order (i.e. the number of nodes) of the graphs when comparing graphs with the same and different orders. Second, we develop a randomization statistical test based on the GCD11 to compare empirical graphs to the four possible null models used in this analysis and apply it to a fishing case study where graphs represent pairwise proximity between fishing vessels. The statistical test rules out independent pairing within the fleet studied which is a standard assumption in fisheries. It also illustrates the difficulty to identify similarities between real-world small graphs and graph models.
| S-EPMC9931116 | biostudies-literature
Project description:MotivationThe size of a genome graph-the space required to store the nodes, node labels and edges-affects the efficiency of operations performed on it. For example, the time complexity to align a sequence to a graph without a graph index depends on the total number of characters in the node labels and the number of edges in the graph. This raises the need for approaches to construct space-efficient genome graphs.ResultsWe point out similarities in the string encoding mechanisms of genome graphs and the external pointer macro (EPM) compression model. We present a pair of linear-time algorithms that transform between genome graphs and EPM-compressed forms. The algorithms result in an upper bound on the size of the genome graph constructed in terms of an optimal EPM compression. To further reduce the size of the genome graph, we propose the source assignment problem that optimizes over the equivalent choices during compression and introduce an ILP formulation that solves that problem optimally. As a proof-of-concept, we introduce RLZ-Graph, a genome graph constructed based on the relative Lempel-Ziv algorithm. Using RLZ-Graph, across all human chromosomes, we are able to reduce the disk space to store a genome graph on average by 40.7% compared to colored compacted de Bruijn graphs constructed by Bifrost under the default settings. The RLZ-Graph scales well in terms of running time and graph sizes with an increasing number of human genome sequences compared to Bifrost and variation graphs produced by VGtoolkit.AvailabilityThe RLZ-Graph software is available at: https://github.com/Kingsford-Group/rlzgraph.Supplementary informationSupplementary data are available at Bioinformatics online.
| S-EPMC8275343 | biostudies-literature
Project description:Real networks, including biological networks, are known to have the small-world property, characterized by a small "diameter", which is defined as the average minimal path length between all pairs of nodes in a network. Because random networks also have short diameters, one may predict that the diameter of a real network should be even shorter than its random expectation, because having shorter diameters potentially increases the network efficiency such as minimizing transition times between metabolic states in the context of metabolic networks. Contrary to this expectation, we here report that the observed diameter is greater than the random expectation in every real network examined, including biological, social, technological, and linguistic networks. Simulations show that a modest enlargement of the diameter beyond its expectation allows a substantial increase of the network modularity, which is present in all real networks examined. Hence, short diameters appear to be sacrificed for high modularities, suggesting a tradeoff between network efficiency and advantages offered by modularity (e.g., multi-functionality, robustness, and/or evolvability).
| S-EPMC2682646 | biostudies-literature
Project description:Measuring protein structural similarity attempts to establish a relationship of equivalence between polymer structures based on their conformations. In several recent studies, researchers have explored protein-graph remodeling, instead of looking a minimum superimposition for pairwise proteins. When graphs are used to represent structured objects, the problem of measuring object similarity become one of computing the similarity between graphs. Graph theory provides an alternative perspective as well as efficiency. Once a protein graph has been created, its structural stability must be verified. Therefore, a criterion is needed to determine if a protein graph can be used for structural comparison. In this paper, we propose a measurement for protein graph remodeling based on graph entropy. We extend the concept of graph entropy to determine whether a graph is suitable for representing a protein. The experimental results suggest that when applied, graph entropy helps a conformational on protein graph modeling. Furthermore, it indirectly contributes to protein structural comparison if a protein graph is solid.
| S-EPMC4271566 | biostudies-literature