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.展开更多
Schlieren imaging is a widely used technique to visualize the structure of supersonic flow field,which is usually dominated by shock waves.Precise identification of shock waves in schlieren image provides critical ins...Schlieren imaging is a widely used technique to visualize the structure of supersonic flow field,which is usually dominated by shock waves.Precise identification of shock waves in schlieren image provides critical insights for flow diagnostics,especially for supersonic inlet whose performance is highly associated with that of the whole flight.However,conventional shock wave identification methods have limited accuracy in segmenting the shock wave.To overcome the limitation,we proposed an automated shock wave identification method(SW-Segment)that can attain high resolution and automatic shock wave segmentation by integrating correlation-based feature extraction with graph search.We demonstrated the efficacy of SW-Segment via the identification of shock waves in simulatively and experimentally obtained schlieren image.The results proved that SW-Segment showed a shock wave identification accuracy of 95.24%in the numerical schlieren image and an accuracy of 88.33%in the experimental image,clearly demonstrating its reliability.SW-Segment holds broad applicability for shock wave detection in diverse schlieren imaging scenarios,offering robust data support for flow field analysis and supersonic flight design.展开更多
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.展开更多
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.展开更多
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.展开更多
<span style="font-family:Verdana;">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 robb...<span style="font-family:Verdana;">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.展开更多
文摘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.
基金supported by the National Natural Science Foundation of China(Grant Nos.12402336,U20A2070,12025202)the Natural Science Foundation of Jiangsu Province(Grant No.BK20230876)+2 种基金the National High-Level Talent Project(Grant No.YQR23069)the Key Laboratory of Intake and Exhaust Technology,Ministry of Education(Grant No.CEPE2024015)the Key Laboratory of Mechanics and Control for Aerospace Structures(Nanjing University of Aeronautics and Astronautics)(Grant No.MCAS-I-0325K01)。
文摘Schlieren imaging is a widely used technique to visualize the structure of supersonic flow field,which is usually dominated by shock waves.Precise identification of shock waves in schlieren image provides critical insights for flow diagnostics,especially for supersonic inlet whose performance is highly associated with that of the whole flight.However,conventional shock wave identification methods have limited accuracy in segmenting the shock wave.To overcome the limitation,we proposed an automated shock wave identification method(SW-Segment)that can attain high resolution and automatic shock wave segmentation by integrating correlation-based feature extraction with graph search.We demonstrated the efficacy of SW-Segment via the identification of shock waves in simulatively and experimentally obtained schlieren image.The results proved that SW-Segment showed a shock wave identification accuracy of 95.24%in the numerical schlieren image and an accuracy of 88.33%in the experimental image,clearly demonstrating its reliability.SW-Segment holds broad applicability for shock wave detection in diverse schlieren imaging scenarios,offering robust data support for flow field analysis and supersonic flight design.
基金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.
文摘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.
基金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.
文摘<span style="font-family:Verdana;">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.
