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.展开更多
The study investigated user experience, display complexity, display type (tables versus graphs), and task difficulty as variables affecting the user’s ability to navigate through complex visual data. A total of 64 pa...The study investigated user experience, display complexity, display type (tables versus graphs), and task difficulty as variables affecting the user’s ability to navigate through complex visual data. A total of 64 participants, 39 undergraduate students (novice users) and 25 graduate students (intermediate-level users) participated in the study. The experimental design was 2 × 2 × 2 × 3 mixed design using two between-subject variables (display complexity, user experience) and two within-subject variables (display format, question difficulty). The results indicated that response time was superior for graphs (relative to tables), especially when the questions were difficult. The intermediate users seemed to adopt more extensive search strategies than novices, as revealed by an analysis of the number of changes they made to the display prior to answering questions. It was concluded that designers of data displays should consider the (a) type of display, (b) difficulty of the task, and (c) expertise level of the user to obtain optimal levels of performance.展开更多
Evolutionary computation techniques have mostly been used to solve various optimization problems, and it is well known that graph isomorphism problem （GIP） is a nondeterministic polynomial problem. A simulated annea...Evolutionary computation techniques have mostly been used to solve various optimization problems, and it is well known that graph isomorphism problem （GIP） is a nondeterministic polynomial problem. A simulated annealing （SA） algorithm for detecting graph isomorphism is proposed, and the proposed SA algorithm is well suited to deal with random graphs with large size. To verify the validity of the proposed SA algorithm, simulations are performed on three pairs of small graphs and four pairs of large random graphs with edge densities 0.5, 0.1, and 0.01, respectively. The simulation results show that the proposed SA algorithm can detect graph isomorphism with a high probability.展开更多
According to the researches on theoretic basis in part Ⅰ of the paper, the spanning tree algorithms solving the maximum independent set both in even network and in odd network have been developed in this part, part ...According to the researches on theoretic basis in part Ⅰ of the paper, the spanning tree algorithms solving the maximum independent set both in even network and in odd network have been developed in this part, part Ⅱ of the paper. The algorithms transform first the general network into the pair sets network, and then decompose the pair sets network into a series of pair subsets by use of the characteristic of maximum flow passing through the pair sets network. As for the even network, the algorithm requires only one time of transformation and decomposition, the maximum independent set can be gained without any iteration processes, and the time complexity of the algorithm is within the bound of O(V3). However, as for the odd network, the algorithm consists of two stages. In the first stage, the general odd network is transformed and decomposed into the pseudo-negative envelope graphs and generalized reverse pseudo-negative envelope graphs alternately distributed at first; then the algorithm turns to the second stage, searching for the negative envelope graphs within the pseudo-negative envelope graphs only. Each time as a negative envelope graph has been found, renew the pair sets network by iteration at once, and then turn back to the first stage. So both stages form a circulation process up to the optimum. Two available methods, the adjusting search and the picking-off search are specially developed to deal with the problems resulted from the odd network. Both of them link up with each other harmoniously and are embedded together in the algorithm. Analysis and study indicate that the time complexity of this algorithm is within the bound of O(V5).展开更多
文摘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.
文摘The study investigated user experience, display complexity, display type (tables versus graphs), and task difficulty as variables affecting the user’s ability to navigate through complex visual data. A total of 64 participants, 39 undergraduate students (novice users) and 25 graduate students (intermediate-level users) participated in the study. The experimental design was 2 × 2 × 2 × 3 mixed design using two between-subject variables (display complexity, user experience) and two within-subject variables (display format, question difficulty). The results indicated that response time was superior for graphs (relative to tables), especially when the questions were difficult. The intermediate users seemed to adopt more extensive search strategies than novices, as revealed by an analysis of the number of changes they made to the display prior to answering questions. It was concluded that designers of data displays should consider the (a) type of display, (b) difficulty of the task, and (c) expertise level of the user to obtain optimal levels of performance.
基金the National Natural Science Foundation of China (60373089, 60674106, and 60533010)the National High Technology Research and Development "863" Program (2006AA01Z104)
文摘Evolutionary computation techniques have mostly been used to solve various optimization problems, and it is well known that graph isomorphism problem （GIP） is a nondeterministic polynomial problem. A simulated annealing （SA） algorithm for detecting graph isomorphism is proposed, and the proposed SA algorithm is well suited to deal with random graphs with large size. To verify the validity of the proposed SA algorithm, simulations are performed on three pairs of small graphs and four pairs of large random graphs with edge densities 0.5, 0.1, and 0.01, respectively. The simulation results show that the proposed SA algorithm can detect graph isomorphism with a high probability.
文摘According to the researches on theoretic basis in part Ⅰ of the paper, the spanning tree algorithms solving the maximum independent set both in even network and in odd network have been developed in this part, part Ⅱ of the paper. The algorithms transform first the general network into the pair sets network, and then decompose the pair sets network into a series of pair subsets by use of the characteristic of maximum flow passing through the pair sets network. As for the even network, the algorithm requires only one time of transformation and decomposition, the maximum independent set can be gained without any iteration processes, and the time complexity of the algorithm is within the bound of O(V3). However, as for the odd network, the algorithm consists of two stages. In the first stage, the general odd network is transformed and decomposed into the pseudo-negative envelope graphs and generalized reverse pseudo-negative envelope graphs alternately distributed at first; then the algorithm turns to the second stage, searching for the negative envelope graphs within the pseudo-negative envelope graphs only. Each time as a negative envelope graph has been found, renew the pair sets network by iteration at once, and then turn back to the first stage. So both stages form a circulation process up to the optimum. Two available methods, the adjusting search and the picking-off search are specially developed to deal with the problems resulted from the odd network. Both of them link up with each other harmoniously and are embedded together in the algorithm. Analysis and study indicate that the time complexity of this algorithm is within the bound of O(V5).
