We have studied the problem of reaching a globally optimal segment for a graph-like environment with a single or a group of autonomous mobile agents. Firstly, two efficient simulated-annealing-like algorithms are give...We have studied the problem of reaching a globally optimal segment for a graph-like environment with a single or a group of autonomous mobile agents. Firstly, two efficient simulated-annealing-like algorithms are given for a single agent to solve the problem in a partially known environment and an unknown environment, respectively. It shows that under both proposed control strategies, the agent will eventually converge to a globally optimal segment with probability 1. Secondly, we use multi-agent searching to simultaneously reduce the computation complexity and accelerate convergence based on the algorithms we have given for a single agent. By exploiting graph partition, a gossip-consensus method based scheme is presented to update the key parameter--radius of the graph, ensuring that the agents spend much less time finding a globally optimal segment.展开更多
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 th...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.展开更多
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 ...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.展开更多
Wireless sensor networks are suffering from serious frequency interference.In this paper,we propose a channel assignment algorithm based on graph theory in wireless sensor networks.We first model the conflict infectio...Wireless sensor networks are suffering from serious frequency interference.In this paper,we propose a channel assignment algorithm based on graph theory in wireless sensor networks.We first model the conflict infection graph for channel assignment with the goal of global optimization minimizing the total interferences in wireless sensor networks.The channel assignment problem is equivalent to the generalized graph-coloring problem which is a NP-complete problem.We further present a meta-heuristic Wireless Sensor Network Parallel Tabu Search(WSN-PTS) algorithm,which can optimize global networks with small numbers of iterations.The results from a simulation experiment reveal that the novel algorithm can effectively solve the channel assignment problem.展开更多
Janmark, Meyer, and Wong showed that continuous-time quantum walk search on known families of strongly regular graphs（SRGs） with parameters（N, k, λ, μ） achieves full quantum speedup. The problem is reconsidered ...Janmark, Meyer, and Wong showed that continuous-time quantum walk search on known families of strongly regular graphs（SRGs） with parameters（N, k, λ, μ） achieves full quantum speedup. The problem is reconsidered in terms of scattering quantum walk, a type of discrete-time quantum walks. Here, the search space is confined to a low-dimensional subspace corresponding to the collapsed graph of SRGs. To quantify the algorithm＇s performance, we leverage the fundamental pairing theorem, a general theory developed by Cottrell for quantum search of structural anomalies in star graphs.The search algorithm on the SRGs with k scales as N satisfies the theorem, and results can be immediately obtained, while search on the SRGs with k scales as√N does not satisfy the theorem, and matrix perturbation theory is used to provide an analysis. Both these cases can be solved in O（√N） time steps with a success probability close to 1. The analytical conclusions are verified by simulation results on two SRGs. These examples show that the formalism on star graphs can be applied more generally.展开更多
文摘We have studied the problem of reaching a globally optimal segment for a graph-like environment with a single or a group of autonomous mobile agents. Firstly, two efficient simulated-annealing-like algorithms are given for a single agent to solve the problem in a partially known environment and an unknown environment, respectively. It shows that under both proposed control strategies, the agent will eventually converge to a globally optimal segment with probability 1. Secondly, we use multi-agent searching to simultaneously reduce the computation complexity and accelerate convergence based on the algorithms we have given for a single agent. By exploiting graph partition, a gossip-consensus method based scheme is presented to update the key parameter--radius of the graph, ensuring that the agents spend much less time finding a globally optimal segment.
文摘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.
基金This work was supported in part by 973 program （2014CB340300）, National Natural Science Foundation of China （Grant No. 61322207） and the Fundamental Research Funds for the Central Universi- ties.
文摘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.
基金supported by National Key Basic Research Program of China(973 program) under Grant No. 2007CB307101National Natural Science Foundation of China under Grant No.60833002,No.60802016,No.60972010+1 种基金Next Generation Internet of China under Grant No.CNGI-0903-05the Fundamental Research Funds for the Central Universities under Grant No.2009YJS011
文摘Wireless sensor networks are suffering from serious frequency interference.In this paper,we propose a channel assignment algorithm based on graph theory in wireless sensor networks.We first model the conflict infection graph for channel assignment with the goal of global optimization minimizing the total interferences in wireless sensor networks.The channel assignment problem is equivalent to the generalized graph-coloring problem which is a NP-complete problem.We further present a meta-heuristic Wireless Sensor Network Parallel Tabu Search(WSN-PTS) algorithm,which can optimize global networks with small numbers of iterations.The results from a simulation experiment reveal that the novel algorithm can effectively solve the channel assignment problem.
基金supported by the National Natural Science Foundation of China(Grant Nos.61502101 and 61170321)the Natural Science Foundation of Jiangsu Province,China(Grant No.BK20140651)the Research Fund for the Doctoral Program of Higher Education of China(Grant No.20110092110024)
文摘Janmark, Meyer, and Wong showed that continuous-time quantum walk search on known families of strongly regular graphs（SRGs） with parameters（N, k, λ, μ） achieves full quantum speedup. The problem is reconsidered in terms of scattering quantum walk, a type of discrete-time quantum walks. Here, the search space is confined to a low-dimensional subspace corresponding to the collapsed graph of SRGs. To quantify the algorithm＇s performance, we leverage the fundamental pairing theorem, a general theory developed by Cottrell for quantum search of structural anomalies in star graphs.The search algorithm on the SRGs with k scales as N satisfies the theorem, and results can be immediately obtained, while search on the SRGs with k scales as√N does not satisfy the theorem, and matrix perturbation theory is used to provide an analysis. Both these cases can be solved in O（√N） time steps with a success probability close to 1. The analytical conclusions are verified by simulation results on two SRGs. These examples show that the formalism on star graphs can be applied more generally.
