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.展开更多
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.展开更多
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.展开更多
In this paper, a method to initiate, develop and visualize an abstract syntax tree (AST) in C++ source code is presented. The approach is in chronological order starting with collection of program codes as a string an...In this paper, a method to initiate, develop and visualize an abstract syntax tree (AST) in C++ source code is presented. The approach is in chronological order starting with collection of program codes as a string and split into individual characters using regular expression. This will be followed by separating the token grammar using best first search (BFS) algorithm to determine node having lowest value, lastly followed by graph presentation of intermediate representation achieved with the help of graph visualization software (GraphViz) while former is implemented using python programming language version 3. The efficacy of our approach is used in analyzing C++ code and yielded a satisfactory result.展开更多
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).展开更多
图是一种非常重要的数据结构形式,被广泛用于社交网络、交通网络和搜索引擎等领域。随着图数据规模爆发式增长,存储容量受限,分布式图计算成为处理大规模图数据的焦点。宽度优先搜索(breadth first search,BFS)算法是图遍历和许多图分...图是一种非常重要的数据结构形式,被广泛用于社交网络、交通网络和搜索引擎等领域。随着图数据规模爆发式增长,存储容量受限,分布式图计算成为处理大规模图数据的焦点。宽度优先搜索(breadth first search,BFS)算法是图遍历和许多图分析算法的基础,而在分布式图计算过程中存在严重的通信开销。针对上述问题,本文提出了一种综合的数据压缩编码优化方案,结合位图和变长压缩数组,通过更高的压缩率来降低数据通信开销;此外,还提出了一种点对点异步环形通信策略,进一步降低分布式图计算中计算-通信的同步开销。通过这些优化手段,本文在8节点的分布式集群上对优化后BFS算法的性能进行了系统评估,结果表明,当图数据规模为28时,优化后的BFS算法平均性能为46.79亿条边每秒遍历(giga-traversed edges per second,GTEPS),性能比优化前提升了接近7.82%。展开更多
针对大多数基于图神经网络(Graph Neural Network,GNN)的社区搜索方法中存在的时间开销巨大和“搭便车”效应问题,本文提出一种基于图组合优化的高效社区搜索模型(Efficient Community Search Based on Graph Combinatorial Optimizatio...针对大多数基于图神经网络(Graph Neural Network,GNN)的社区搜索方法中存在的时间开销巨大和“搭便车”效应问题,本文提出一种基于图组合优化的高效社区搜索模型(Efficient Community Search Based on Graph Combinatorial Optimization,CS-ROMF).该模型设计基于GNN的社区定位器来快速定位查询节点的潜在社区,减少时间开销.在此基础上设计基于强化学习(Reinforcement Learning,RL)的社区优化器调整候选社区的结构,减轻“搭便车”效应.在5个具有真实社区的数据集上进行大量实验,结果表明CS-ROMF在所有评估指标上均优于基线模型.其中,相比结果最好的基线模型,CS-ROMF在F_(1)值、Jaccard值以及NMI上分别最高提升14.99%、20.67%和21.37%,表明CS-ROMF减轻了“搭便车”效应.同时,CS-ROMF能够显著提升搜索效率,其运行速度比基于GNN的基线模型最多快10倍.展开更多
基金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.
文摘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.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.
文摘In this paper, a method to initiate, develop and visualize an abstract syntax tree (AST) in C++ source code is presented. The approach is in chronological order starting with collection of program codes as a string and split into individual characters using regular expression. This will be followed by separating the token grammar using best first search (BFS) algorithm to determine node having lowest value, lastly followed by graph presentation of intermediate representation achieved with the help of graph visualization software (GraphViz) while former is implemented using python programming language version 3. The efficacy of our approach is used in analyzing C++ code and yielded a satisfactory result.
文摘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).
文摘图是一种非常重要的数据结构形式,被广泛用于社交网络、交通网络和搜索引擎等领域。随着图数据规模爆发式增长,存储容量受限,分布式图计算成为处理大规模图数据的焦点。宽度优先搜索(breadth first search,BFS)算法是图遍历和许多图分析算法的基础,而在分布式图计算过程中存在严重的通信开销。针对上述问题,本文提出了一种综合的数据压缩编码优化方案,结合位图和变长压缩数组,通过更高的压缩率来降低数据通信开销;此外,还提出了一种点对点异步环形通信策略,进一步降低分布式图计算中计算-通信的同步开销。通过这些优化手段,本文在8节点的分布式集群上对优化后BFS算法的性能进行了系统评估,结果表明,当图数据规模为28时,优化后的BFS算法平均性能为46.79亿条边每秒遍历(giga-traversed edges per second,GTEPS),性能比优化前提升了接近7.82%。
文摘针对大多数基于图神经网络(Graph Neural Network,GNN)的社区搜索方法中存在的时间开销巨大和“搭便车”效应问题,本文提出一种基于图组合优化的高效社区搜索模型(Efficient Community Search Based on Graph Combinatorial Optimization,CS-ROMF).该模型设计基于GNN的社区定位器来快速定位查询节点的潜在社区,减少时间开销.在此基础上设计基于强化学习(Reinforcement Learning,RL)的社区优化器调整候选社区的结构,减轻“搭便车”效应.在5个具有真实社区的数据集上进行大量实验,结果表明CS-ROMF在所有评估指标上均优于基线模型.其中,相比结果最好的基线模型,CS-ROMF在F_(1)值、Jaccard值以及NMI上分别最高提升14.99%、20.67%和21.37%,表明CS-ROMF减轻了“搭便车”效应.同时,CS-ROMF能够显著提升搜索效率,其运行速度比基于GNN的基线模型最多快10倍.
