Markov Models for the Tipsy Cop and Robber Game on Graph

In this paper we analyze and model three open problems posed by Harris, Insko, Prieto-Langarica, Stoisavljevic, and Sullivan in 2020 concerning the tipsy cop and robber game on graphs. The three different scenarios we model account for different biological scenarios. The first scenario is when the cop and robber have a consistent tipsiness level through the duration of the game;the second is when the cop and robber sober up as a function of time;the third is when the cop and robber sober up as a function of the distance between them. Using Markov chains to model each scenario we calculate the probability of a game persisting through M rounds of the game and the expected game length given different starting positions and tipsiness levels for the cop and robber.

Composite Recommendation of Artworks in E-Commerce Based on User Keyword-Driven Correlation Graph Search

With the ever-increasing diversification of people’s interests and preferences,artwork has become one of the most popular commodities or investment goods in E-commerce,and it increasingly attracts the attention of the public.Currently,many real-world or virtual artworks can be found in E-commerce,and finding a means to recommend them to appropriate users has become a significant task to alleviate the heavy burden on artwork selection decisions by users.Existing research mainly studies the problem of single-artwork recommendation while neglecting the more practical but more complex composite recommendation of artworks in E-commerce,which considerably influences the quality of experience of potential users,especially when they need to select a set of artworks instead of a single artwork.Inspired by this limitation,we put forward a novel composite recommendation approach to artworks by a user keyword-driven correlation graph search named ART_(com-rec).Through ART_(com-rec),the recommender system can output a set of artworks(e.g.,an artwork composite solution)in E-commerce by considering the keywords typed by a user to indicate his or her personalized preferences.Finally,we validate the feasibility of the ART_(com-rec) approach by a set of simulated experiments on a real-world PW dataset.

Structure learning on Bayesian networks by finding the optimal ordering with and without priors

Ordering based search methods have advantages over graph based search methods for structure learning of Bayesian networks in terms on the efficiency. With the aim of further increasing the accuracy of ordering based search methods, we first propose to increase the search space, which can facilitate escaping from the local optima. We present our search operators with majorizations, which are easy to implement. Experiments show that the proposed algorithm can obtain significantly more accurate results. With regard to the problem of the decrease on efficiency due to the increase of the search space, we then propose to add path priors as constraints into the swap process. We analyze the coefficient which may influence the performance of the proposed algorithm, the experiments show that the constraints can enhance the efficiency greatly, while has little effect on the accuracy. The final experiments show that, compared to other competitive methods, the proposed algorithm can find better solutions while holding high efficiency at the same time on both synthetic and real data sets.

Application of Rollout Strategy to Test Points Selection for Integer-Coded Fault Wise Table

Test points selection for integer-coded fault wise table is a discrete optimization problem. The global minimum set of test points can only be guaranteed by an exhaustive search which is eompurationally expensive. In this paper, this problem is formulated as a heuristic depth-first graph search problem at first. The graph node expanding method and rules are given. Then, rollout strategies are applied, which can be combined with the heuristic graph search algorithms, in a computationally more efficient manner than the optimal strategies, to obtain solutions superior to those using the greedy heuristic algorithms. The proposed rollout-based test points selection algorithm is illustrated and tested using an analog circuit and a set of simulated integer-coded fault wise tables. Computa- tional results are shown, which suggest that the rollout strategy policies are significantly better than other strategies.

Big graph search： challenges and techniques

On one hand, compared with traditional rela- tional and XML models, graphs have more expressive power and are widely used today. On the other hand, various ap- plications of social computing trigger the pressing need of a new search paradigm. In this article, we argue that big graph search is the one filling this gap. We first introduce the ap- plication of graph search in various scenarios. We then for- malize the graph search problem, and give an analysis of graph search from an evolutionary point of view, followed by the evidences from both the industry and academia. After that, we analyze the difficulties and challenges of big graph search. Finally, we present three classes of techniques to- wards big graph search： query techniques, data techniques and distributed computing techniques.

Graph representation of n-dimensional space

This paper investigates how graph representation can be created for the mesh which is a discrete approximation of n-dimensional continuous space. The paper discusses the relationship between mesh dimensionality and the type and quantity of edges connecting each vertex with its neighbors. Basing on the analysis, a simple algorithm is also proposed to create such graph representation. The purpose of the graph is to search optimal paths and trajectories in the represented space.

An Incremental Partitioning Graph Similarity Search Based on Tree Structure Index

Graph similarity search is a common operation of graph database,and graph editing distance constraint is the most common similarity measure to solve graph similarity search problem.However,accurate calculation of graph editing distance is proved to be NP hard,and the filter and verification framework are adopted in current method.In this paper,a dictionary tree based clustering index structure is proposed to reduce the cost of candidate graph,and is verified in the filtering stage.An efficient incremental partition algorithm was designed.By calculating the distance between query graph and candidate graph partition,the filtering effect was further enhanced.Experiments on real large graph datasets show that the performance of this algorithm is significantly better than that of the existing algorithms.

Forecasting complex group behavior via multiple plan recognition

Group behavior forecasting is an emergent re- search and application field in social computing. Most of the existing group behavior forecasting methods have heavily re- lied on structured data which is usually hard to obtain. To ease the heavy reliance on structured data, in this paper, we pro- pose a computational approach based on the recognition of multiple plans/intentions underlying group behavior. We fur- ther conduct human experiment to empirically evaluate the effectiveness of our proposed approach.

Test sequencing problem arising at the design stage for reducing life cycle cost

Previous test sequencing algorithms only consider the execution cost of a test at the application stage. Due to the fact that the placement cost of some tests at the design stage is considerably high compared with the execution cost, the sequential diagnosis strategy obtained by previous methods is actually not optimal from the view of life cycle. In this paper, the test sequencing problem based on life cycle cost is presented. It is formulated as an optimization problem, which is non-deterministic polynomial-time hard （NP-hard）. An algorithm and a strategy to improve its computational efficiency are proposed. The formulation and algorithms are tested on various simulated systems and comparisons are made with the extant test sequencing methods. Application on a pump rotational speed control （PRSC） system of a spacecraft is studied in detail. Both the simulation results and the real-world case application results suggest that the solution proposed in this paper can significantly reduce the life cycle cost of a sequential fault diagnosis strategy.