Search results

Shortest path problem has always been a hot topic in the study of graph theory, because of its wide application field, extending from operational research to the disciplines of geography, automatic control, computer science and traffic. According to its concrete application, scholars in the relevant field have presented many algorithms, but most of them are solely improvements based on Dijkstra algorithm. The purpose of this paper is to enrich the kinds of (and improve the efficiency of) the shortest path algorithms.

This paper puts forward an improved calculation method of shortest path using cellular automata model, which is designed to search the shortest path from one node to another node. Cellular state set is adjusted with combination of breeding and mature states. Evolution rule is improved to enhance its parallelism. At the same time, recording manner of cellular state turnover is modified to record all information sources.

The result indicates that the improved algorithm is correct and more efficient, in that it could reduce the times of cellular state turnover; meanwhile, it can solve multi‐paths problem.

In this paper, cellular state set in exiting shortest path algorithm based on cellular automata theory is adjusted; evolution rule is improved; and recording manner of cellular state turnover is modified to record all information sources. All of which make the parallelism of this algorithm enhanced and the multi‐paths problem solved.

The purpose of this paper is to study a multiple-origin-multiple-destination variant of dynamic critical nodes detection problem (DCNDP) and dynamic critical links detection problem (DCLDP) in stochastic networks. DCNDP and DCLDP consist of identifying the subset of nodes and links, respectively, whose deletion maximizes the stochastic shortest paths between all origins–destinations pairs, in the graph modeling the transport network. The identification of such nodes (or links) helps to better control the road traffic and predict the necessary measures to avoid congestion.

A Markovian decision process is used to model the shortest path problem under dynamic traffic conditions. Effective algorithms to determine the critical nodes (links) while considering the dynamicity of the traffic network are provided. Also, sensitivity analysis toward capacity reduction for critical links is studied. Moreover, the complexity of the underlying algorithms is analyzed and the computational efficiency resulting from the decomposition operation of the network into communities is highlighted.

The numerical results demonstrate that the use of dynamic shortest path (time dependency) as a metric has a significant impact on the identification of critical nodes/links and the experiments conducted on real world networks highlight the importance of sensitive links to dynamically detect critical links and elaborate smart transport plans.

The research in this paper also revealed several challenges, which call for future investigations. First, the authors have restricted our experimentation to a small network where the only focus is on the model behavior, in the absence of historical data. The authors intend to extend this study to very large network using real data. Second, the authors have considered only congestion to assess network’s criticality; future research on this topic may include other factors, mainly vulnerability.

Taking into consideration the dynamic and stochastic nature in problem modeling enables to be effective tools for real-time control of transportation networks. This leads to design optimized smart transport plans particularly in disaster management, to improve the emergency evacuation effeciency.

The paper provides a novel approach to solve critical nodes/links detection problems. In contrast to the majority of research works in the literature, the proposed model considers dynamicity and betweenness while taking into account the stochastic aspect of transport networks. This enables the approach to guide the traffic and analyze transport networks mainly under disaster conditions in which networks become highly dynamic.

The purpose of this paper is to obtain the reasonable dimensioning for each part and a full-dimension model of assembly dimensions.

The relational path graph of assembly dimension, the shortest-path spanning tree of functional dimension and a revised spanning tree are established in this paper.

The proposed method can obtain reasonable dimensioning of parts and establishment of dimension model in an assembly.

The proposed method can easily realise by computer and be more suitable to automatic dimensioning and establishment of dimension model of parts.

A variety of phenomena such as world wide web, social or business networks, interactions are modelled by various kinds of networks (such as the scale free or preferential attachment networks). However, due to the model‐specific requirements one may want to rewire the network to optimize the communication among the various nodes while not overloading the number of channels (i.e. preserving the number of edges). The purpose of this paper is to present a formal framework for this problem and to examine a family of local search strategies to cope with it.

This is mostly theoretical work. The authors use rigorous mathematical framework to set‐up the model and then we prove some interesting theorems about it which pertain to various local search algorithms that work by rerouting the network.

This paper proves that in cases when every pair of nodes is sampled with non‐zero probability then the algorithm is ergodic in the sense that it samples every possible network on the specified set of nodes and having a specified number of edges with nonzero probability. Incidentally, the ergodicity result led to the construction of a class of algorithms for sampling graphs with a specified number of edges over a specified set of nodes uniformly at random and opened some other challenging and important questions for future considerations.

The measure‐theoretic framework presented in the current paper is original and rather general. It allows one to obtain new points of view on the problem.

The purpose of this paper is to present an efficient method to integrate path generation and following for an unmanned aerial vehicle.

The shortest path is briefly reviewed using a straight line and a circular arc in a horizontal plane. Based on shortest paths, various path generation algorithms using oriented waypoints are described. Path design unit, which is structured concatenations of line segments and circular arcs, is proposed to represent different paths as one structure. Simple path following controller to follow a straight line and a circle was also implemented with linear‐quadratic regulator control laws. Some flight tests were conducted to verify the efficiency of proposed algorithm.

Proposed method represents various paths between given waypoints efficiently by a small number of parameters. It does not need a large amount of memory storage and computation time to run in real time on a low‐cost microprocessor.

