Article
Physics, Multidisciplinary
Shahid Zaman, Mehreen Mustafa, Asad Ullah, Muhammad Kamran Siddiqui
Summary: This study presents a new graph spectrum-based approach to compute the mean first-passage time (MFPT) and Kemeny's constant (KC) of random walks on a penta-chain network ('O). By using the decomposition theorem of the normalized Laplacian polynomial, the normalized Laplacian matrix for the penta-chain network ('O) is computed. Formulas for both MFPT and KC for 'O are derived by utilizing the roots and coefficients of the obtained matrices. Finally, the results of MFPT and KC are compared with the number of pentagons.
EUROPEAN PHYSICAL JOURNAL PLUS
(2023)
Article
Mathematics
Lorenzo Ciardo, Geir Dahl, Steve Kirkland
Summary: In this study, Kemeny's constant of a connected graph was analyzed to determine the expected transit time for a random walk. Lower and upper bounds were provided for the case when the graph is a tree using two different techniques. The lower bound was obtained by considering a specific type of tree and is proven to be sharp. The upper bound was obtained via induction by repeatedly removing pendent vertices from the tree. It was shown that the upper bound is asymptotically sharp by considering a specific family of trees called broom-stars.
LINEAR & MULTILINEAR ALGEBRA
(2022)
Article
Mathematics, Applied
Shahid Zaman, Asad Ullah
Summary: This paper investigates the random walks of octagonal cell network by using the Laplacian spectrum method. The mean first passage time (τ) and Kemeny's constant (Ω) between nodes are obtained. The mean first passage time (τ) is explicitly studied in terms of the eigenvalues of a Laplacian matrix, while Kemeny's constant (Ω) is introduced to measure node strength and determine the scaling of the random walks. An explicit expression of Kemeny's constant and mean first passage time for octagonal cell network is provided based on Laplacian eigenvalues and the correlation among roots of characteristic polynomial. Comparative studies are also performed for τ and Ω based on the achieved results. This work also delivers an inclusive approach for exploring random walks of networks, particularly biased random walks, which can help better understand and tackle practical problems such as search and routing on networks.
MATHEMATICAL METHODS IN THE APPLIED SCIENCES
(2023)
Article
Chemistry, Multidisciplinary
Nolan Faught, Mark Kempton, Adam Knudson
Summary: This paper introduces a method for calculating the Kemeny constant in 1-separable graphs effectively. It is shown through a simple proof that path graphs maximize the Kemeny constant. Furthermore, by further applying this method, expressions for the Kemeny constant of barbell graphs can be simplified.
JOURNAL OF MATHEMATICAL CHEMISTRY
(2022)
Article
Chemistry, Multidisciplinary
Nolan Faught, Mark Kempton, Adam Knudson
Summary: A general formula for resistance distance in flower graphs between any pair of nodes is derived and applied to specific families. Bounds on Kirchhoff index and Kemeny's constant of flower graphs are obtained using the formula, with exact expressions for complete graph or cycle base graphs.
MATCH-COMMUNICATIONS IN MATHEMATICAL AND IN COMPUTER CHEMISTRY
(2021)
Article
Engineering, Multidisciplinary
Junhao Peng, Tengjie Chen, Guoai Xu
Summary: This study focuses on improving the trapping efficiency in regular branched networks by analyzing biased random walks on a family of weighted Cayley trees. By calculating quantities for measuring the trapping efficiency and optimizing with respect to parameter r, the highest trapping efficiency can be achieved in different scenarios.
IEEE TRANSACTIONS ON NETWORK SCIENCE AND ENGINEERING
(2022)
Article
Mathematics, Applied
Jose Luis Palacios, Greg Markowsky
Summary: Bouquet graphs are graphs consisting of highly symmetric pieces connected at a single vertex, for which closed form formulas for Kemeny's constant and two Kirchhoffian indices have been found in terms of the parameters of the component pieces. Additionally, it has been proven that regular edge-transitive graphs are highly symmetric.
DISCRETE APPLIED MATHEMATICS
(2021)
Article
Mathematics
Sooyeong Kim
Summary: This paper discusses Kemeny's constant in the context of a random walk on an undirected graph, and examines the effect of inserting a specific edge on this constant, particularly focusing on cut-vertices with at least two branches as paths. Several tools for identifying edges and analyzing asymptotic behavior of the family are provided, along with examples of specific graph classes. Furthermore, the asymptotic behaviors of families of trees are described.
ELECTRONIC JOURNAL OF LINEAR ALGEBRA
(2022)
Article
Mathematics
Ziliang Guo, Shuchao Li, Xin Liu, Xiaoling Mei
Summary: This paper explores the diamond hierarchical graph S(G) formed from a given connected graph G, providing eigenvalues and eigenvectors of the probability transition matrix on S(G), as well as expected hitting times and resistance distances between vertices on S(G). Applications include establishing connections between properties of S-G and G.
LINEAR & MULTILINEAR ALGEBRA
(2021)
Article
Mathematics, Applied
Jose Luis Palacios, Greg Markowsky
Summary: Closed-form formulas for the Kemeny's constant and the Kirchhoff index of two highly symmetric graphs G(1), G(2) in terms of the original graphs' parameters are found. Necessary conditions for a graph to be highly symmetric are also discussed.
APPLIED MATHEMATICS AND COMPUTATION
(2021)
Article
Mathematics
John Sylvester
Summary: The study proves an upper bound on the effective resistance between two vertices in a connected graph with a suitably well-connected subgraph, and applies it to Erdos-Renyi random graphs. It also demonstrates expectation and concentration results for various parameters in the sparsely connected regime.
JOURNAL OF GRAPH THEORY
(2021)
Article
Mathematics
A. Carmona, M. J. Jimenez, A. Martin
Summary: In the field of random walks, the mean first passage time matrix and Kemeny's constant are important parameters for studying networks. This paper focuses on obtaining expressions for these parameters using generalized inverses of the combinatorial Laplacian. The authors analyze the structure and relations between any generalized inverse and the group inverse of the combinatorial Laplacian, and provide closed-formulas for the mean first passage matrix and Kemeny's constant based on the group inverse of the combinatorial Laplacian. Wheel networks are used as an example to illustrate the findings.
LINEAR & MULTILINEAR ALGEBRA
(2023)
Article
Physics, Multidisciplinary
Claude Godreche, Jean-Marc Luck
Summary: The study investigates the statistics of records associated with planar random walks and the growth of mean numbers of these records with universal power laws of time. It extends the analysis made by Feller of ladder points to a two-dimensional level and yields various analytical asymptotic results, including full statistics of numbers of diagonal and simultaneous records. The sequence of radial records also shows growth with a super-universal square-root law for isotropic random walks in any spatial dimension.
JOURNAL OF PHYSICS A-MATHEMATICAL AND THEORETICAL
(2021)
Article
Computer Science, Information Systems
Haiyao Dong, Haoming Ma, Zhenguang Du, Zhicheng Zhou, Haitao Yang, Zhenyuan Wang
Summary: This study proposes a novel method called DSRS to address the limitations of current dynamic graph methods in capturing high-order global information. By using random walk techniques to mine high-order structural information, DSRS aims to balance the dynamic and high-order structures. Experimental results demonstrate significant improvements in link prediction compared to existing methods, and sensitivity testing and ablation experiments confirm the effectiveness of the proposed pre-training and parameter fine-tuning methods.
JOURNAL OF KING SAUD UNIVERSITY-COMPUTER AND INFORMATION SCIENCES
(2023)
Article
Quantum Science & Technology
Yusuke Yoshie, Kiyoto Yoshino
Summary: This paper presents a discrete-time quantum walk model for finding one of the edges of a given subgraph in a complete graph. By constructing a perturbed quantum walk, we can quickly locate one of the edges, achieving quantum searching.
QUANTUM INFORMATION PROCESSING
(2022)
Article
Mathematics, Applied
Enide Andrade, Lorenzo Ciardo, Geir Dahl
LINEAR ALGEBRA AND ITS APPLICATIONS
(2019)
Article
Mathematics, Applied
Lorenzo Ciardo
LINEAR ALGEBRA AND ITS APPLICATIONS
(2020)
Article
Mathematics
Lorenzo Ciardo, Geir Dahl, Steve Kirkland
Summary: In this study, Kemeny's constant of a connected graph was analyzed to determine the expected transit time for a random walk. Lower and upper bounds were provided for the case when the graph is a tree using two different techniques. The lower bound was obtained by considering a specific type of tree and is proven to be sharp. The upper bound was obtained via induction by repeatedly removing pendent vertices from the tree. It was shown that the upper bound is asymptotically sharp by considering a specific family of trees called broom-stars.
LINEAR & MULTILINEAR ALGEBRA
(2022)
Article
Mathematics, Applied
Lorenzo Ciardo
Summary: The study compares the Perron value and moment of a rooted tree T, showing that mu(T) is almost an upper bound for rho(T) and the ratio mu(T)/rho(T) is unbounded but at most linear in the order of T. Additionally, two new objects associated with T - the Perron entropy and the neckbottle matrix are introduced and the impact of different operations on the set of rooted trees on the Perron value and moment is investigated.
LINEAR ALGEBRA AND ITS APPLICATIONS
(2022)
Article
Mathematics, Applied
Enide Andrade, Lorenzo Ciardo, Geir Dahl
Summary: This paper investigates the Perron values of various classes of rooted trees using combinatorial and linear-algebraic techniques, resulting in multiple bounds on the Perron values of these classes, which can provide information on algebraic connectivity.
LINEAR ALGEBRA AND ITS APPLICATIONS
(2022)
Article
Mathematics
Minerva Catral, Lorenzo Ciardo, Leslie Hogben, Carolyn Reinhart
ELECTRONIC JOURNAL OF LINEAR ALGEBRA
(2020)
Article
Mathematics, Applied
Muhammad Syifa'ul Mufid, Ebrahim Patel, Sergei Sergeev
Summary: This paper presents an approach to solve maxmin-omega linear systems by performing normalization and generating a principal order matrix. The possible solution indices can be identified using the principal order matrix and the parameter omega, and the fully active solutions can be obtained from these indices. Other solutions can be found by applying a relaxation to the fully active solutions. This approach can be seen as a generalization of solving max-plus or min-plus linear systems. The paper also highlights the unusual feature of maxmin-omega linear systems having a finite number of solutions when the solution is non-unique.
LINEAR ALGEBRA AND ITS APPLICATIONS
(2024)
Article
Mathematics, Applied
E. Mainar, J. M. Pena, B. Rubio
Summary: A bidiagonal decomposition of quantum Hilbert matrices is obtained and the total positivity of these matrices is proved. This factorization is used for accurate algebraic computations and the numerical errors caused by imprecise computer arithmetic or perturbed input data are analyzed. Numerical experiments demonstrate the accuracy of the proposed methods.
LINEAR ALGEBRA AND ITS APPLICATIONS
(2024)
Article
Mathematics, Applied
Zhong-Zhi Bai
Summary: This study explores the algebraic structures and computational properties of Wasserstein-1 metric matrices. It shows that these matrices can be expressed using the Neumann series of nilpotent matrices and can be accurately and stably computed by solving unit bidiagonal triangular systems of linear equations.
LINEAR ALGEBRA AND ITS APPLICATIONS
(2024)
Article
Mathematics, Applied
Bogdan Nica
Summary: This study investigates the relationship between the independence number and chromatic number in a graph of non-singular matrices over a finite field, and obtains an upper bound for the former and a lower bound for the latter.
LINEAR ALGEBRA AND ITS APPLICATIONS
(2024)
Article
Mathematics, Applied
Dijian Wang, Yaoping Hou, Deqiong Li
Summary: In this paper, a Turán-like problem in signed graphs is studied. The properties of signed graphs are proven in the context of the problem.
LINEAR ALGEBRA AND ITS APPLICATIONS
(2024)
Article
Mathematics, Applied
Tyler Chen, Thomas Trogdon
Summary: This study focuses on the stability of the Lanczos algorithm when applied to problems with eigenvector empirical spectral distribution close to a reference measure characterized by well-behaved orthogonal polynomials. The analysis reveals that the Lanczos algorithm is forward stable on many large random matrix models, even in finite precision arithmetic, which indicates that random matrices differ significantly from general matrices and caution must be exercised when using them to test numerical algorithms.
LINEAR ALGEBRA AND ITS APPLICATIONS
(2024)
Article
Mathematics, Applied
Constantin Costara
Summary: This passage discusses linear mappings on matrices and the relationship between subsets of the spectrum, providing corresponding characterization conditions.
LINEAR ALGEBRA AND ITS APPLICATIONS
(2024)
Article
Mathematics, Applied
Amir Hossein Ghodrati, Mohammad Ali Hosseinzadeh
Summary: This paper presents tight upper bounds for all signless Laplacian eigenvalues of a graph with prescribed order and minimum degree, improving upon previously known bounds. Additionally, the relationship between the number of signless Laplacian eigenvalues falling within specific intervals and various graph parameters such as independence, clique, chromatic, edge covering, and matching numbers is explored.
LINEAR ALGEBRA AND ITS APPLICATIONS
(2024)
Article
Mathematics, Applied
Ya-Lei Jin, Jie Zhang, Xiao-Dong Zhang
Summary: This paper investigates the relationship between the spectral radius of a symmetric matrix and its principal submatrices, and uses these relationships to obtain upper bounds of the spectral radius of graphs.
LINEAR ALGEBRA AND ITS APPLICATIONS
(2024)
Article
Mathematics, Applied
Davide Bolognini, Paolo Sentinelli
Summary: We introduce immanant varieties associated with simple characters of a finite group and discuss the features of one-dimensional characters and trivial characters.
LINEAR ALGEBRA AND ITS APPLICATIONS
(2024)
Article
Mathematics, Applied
A. S. Gordienko
Summary: We introduce the concept of a graded group action on a graded algebra, or equivalently, a group action by graded pseudoautomorphisms. We study the properties of groups of graded pseudoautomorphisms and prove several important theorems and conjectures regarding graded algebras with a group action.
LINEAR ALGEBRA AND ITS APPLICATIONS
(2024)
Article
Mathematics, Applied
Jiaqi Gu, Shenghao Feng, Yimin Wei
Summary: We propose a tensor product structure compatible with the hypergraph structure and define the algebraic connectivity of the hypergraph in this product, establishing its relationship with vertex connectivity. We introduce connectivity optimization problems into the hypergraph and solve them using algebraic connectivity. Additionally, we apply the Laplacian eigenmap algorithm to the hypergraph under our tensor product.
LINEAR ALGEBRA AND ITS APPLICATIONS
(2024)
Article
Mathematics, Applied
Samuel Lichtenberg, Abiy Tasissa
Summary: This paper explores a dual basis approach to Classical Multidimensional Scaling (CMDS) and provides explicit formulas for the dual basis vectors. It also characterizes the spectrum of an essential matrix in the dual basis framework. Connections to a related problem in metric nearness are made.
LINEAR ALGEBRA AND ITS APPLICATIONS
(2024)
