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-c...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.展开更多
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...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.展开更多
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 id...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.展开更多
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 linea...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.展开更多
We consider the problem of detecting the community structure in a complex network, groups of nodes with a higher-than-average density of edges connecting them. In this paper we use the simulated annealing strategy to ...We consider the problem of detecting the community structure in a complex network, groups of nodes with a higher-than-average density of edges connecting them. In this paper we use the simulated annealing strategy to maximize the modularity, which has been indicated as a robust benefit function, associating with a shortest-path-based k-means iterative procedure for network partition. The proposed algorithm can not only find the communities, but also identify the nodes which occupy central positions under the metric of the shortest path within the communities to which they belong. The optimal number of communities can be automatically determined without any prior knowledge about the network structure. The applications to both artificial and real-world networks demonstrate the effectiveness of our algorithm.展开更多
基金This work was supported in part by the National Natural Science Foundation of China(61471101)the National Natural Science Foundation of China(U1736205).
文摘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.
基金Supported by Shanghai Municipal Education Committee Educationand Scientific Research (Grant No. 07ZZ60)~~
文摘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.
基金Supported bythe National Tenth Five-Year PlanforScientific and Technological Development of China (2001BA102A06-11)
文摘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.
文摘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.
基金Supported by the National Natural Science Foundation of China(Grant No.10771085)
文摘We consider the problem of detecting the community structure in a complex network, groups of nodes with a higher-than-average density of edges connecting them. In this paper we use the simulated annealing strategy to maximize the modularity, which has been indicated as a robust benefit function, associating with a shortest-path-based k-means iterative procedure for network partition. The proposed algorithm can not only find the communities, but also identify the nodes which occupy central positions under the metric of the shortest path within the communities to which they belong. The optimal number of communities can be automatically determined without any prior knowledge about the network structure. The applications to both artificial and real-world networks demonstrate the effectiveness of our algorithm.
