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.展开更多
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.展开更多
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 s...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.展开更多
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 regio...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.展开更多
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 t...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.展开更多
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 mech...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.展开更多
基金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 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 work was supported by the Serbian Ministry of Science and Education(project TR-32022)by companies Telekom Srbija and Informatika.
文摘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.
基金partially supported by the Doctoral Programming Research Fund of Higher Education, Chinese Ministry of Education (No. 20110205110010)
文摘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.
基金supported by the Anhui Provincial Natural Science Foundation(2008085MF195)the National Natural Science Foundation of China(62072422)Zhejiang Lab(2019NB0AB03).
文摘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.
基金supported by the National Natural Science Foundation of China (61271199)
文摘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.