Predicting Arabidopsis thaliana Gene Function by Transitiving Co-expression in Shortest-path

The present paper predicted the function of unknow genes by analyzing the co-expression data of Arabidopsis thaliana from biological pathway based on the shortest-path algorithm. This paper proposed that transitive co-expression among genes can be used as an important attribute to link genes of the same biological pathway. The genes from the same biological pathway with similar functions are strongly correlated in expression. Moreover,the function of unknown genes can be predicted by the known genes where they are strongly correlated in expression lying on the same shortest-path from the biological pathway. Analyzing the Arabidopsis thaliana from the biological pathway,this study showed that this method can reliably reveal function of the unknown Arabidopsis thaliana genes and the approach of predicting gene function by transitiving co-expression in shortest-path is feasible and effective.

A Fast Method for Shortest-Path Cover Identification in Large Complex Networks

Fast identifying the amount of information that can be gained by measuring a network via shortest-paths is one of the fundamental problem for networks exploration and monitoring.However,the existing methods are time-consuming for even moderate-scale networks.In this paper,we present a method for fast shortest-path cover identification in both exact and approximate scenarios based on the relationship between the identification and the shortest distance queries.The effectiveness of the proposed method is validated through synthetic and real-world networks.The experimental results show that our method is 105 times faster than the existing methods and can solve the shortest-path cover identification in a few seconds for large-scale networks with millions of nodes and edges.

Using Link Analysis Technique with a Modified Shortest-Path Algorithm to Fight Money Laundering

Effective link analysis techniques are needed to help law enforcement and intelligence agencies fight money laundering. This paper presents a link analysis technique that uses a modified shortest-path algorithms to identify the strongest association paths between entities in a money laundering network. Based on two-tree Dijkstra and Priority＇First-Search （PFS） algorithm, a modified algorithm is presented. To apply the algorithm, a network representation transformation is made first.

Optimal parallel algorithm for shortest-paths problem on interval graphs

This paper presents an efficient parallel algorithm for the shortest-path problem in interval graph for computing shortest-paths in a weighted interval graph that runs in O(n) time with n intervals in a graph. A linear processor CRCW algorithm for determining the shortest-paths in an interval graphs is given.

Fast and scalable routing protocols for data center networks

Data center networks may comprise tens or hundreds of thousands of nodes,and,naturally,suffer from frequent software and hardware failures as well as link congestions.Packets are routed along the shortest paths with sufficient resources to facilitate efficient network utilization and minimize delays.In such dynamic networks,links frequently fail or get congested,making the recalculation of the shortest paths a computationally intensive problem.Various routing protocols were proposed to overcome this problem by focusing on network utilization rather than speed.Surprisingly,the design of fast shortest-path algorithms for data centers was largely neglected,though they are universal components of routing protocols.Moreover,parallelization techniques were mostly deployed for random network topologies,and not for regular topologies that are often found in data centers.The aim of this paper is to improve scalability and reduce the time required for the shortest-path calculation in data center networks by parallelization on general-purpose hardware.We propose a novel algorithm that parallelizes edge relaxations as a faster and more scalable solution for popular data center topologies.

The Structure of the Optimal Solution Set on the Shortest Paths for Networks

Abstract： The shortest path problem in a network G is to find shortest paths between some specified source vertices and terminal vertices when the lengths of edges are given. The structure of the optimal solutions set on the shortest paths is studied in this paper. First, the conditions of having unique shortest path between two distinguished vertices 8 and t in a network G are discussed; Second, the structural properties of 2-transformation ^-G graph G on the shortest-paths for G are presented heavily.

3-D multi-parameter type traveltime tomography in a spherical coordinate frame: comparison of double and triple class simultaneous inversions

It is now common practice to perform simultaneous traveltime inversion for the velocity field and the reflector geometry in reflection/refraction tomography, or the velocity field and the hypocenter locations in regional earthquake tomography, but seldom are all three classes of model parameters updated simultaneously. This is mainly due to the trade-off between the different types of model parameters and the lack of different seismic phases to constrain the model parameters. Using a spherical-coordinate ray tracing algorithm for first and later（primary reflected） arrival tracing algorithm in combination with a popular linearized inversion solver, it is possible to simultaneously recover the three classes of model parameters in regional or global tomographic studies. In this paper we incorporate the multistage irregular shortest-path ray tracing algorithm（in a spherical coordinate system） with a subspace inversion solver to formulate a simultaneous inversion algorithm for triple model parameters updating using direct and later arrival time information.Comparison tests for two sets of data（noise free and added noise） indicate that the new triple-class parameter inversion algorithm is capable of obtaining nearly the same results as the double-class parameter inversion scheme. Furthermore,the proposed multi-parameter type inversion method is not sensitive to a modest level of picking error in the traveltime data, and also performs well with a relatively large uncertainty in earthquake hypocentral locations. This shows it to be a feasible and promising approach in regional or global tomographic applications.

Efficient fastest-path computations for road maps

In the age of real-time online traffic information and GPS-enabled devices,fastest-path computations between two points in a road network modeled as a directed graph,where each directed edge is weighted by a“travel time”value,are becoming a standard feature of many navigation-related applications.To support this,very efficient computation of these paths in very large road networks is critical.Fastest paths may be computed as minimal-cost paths in a weighted directed graph,but traditional minimal-cost path algorithms based on variants of the classical Dijkstra algorithm do not scale well,as in the worst case they may traverse the entire graph.A common improvement,which can dramatically reduce the number of graph vertices traversed,is the A*algorithm,which requires a good heuristic lower bound on the minimal cost.We introduce a simple,but very effective,heuristic function based on a small number of values assigned to each graph vertex.The values are based on graph separators and are computed efficiently in a preprocessing stage.We present experimental results demonstrating that our heuristic provides estimates of the minimal cost superior to those of other heuristics.Our experiments show that when used in the A*algorithm,this heuristic can reduce the number of vertices traversed by an order of magnitude compared to other heuristics.

Online social network model with renewal and accelerated growth

Based on observation of the growing mechanism in Twitter-like online social networks, an online social network （OSN） evolution model was proposed, a renewal mechanism for the old nodes and an accelerated growth mechanism was introduced for the new nodes, comparing with the native copying model. Topological characteristics of the generated networks, such as degree distribution, average shortest-path length and clustering coefficient, are analyzed and numerized. These properties are validated with some crawled datasets of real online social networks.