This paper provides new structured method to generate different paths efficiently including Dubins' set, which makes path following easy by simple switching logic. It needs small computational time to run in real time. The proposed algorithm in this paper could be used as a basis of other applications such as air traffic control and curved landing approach, which require more accurate path control.

Social network group decision-making (SNGDM) has rapidly developed because of the impact of social relationships on decision-making behavior. However, not only do social relationships affect decision-making behavior, but decision-making behavior also affects social relationships. Such complicated interactions are rarely considered in current research. To bridge this gap, this study proposes an SNGDM model that considers the interaction between social trust relationships and opinion evolution.

First, the trust propagation and aggregation operators are improved to obtain a complete social trust relationship among decision-makers (DMs). Second, the evolution of preference information under the influence of trust relationships is measured, and the development of trust relationships during consensus interactions is predicted. Finally, the iteration of consensus interactions is simulated using an opinion dynamics model. A case study is used to verify the feasibility of the proposed model.

The proposed model can predict consensus achievement based on a group’s initial trust relationship and preference information and effectively captures the dynamic characteristics of opinion evolution in social networks.

This study proposes an SNGDM model that considers the interaction of trust and opinion. The proposed model improves trust propagation and aggregation operators, determines improved preference information based on the existing trust relationships and predicts the evolution of trust relationships in the consensus process. The dynamic interaction between the two accelerates DMs to reach a consensus.

What makes investors tick? Largely counter-intuitive compared to the findings of most past research, this study explores the possibility that funding investors invest in companies based on social relationships, which could be positive or negative, similar or dissimilar. The purpose of this paper is to build a social network graph using data from CrunchBase, the largest public database with profiles about companies. The authors combine social network analysis with the study of investing behavior in order to explore how similarity between investors and companies affects investing behavior through social network analysis.

This study crawls and analyzes data from CrunchBase and builds a social network graph which includes people, companies, social links and funding investment links. The problem is then formalized as a link (or relationship) prediction task in a social network to model and predict (across various machine learning methods and evaluation metrics) whether an investor will create a link to a company in the social network. Various link prediction techniques such as common neighbors, shortest path, Jaccard Coefficient and others are integrated to provide a holistic view of a social network and provide useful insights as to how a pair of nodes may be related (i.e., whether the investor will invest in the particular company at a time) within the social network.

This study finds that funding investors are more likely to invest in a particular company if they have a stronger social relationship in terms of closeness, be it direct or indirect. At the same time, if investors and companies share too many common neighbors, investors are less likely to invest in such companies.

The author’s study is among the first to use data from the largest public company profile database of CrunchBase as a social network for research purposes. The author ' s also identify certain social relationship factors that can help prescribe the investor funding behavior. Authors prediction strategy based on these factors and modeling it as a link prediction problem generally works well across the most prominent learning algorithms and perform well in terms of aggregate performance as well as individual industries. In other words, this study would like to encourage companies to focus on social relationship factors in addition to other factors when seeking external funding investments.

Isometric feature mapping (Isomap) is a very popular manifold learning method and is widely used in dimensionality reduction and data visualization. The most time-consuming step in Isomap is to compute the shortest paths between all pairs of data points based on a neighbourhood graph. The classical Isomap (C-Isomap) is very slow, due to the use of Floyd’s algorithm to compute the shortest paths. The purpose of this paper is to speed up Isomap.

Through theoretical analysis, it is found that the neighbourhood graph in Isomap is sparse. In this case, the Dijkstra’s algorithm with Fibonacci heap (Fib-Dij) is faster than Floyd’s algorithm. In this paper, an improved Isomap method based on Fib-Dij is proposed. By using Fib-Dij to replace Floyd’s algorithm, an improved Isomap method is presented in this paper.

Using the S-curve, the Swiss-roll, the Frey face database, the mixed national institute of standards and technology database of handwritten digits and a face image database, the performance of the proposed method is compared with C-Isomap, showing the consistency with C-Isomap and marked improvements in terms of the high speed. Simulations also demonstrate that Fib-Dij reduces the computation time of the shortest paths from O(N³) to O(N²lgN).

Due to the limitations of the computer, the sizes of the data sets in this paper are all smaller than 3,000. Therefore, researchers are encouraged to test the proposed algorithm on larger data sets.

The new method based on Fib-Dij can greatly improve the speed of Isomap.

Nodes in sensor networks do not have enough topology information to make efficient routing decisions. To relay messages through intermediate sensors, geographic routing has been proposed as such a solution. Its greedy nature, however, makes routing inefficient especially in the presence of topology voids or holes. In this paper we present GRAViTy (Geographic Routing Around Voids In any TopologY of sensor networks), a simple greedy forwarding algorithm that combines compass routing along with a mechanism that allows packets to explore the area around voids and bypass them without significant communication overhead. Using extended simulation results we show that our mechanism outperforms the right‐hand rule for bypassing voids and that the resulting paths found well approximate the corresponding shortest paths. GRAViTy uses a cross‐layered approach to improve routing paths for subsequent packets based on experience gained by former routing decisions. Furthermore, our protocol responds to topology changes, i.e. failure of nodes, and efficiently adjusts routing paths towards the destination.