Quantum navigation and ranking in complex networks.
Ontology highlight
ABSTRACT:
SUBMITTER: Sanchez-Burillo E
PROVIDER: S-EPMC3428603 | biostudies-other | 2012
REPOSITORIES: biostudies-other
Similar Datasets
Project description:Anomalous random walks having long-range jumps are a critical branch of dynamical processes on networks, which can model a number of search and transport processes. However, traditional measurements based on mean first passage time are not useful as they fail to characterize the cost associated with each jump. Here we introduce a new concept of mean first traverse distance (MFTD) to characterize anomalous random walks that represents the expected traverse distance taken by walkers searching from source node to target node, and we provide a procedure for calculating the MFTD between two nodes. We use Lévy walks on networks as an example, and demonstrate that the proposed approach can unravel the interplay between diffusion dynamics of Lévy walks and the underlying network structure. Moreover, applying our framework to the famous PageRank search, we show how to inform the optimality of the PageRank search. The framework for analyzing anomalous random walks on complex networks offers a useful new paradigm to understand the dynamics of anomalous diffusion processes, and provides a unified scheme to characterize search and transport processes on networks.
| S-EPMC5120342 | biostudies-literature
Project description:Many networks are used to transfer information or goods, in other words, they are navigated. The larger the network, the more difficult it is to navigate efficiently. Indeed, information routing in the Internet faces serious scalability problems due to its rapid growth, recently accelerated by the rise of the Internet of Things. Large networks like the Internet can be navigated efficiently if nodes, or agents, actively forward information based on hidden maps underlying these systems. However, in reality most agents will deny to forward messages, which has a cost, and navigation is impossible. Can we design appropriate incentives that lead to participation and global navigability? Here, we present an evolutionary game where agents share the value generated by successful delivery of information or goods. We show that global navigability can emerge, but its complete breakdown is possible as well. Furthermore, we show that the system tends to self-organize into local clusters of agents who participate in the navigation. This organizational principle can be exploited to favor the emergence of global navigability in the system.
| S-EPMC5460226 | biostudies-other
Project description:Designing node influence ranking algorithms can provide insights into network dynamics, functions and structures. Increasingly evidences reveal that node's spreading ability largely depends on its neighbours. We introduce an iterative neighbourinformation gathering (Ing) process with three parameters, including a transformation matrix, a priori information and an iteration time. The Ing process iteratively combines priori information from neighbours via the transformation matrix, and iteratively assigns an Ing score to each node to evaluate its influence. The algorithm appropriates for any types of networks, and includes some traditional centralities as special cases, such as degree, semi-local, LeaderRank. The Ing process converges in strongly connected networks with speed relying on the first two largest eigenvalues of the transformation matrix. Interestingly, the eigenvector centrality corresponds to a limit case of the algorithm. By comparing with eight renowned centralities, simulations of susceptible-infected-removed (SIR) model on real-world networks reveal that the Ing can offer more exact rankings, even without a priori information. We also observe that an optimal iteration time is always in existence to realize best characterizing of node influence. The proposed algorithms bridge the gaps among some existing measures, and may have potential applications in infectious disease control, designing of optimal information spreading strategies.
| S-EPMC5259765 | biostudies-literature
Project description:Calculating the importance of influential nodes and ranking them based on their diffusion power is one of the open issues and critical research fields in complex networks. It is essential to identify an attribute that can compute and rank the diffusion power of nodes with high accuracy, despite the plurality of nodes and many relationships between them. Most methods presented only use one structural attribute to capture the influence of individuals, which is not entirely accurate in most networks. The reason is that network structures are disparate, and these methods will be inefficient by altering the network. A possible solution is to use more than one attribute to examine the characteristics aspect and address the issue mentioned. Therefore, this study presents a method for identifying and ranking node’s ability to spread information. The purpose of this study is to present a multi-attribute decision making approach for determining diffusion power and classification of nodes, which uses several local and semi-local attributes. Local and semi-local attributes with linear time complexity are used, considering different aspects of the network nodes. Evaluations performed on datasets of real networks demonstrate that the proposed method performs satisfactorily in allocating distinct ranks to nodes; moreover, as the infection rate of nodes increases, the accuracy of the proposed method increases.
| S-EPMC9704601 | biostudies-literature
Project description:Crystals arise as the result of the breaking of a spatial translation symmetry. Similarly, translation symmetries can also be broken in time so that discrete time crystals appear. Here, we introduce a method to describe, characterize, and explore the physical phenomena related to this phase of matter using tools from graph theory. The analysis of the graphs allows to visualizing time-crystalline order and to analyze features of the quantum system. For example, we explore in detail the melting process of a minimal model of a period-2 discrete time crystal and describe it in terms of the evolution of the associated graph structure. We show that during the melting process, the network evolution exhibits an emergent preferential attachment mechanism, directly associated with the existence of scale-free networks. Thus, our strategy allows us to propose a previously unexplored far-reaching application of time crystals as a quantum simulator of complex quantum networks.
| S-EPMC7567590 | biostudies-literature
Project description:Understanding the architectural subtleties of ecological networks, believed to confer them enhanced stability and robustness, is a subject of outmost relevance. Mutualistic interactions have been profusely studied and their corresponding bipartite networks, such as plant-pollinator networks, have been reported to exhibit a characteristic "nested" structure. Assessing the importance of any given species in mutualistic networks is a key task when evaluating extinction risks and possible cascade effects. Inspired in a recently introduced algorithm--similar in spirit to Google's PageRank but with a built-in non-linearity--here we propose a method which--by exploiting their nested architecture--allows us to derive a sound ranking of species importance in mutualistic networks. This method clearly outperforms other existing ranking schemes and can become very useful for ecosystem management and biodiversity preservation, where decisions on what aspects of ecosystems to explicitly protect need to be made.
| S-EPMC4313099 | biostudies-other
Project description:Despite its importance for public transportation, communication within organizations or the general understanding of organized knowledge, our understanding of how human individuals navigate complex networked systems is still limited owing to the lack of datasets recording a sufficient amount of navigation paths of individual humans. Here, we analyse 10587 paths recorded from 259 human subjects when navigating between nodes of a complex word-morph network. We find a clear presence of systematic detours organized around individual hierarchical scaffolds guiding navigation. Our dataset is the first enabling the visualization and analysis of scaffold hierarchies whose presence and role in supporting human navigation is assumed in existing navigational models. By using an information-theoretic argumentation, we argue that taking short detours following the hierarchical scaffolds is a clear sign of human subjects simplifying the interpretation of the complex networked system by an order of magnitude. We also discuss the role of these scaffolds in the phases of learning to navigate a network from scratch.
| S-EPMC6981150 | biostudies-literature
Project description:We propose a characterization of complex networks, based on the potential of an associated Schrödinger equation. The potential is designed so that the energy spectrum of the Schrödinger equation coincides with the graph spectrum of the normalized Laplacian. Crucial information is retained in the reconstructed potential, which provides a compact representation of the properties of the network structure. The median potential over several random network realizations, which we call ensemble potential, is fitted via a Landau-like function, and its length scale is found to diverge as the critical connection probability is approached from above. The ruggedness of the ensemble potential profile is quantified by using the Higuchi fractal dimension, which displays a maximum at the critical connection probability. This demonstrates that this technique can be successfully employed in the study of random networks, as an alternative indicator of the percolation phase transition. We apply the proposed approach to the investigation of real-world networks describing infrastructures (US power grid). Curiously, although no notion of phase transition can be given for such networks, the fractality of the ensemble potential displays signatures of criticality. We also show that standard techniques (such as the scaling features of the largest connected component) do not detect any signature or remnant of criticality.
| S-EPMC7592062 | biostudies-literature
Project description:Understanding the mechanisms of neural communication in large-scale brain networks remains a major goal in neuroscience. We investigated whether navigation is a parsimonious routing model for connectomics. Navigating a network involves progressing to the next node that is closest in distance to a desired destination. We developed a measure to quantify navigation efficiency and found that connectomes in a range of mammalian species (human, mouse, and macaque) can be successfully navigated with near-optimal efficiency (>80% of optimal efficiency for typical connection densities). Rewiring network topology or repositioning network nodes resulted in 45-60% reductions in navigation performance. We found that the human connectome cannot be progressively randomized or clusterized to result in topologies with substantially improved navigation performance (>5%), suggesting a topological balance between regularity and randomness that is conducive to efficient navigation. Navigation was also found to (i) promote a resource-efficient distribution of the information traffic load, potentially relieving communication bottlenecks, and (ii) explain significant variation in functional connectivity. Unlike commonly studied communication strategies in connectomics, navigation does not mandate assumptions about global knowledge of network topology. We conclude that the topology and geometry of brain networks are conducive to efficient decentralized communication.
| S-EPMC6004443 | biostudies-literature
Project description:Link prediction methods use patterns in known network data to infer which connections may be missing. Previous work has shown that continuous-time quantum walks can be used to represent path-based link prediction, which we further study here to develop a more optimized quantum algorithm. Using a sampling framework for link prediction, we analyze the query access to the input network required to produce a certain number of prediction samples. Considering both well-known classical path-based algorithms using powers of the adjacency matrix as well as our proposed quantum algorithm for path-based link prediction, we argue that there is a polynomial quantum advantage on the dependence on N, the number of nodes in the network. We further argue that the complexity of our algorithm, although sub-linear in N, is limited by the complexity of performing a quantum simulation of the network's adjacency matrix, which may prove to be an important problem in the development of quantum algorithms for network science in general.
| S-EPMC10781705 | biostudies-literature