A graph has exactly two main eigenvalues if and only if it is a 2-walk linear graph.In this paper,we show some necessary conditions that a 2-walk（a,b）-linear graph must obey.Using these conditions and some basic the...A graph has exactly two main eigenvalues if and only if it is a 2-walk linear graph.In this paper,we show some necessary conditions that a 2-walk（a,b）-linear graph must obey.Using these conditions and some basic theorems in graph theory,we characterize all 2-walk linear graphs with small cyclic graphs without pendants.The results are given in sort on unicyclic,bicyclic,tricyclic graphs.展开更多
A graph has exactly two main eigenvalues if and only if it is a 2-walk linear graph. In this paper, we show some structural properties that a 2-walk （a, b）-linear graph holds. According to these properties, we can e...A graph has exactly two main eigenvalues if and only if it is a 2-walk linear graph. In this paper, we show some structural properties that a 2-walk （a, b）-linear graph holds. According to these properties, we can estimate and characterize more 2-walk linear graphs that have exactly two main eigenvalues.展开更多
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 establish a relation between the number of semi-edge walks of a connected graph and the number of walks of two auxiliary graphs. In addition, this relation gives upper bounds on the signless Laplacian spectral radi...We establish a relation between the number of semi-edge walks of a connected graph and the number of walks of two auxiliary graphs. In addition, this relation gives upper bounds on the signless Laplacian spectral radius of connected graphs and planar graphs.展开更多
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.展开更多
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.展开更多
量子行走得益于概率幅的叠加特性,可同时出现在多条路径中,使其能以平方式乃至指数级别的速度加速扩散所携带的量子信息。文章基于无向图G=(V,E)结构,从离散时间量子随机行走(Discrete Time Quantum Walk,DTQW)搜索算法特性出发,运用幺...量子行走得益于概率幅的叠加特性,可同时出现在多条路径中,使其能以平方式乃至指数级别的速度加速扩散所携带的量子信息。文章基于无向图G=(V,E)结构,从离散时间量子随机行走(Discrete Time Quantum Walk,DTQW)搜索算法特性出发,运用幺正变换的硬币算符与迁移算符,构建了DTQW搜索算法步骤框图,在此基础上,应用SKW搜索算法对4节点无向图中的标记节点态进行搜索,通过态塌缩的观测,实现以1/4概率化读取出目标节点。研究结果表明,当有n个足够大的量子系统,并保持彼此之间的强纠缠性时,量子随机行走可以过渡到经典随机行走。文章还详细讨论了DTQW搜索算法实现左右同移的二次加速搜索机制。展开更多
链路预测是通过已知网络节点或者网络拓扑结构预测未产生链接的两个节点间产生链接的可能性.传统方法大多从原始图中提取转移矩阵,导致获取的信息稀疏.鉴于此,设计了一种基于图神经网络和随机游走的链路预测框架(link prediction-graph ...链路预测是通过已知网络节点或者网络拓扑结构预测未产生链接的两个节点间产生链接的可能性.传统方法大多从原始图中提取转移矩阵,导致获取的信息稀疏.鉴于此,设计了一种基于图神经网络和随机游走的链路预测框架(link prediction-graph neural network and random walk,LP-GNRW).首先,通过基于注意力机制的图神经网络Bert学习节点的多种嵌入表示;然后,结合随机游走,获取图的高阶结构信息;最后,将链路预测转换成二分类问题,通过图神经网络对获得的高阶结构信息进行二分类实现链路预测.实验表明LPGNRW能更有效地学习图结构特征,与基于步行的启发式方法相比,获得了更好的AUC指标,提高了链路预测的性能.展开更多
基金Supported by the National Natural Science Foundation of China (10671081)
文摘A graph has exactly two main eigenvalues if and only if it is a 2-walk linear graph.In this paper,we show some necessary conditions that a 2-walk（a,b）-linear graph must obey.Using these conditions and some basic theorems in graph theory,we characterize all 2-walk linear graphs with small cyclic graphs without pendants.The results are given in sort on unicyclic,bicyclic,tricyclic graphs.
基金Supported by the National Natural Science Foundation of China(11171129)
文摘A graph has exactly two main eigenvalues if and only if it is a 2-walk linear graph. In this paper, we show some structural properties that a 2-walk （a, b）-linear graph holds. According to these properties, we can estimate and characterize more 2-walk linear graphs that have exactly two main eigenvalues.
基金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.
基金Supported by GRF of Hong Kong(Grant No.HKBU202413)FRG of Hong Kong Baptist University(Grant No.FRG2/14-15/012)
文摘We establish a relation between the number of semi-edge walks of a connected graph and the number of walks of two auxiliary graphs. In addition, this relation gives upper bounds on the signless Laplacian spectral radius of connected graphs and planar graphs.
文摘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.
文摘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.
文摘【目的】知识表示学习(Knowledge Representation Learning,KRL)在跨语言实体对齐方面取得了显著成就,但未能建模异构知识图谱之间的复杂语义关系,且现有方法多数依赖局部特征匹配以至于未能充分利用知识图谱结构信息。提出了一种基于判别式多特征融合的实体对齐框架(Entity Alignment algorithm based on Discriminant Multi-feature Fusion,EA-DMF)。【方法】利用知识图谱中的语义信息、结构信息以及属性信息进行多特征融合,充分挖掘出图谱中的潜在语义信息。具体而言,EA-DMF引入Gromov-Wasserstein距离度量图谱之间的相似性,建立了随机关系游走算法,利用知识图谱中的长期依赖关系丰富了实体的语义信息,并通过高置信度锚节点的迭代更新,将高置信度的局部对齐信息逐步扩展至全局,最终应用多视角最优传输理论融合多个信息特征进而得到对齐实体对集合。【结果】经过在五个实体对齐数据集上的广泛实验,在没有任何监督或超参数调整的情况下,EA-DMF超越多个竞争基线,证明该方法能够更有效准确地进行知识图谱中未知实体的对齐。
文摘量子行走得益于概率幅的叠加特性,可同时出现在多条路径中,使其能以平方式乃至指数级别的速度加速扩散所携带的量子信息。文章基于无向图G=(V,E)结构,从离散时间量子随机行走(Discrete Time Quantum Walk,DTQW)搜索算法特性出发,运用幺正变换的硬币算符与迁移算符,构建了DTQW搜索算法步骤框图,在此基础上,应用SKW搜索算法对4节点无向图中的标记节点态进行搜索,通过态塌缩的观测,实现以1/4概率化读取出目标节点。研究结果表明,当有n个足够大的量子系统,并保持彼此之间的强纠缠性时,量子随机行走可以过渡到经典随机行走。文章还详细讨论了DTQW搜索算法实现左右同移的二次加速搜索机制。
文摘链路预测是通过已知网络节点或者网络拓扑结构预测未产生链接的两个节点间产生链接的可能性.传统方法大多从原始图中提取转移矩阵,导致获取的信息稀疏.鉴于此,设计了一种基于图神经网络和随机游走的链路预测框架(link prediction-graph neural network and random walk,LP-GNRW).首先,通过基于注意力机制的图神经网络Bert学习节点的多种嵌入表示;然后,结合随机游走,获取图的高阶结构信息;最后,将链路预测转换成二分类问题,通过图神经网络对获得的高阶结构信息进行二分类实现链路预测.实验表明LPGNRW能更有效地学习图结构特征,与基于步行的启发式方法相比,获得了更好的AUC指标,提高了链路预测的性能.
