A self-organizing shortest path finding strategy on complex networks

The shortcomings of traditional methods to find the shortest path are revealed, and a strategy of finding the self- organizing shortest path based on thermal flux diffusion on complex networks is presented. In our method, the shortest paths between the source node and the other nodes are found to be self-organized by comparing node temperatures. The computation complexity of the method scales linearly with the number of edges on underlying networks. The effects of the method on several networks, including a regular network proposed by Ravasz and Barabasi which is called the RB network, a real network, a random network proposed by Ravasz and Barabasi which is called the ER network and a scale-free network, are also demonstrated. Analytic and simulation results show that the method has a higher accuracy and lower computational complexity than the conventional methods.

Design and Implementation of Bidirectional Dijkstra Algorithm

Bidirectional Dijkstra algorithm whose time complexity is 8O(n~2) is proposed. The theory foundation is that the classical Dijkstra algorithm has not any directional feature during searching the shortest path. The algorithm takes advantage of the adjacent link and the mechanism of bidirectional search, that is, the algorithm processes the positive search from start point to destination point and the negative search from destination point to start point at the same time. Finally, combining with the practical application of route-planning algorithm in embedded real-time vehicle navigation system (ERTVNS), one example of its practical applications is given, analysis in theory and the experimental results show that compared with the Dijkstra algorithm, the new algorithm can reduce time complexity, and guarantee the searching precision, it satisfies the needs of ERTVNS.

A Shortest Path Algorithm for Multi-stage Network with Linear Parameter

In this paper, we give the shortest path algorithm for multi-stage network with a linear parameter, and study its complexity.

Predicting Resting-state Functional Connectivity With Efficient Structural Connectivity

The complex relationship between structural connectivity(SC) and functional connectivity(FC) of human brain networks is still a critical problem in neuroscience. In order to investigate the role of SC in shaping resting-state FC, numerous models have been proposed. Here, we use a simple dynamic model based on the susceptible-infected-susceptible(SIS) model along the shortest paths to predict FC from SC. Unlike the previous dynamic model based on SIS theory, we focus on the shortest paths as the principal routes to transmit signals rather than the empirical structural brain network. We first simplify the structurally connected network into an efficient propagation network according to the shortest paths and then combine SIS infection theory with the efficient network to simulate the dynamic process of human brain activity. Finally, we perform an extensive comparison study between the dynamic models embedded in the efficient network, the dynamic model embedded in the structurally connected network and dynamic mean field(DMF) model predicting FC from SC. Extensive experiments on two different resolution datasets indicate that i) the dynamic model simulated on the shortest paths can predict FC among both structurally connected and unconnected node pairs; ii) though there are fewer links in the efficient propagation network, the predictive power of FC derived from the efficient propagation network is better than the dynamic model simulated on a structural brain network; iii) in comparison with the DMF model,the dynamic model embedded in the shortest paths is found to perform better to predict FC.

Open Queueing Network Model of Shanghai Public Transportation Problem

In this paper, the open queueing network model is proposed for solving the problem of public transportation in cities. The vertices of the networks(i.e., the bus stops) are determined by means of the fuzzy clustering method. The arcs (i.e., the paths of the public transportation) can be set up by using the shortest path model in the time sense or the 0 1 integer programming method.Applying the statistics method, we can calculate the parameters(such as the passenger flow's distribution, passenger flow's transition probability, mean waiting time for the bus etc. ) of the public transportation network. In this paper, we suggest to divide the network into two or three stages to implement the public transportation system in the form of ``frog jumping' fast transfer and ``permeation' fast dispersion.Combining the computer simulation and the evaluation of the achievement and effect of public transportation system, we modify the model so as to solve the public transportation problem better.