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 study the mixing rate of non-backtracking random walks on graphs by looking at non-backtracking walks as walks on the directed edges of a graph. A result known as Ihara’s Theorem relates the adjacency matrix of a ...We study the mixing rate of non-backtracking random walks on graphs by looking at non-backtracking walks as walks on the directed edges of a graph. A result known as Ihara’s Theorem relates the adjacency matrix of a graph to a matrix related to non-backtracking walks on the directed edges. We prove a weighted version of Ihara’s Theorem which relates the transition probability matrix of a non-backtracking walk to the transition matrix for the usual random walk. This allows us to determine the spectrum of the transition probability matrix of a non-backtracking random walk in the case of regular graphs and biregular graphs. As a corollary, we obtain a result of Alon et al. in [1] that in most cases, a non-backtracking random walk on a regular graph has a faster mixing rate than the usual random walk. In addition, we obtain an analogous result for biregular graphs.展开更多
In this paper, we obtain explicit formulae for the number of 7-cycles and the total number of cycles of lengths 6 and 7 which contain a specific vertex v<sub>i</sub> in a simple graph G, in terms of the ad...In this paper, we obtain explicit formulae for the number of 7-cycles and the total number of cycles of lengths 6 and 7 which contain a specific vertex v<sub>i</sub> in a simple graph G, in terms of the adjacency matrix and with the help of combinatorics.展开更多
以深度学习框架为基础,提出了一种时空联合供水管网漏损检测模型。该模型首先运用Node2Vec算法求解不同时间段内节点特征;其次,通过模糊C-均值聚类法,利用管网模型节点特征进行分区。最后,以不同时间段的压力敏感度作为输入,漏损位置的...以深度学习框架为基础,提出了一种时空联合供水管网漏损检测模型。该模型首先运用Node2Vec算法求解不同时间段内节点特征;其次,通过模糊C-均值聚类法,利用管网模型节点特征进行分区。最后,以不同时间段的压力敏感度作为输入,漏损位置的分区号作为标签,通过深度信念神经网络进行训练,并通过训练后的模型对管网漏损位置进行检测。在实例分析中,以A市实际供水管网拓扑结构进行验证,利用MATLAB-Open Water Analytics toolbox联合编程建模,结果表明,各个时间段的检测效果均较优,正确率均达到为80%以上。因此,该模型能够有效地检测管网漏损。展开更多
Let?G=(V,E)? be a graph. If φ is a function from the vertex set V(G) to the set of positive integers. Then two vertices?u, v ∈ V(G)? are?φ -equitable if|φ(u)-φ(v)|≤1.By the degree, equitable adjacency between ve...Let?G=(V,E)? be a graph. If φ is a function from the vertex set V(G) to the set of positive integers. Then two vertices?u, v ∈ V(G)? are?φ -equitable if|φ(u)-φ(v)|≤1.By the degree, equitable adjacency between vertices can be redefine almost all of the variants of the graphs. In this paper we study the degree equitability of the graph by defining equitable connectivity, equitable regularity, equitable connected graph and equitable complete graph. Some new families of graphs and some interesting results are obtained.展开更多
回归测试用例选择(Regression Test Case Selection,RTS)问题是回归测试研究中的一个热点,旨在从已有测试用例集中选择出所有可检测代码修改的测试用例。但迄今为止,国内研究人员并未对RTS问题的已有研究成果进行系统总结和比较。首先...回归测试用例选择(Regression Test Case Selection,RTS)问题是回归测试研究中的一个热点,旨在从已有测试用例集中选择出所有可检测代码修改的测试用例。但迄今为止,国内研究人员并未对RTS问题的已有研究成果进行系统总结和比较。首先在回归测试活动和测试用例划分基础上,引出RTS问题和相关假设。随后从源代码和模型角度对已有RTS技术进行分类,从源代码角度出发,又进一步将其细分为线性规划法、数据流分析法、图遍历法、程序切片法和防火墙法等。接着对常见评测数据集和评测指标进行总结,最后对该问题的未来研究方向进行了展望。展开更多
基金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.
文摘We study the mixing rate of non-backtracking random walks on graphs by looking at non-backtracking walks as walks on the directed edges of a graph. A result known as Ihara’s Theorem relates the adjacency matrix of a graph to a matrix related to non-backtracking walks on the directed edges. We prove a weighted version of Ihara’s Theorem which relates the transition probability matrix of a non-backtracking walk to the transition matrix for the usual random walk. This allows us to determine the spectrum of the transition probability matrix of a non-backtracking random walk in the case of regular graphs and biregular graphs. As a corollary, we obtain a result of Alon et al. in [1] that in most cases, a non-backtracking random walk on a regular graph has a faster mixing rate than the usual random walk. In addition, we obtain an analogous result for biregular graphs.
文摘In this paper, we obtain explicit formulae for the number of 7-cycles and the total number of cycles of lengths 6 and 7 which contain a specific vertex v<sub>i</sub> in a simple graph G, in terms of the adjacency matrix and with the help of combinatorics.
文摘以深度学习框架为基础,提出了一种时空联合供水管网漏损检测模型。该模型首先运用Node2Vec算法求解不同时间段内节点特征;其次,通过模糊C-均值聚类法,利用管网模型节点特征进行分区。最后,以不同时间段的压力敏感度作为输入,漏损位置的分区号作为标签,通过深度信念神经网络进行训练,并通过训练后的模型对管网漏损位置进行检测。在实例分析中,以A市实际供水管网拓扑结构进行验证,利用MATLAB-Open Water Analytics toolbox联合编程建模,结果表明,各个时间段的检测效果均较优,正确率均达到为80%以上。因此,该模型能够有效地检测管网漏损。
文摘Let?G=(V,E)? be a graph. If φ is a function from the vertex set V(G) to the set of positive integers. Then two vertices?u, v ∈ V(G)? are?φ -equitable if|φ(u)-φ(v)|≤1.By the degree, equitable adjacency between vertices can be redefine almost all of the variants of the graphs. In this paper we study the degree equitability of the graph by defining equitable connectivity, equitable regularity, equitable connected graph and equitable complete graph. Some new families of graphs and some interesting results are obtained.
文摘回归测试用例选择(Regression Test Case Selection,RTS)问题是回归测试研究中的一个热点,旨在从已有测试用例集中选择出所有可检测代码修改的测试用例。但迄今为止,国内研究人员并未对RTS问题的已有研究成果进行系统总结和比较。首先在回归测试活动和测试用例划分基础上,引出RTS问题和相关假设。随后从源代码和模型角度对已有RTS技术进行分类,从源代码角度出发,又进一步将其细分为线性规划法、数据流分析法、图遍历法、程序切片法和防火墙法等。接着对常见评测数据集和评测指标进行总结,最后对该问题的未来研究方向进行了展望。
