Explore the vast range of titles available.

In this paper, we introduce an inexact Noda iteration method featuring inner and outer iterations for computing the smallest eigenvalue and corresponding eigenvector of an irreducible monotone matrix. The proposed method includes two primary relaxation steps designed to compute the smallest eigenvalue and its associated eigenvector. These steps are influenced by specific relaxation factors, and we examine how these factors impact the convergence of the outer iterations. By applying two distinct relaxation factors to solve the inner linear systems, we demonstrate that the convergence can be globally linear or superlinear, contingent upon the relaxation factor used. Additionally, the relaxation factor affects the rate of convergence. The inexact Noda iterations we propose are structure-preserving and ensure the positivity of the approximate eigenvectors. Numerical examples are provided to demonstrate the practicality of the proposed method, consistently preserving the positivity of approximate eigenvectors.

In tensor computations, tensor–vector multiplication is one of the main computational costs. We recently studied algorithms with wider applicability and more computational potential for computing the largest eigenpair of a weakly irreducible nonnegative m th-order tensor A , called higher-order Noda iteration (HONI). This method is an eigenvalue solver which uses an inner-outer scheme. The outer iteration is the update of the approximate eigenpair(s), while in the inner iteration a multilinear system has to be solved, often iteratively. For the inner iteration, we also provide a Newton-type method to solve multilinear systems, and prove that the algorithm converges to the unique solution of multilinear systems and the convergence rate is quadratic. HONI has superior performance in terms of fast convergence and positivity preserving property, and its main advantage is to use simple recursive relations to compute the approximate eigenvalue, which means that no additional tensor–vector multiplication is required. Moreover, we devise a practical relaxation criterion based on our theoretical results to improve the efficiency and practicality of HONI, called inexact HONI, and further explain the relationship between HONI and Newton–Noda iteration. Numerical experiments are provided to support the theoretical results.

In this paper, a distributed algorithm for reaching average consensus is proposed for multi-agent systems with tree communication graph, when the edge weight distribution is unbalanced. First, the problem is introduced as a key topic of core algorithms for several modern scenarios. Then, the relative solution is proposed as a finite-time algorithm, which can be included in any application as a preliminary setup routine, and it is well-suited to be integrated with other adaptive setup routines, thus making the proposed solution useful in several practical applications. A special focus is devoted to the integration of the proposed method with a recent Laplacian eigenvalue allocation algorithm, and the implementation of the overall approach in a wireless sensor network framework. Finally, a worked example is provided, showing the significance of this approach for reaching a more precise average consensus in uncertain scenarios.

Urban mobility and geographical systems benefit significantly from a graph-based topology. To identify the network’s crucial zones in terms of connectivity or movement across the network, we implemented several centrality metrics on a particular type of spatial network, i.e., a Region Adjacency graph, using three geographical regions of different sizes to exhibit the scalability of conventional metrics. To boost the topological analysis of a network with geographical data, we discuss the eigendata centrality and implement it for the largest of our Region Adjacency graphs using available geographical information. For flow prediction data-driven models, we discuss the Deep Gravity model and utilise either its geographical input data or predicted flow values to implement an additional node score through the Perron vector of the transition probability matrix. The results show that the topological analysis of a spatial network can be significantly enhanced by including regional and mobility data for graphs of different scales, connectivity, and orientation properties.

The power method is commonly applied to compute the Perron vector of large adjacency matrices. Blondel et al. [SIAM Rev. 46, 2004] investigated its performance when the adjacency matrix has multiple eigenvalues of the same magnitude. It is well known that the Lanczos method typically requires fewer iterations than the power method to determine eigenvectors with the desired accuracy. However, the Lanczos method demands more computer storage, which may make it impractical to apply to very large problems. The present paper adapts the analysis by Blondel et al. to the Lanczos and restarted Lanczos methods. The restarted methods are found to yield fast convergence and to require less computer storage than the Lanczos method. Computed examples illustrate the theory presented. Applications of the Arnoldi method are also discussed.

In this paper, we investigate some properties of the Perron vector of connected graphs. These results are used to characterize all extremal connected graphs which attain the minimum value among the spectral radii of all connected graphs with ordern=kαand the independence numberα. Moreover, all extremal graphs which attain the maximum value among the spectral radii of clique trees with ordern=kαand the independence numberαare characterized. 2010Mathematics Subject Classification: 05C50, 05C35. Key words and phrases: Spectral radius, Independence number, Perron vector, Clique tree.

Let A be a nonnegative tensor and x = ( x i ) > 0 its Perron vector. We give lower bounds for x t m − 1 / ∑ x i 2 ⋯ x i m and upper bounds for x s m − 1 / ∑ x i 2 ⋯ x i m , where x s = max 1 ≤ i ≤ n x i and x t = min 1 ≤ i ≤ n x i . MSC: 15A18, 15A69, 65F15, 65F10.

Stationary distributions appear in a wide variety of problems in areas like computer science, mathematics, statistics, and economics. The knowledge of stationary distribution has a crucial impact on whether we are able to solve such problems, or how efficiently we can solve them. In this thesis, I present three of my projects which have a common theme of dealing with stationary distributions.In the first work, called Perron-Frobenius theory in nearly linear time, we give a nearly linear time algorithm for computing stationary distribution of matrices characterized by the Perron-Frobenius theorem. Through our algorithm, we non-trivially extend the class of matrices known to be solvable in nearly linear time by graph Laplacian solvers.In the second work, called high precision small space estimation of random walk probabilities, we try to make a step toward derandomization of the complexity class RL or randomized log space, which is a long-standing open problem in complexity theory. In this context, the knowledge of stationary distribution for directed graphs seems to be a barrier in achieving such a result. While we are not able to resolve L vs. RL problem, we give a small space deterministic algorithm to estimate random walk probabilities to high precision in undirected graphs, as well as directed Eulerian graphs.In the last work, with the rise of ride-sharing platforms, we study a set of important questions naturally arise in this context. Although we use a different set of technical tools compared to the previous two works, we still deal with characterizing equilibria in stationary systems. One of the main questions we answer is whether the competition between two platforms can lead to market failure by pushing the drivers out of the market.

Let π = ( d 1 , d 2 , ..., d n ) and π′ = ( d′ 1 , d′ 2 , ..., d′ n ) be two non-increasing degree sequences. We say π is majorizated by π′ , denoted by π ⊲ π′ , if and only if π ≠ π′ , Σ i =1 n d i = Σ i =1 n d′ i , and Σ i =1 j d i ≤ Σ i =1 j d′ i for all j = 1, 2, ..., n . Weuse C π to denote the class of connected graphs with degree sequence π . Let ρ ( G ) be the spectral radius, i.e., the largest eigenvalue of the adjacent matrix of G . In this paper, we extend the main results of [Liu, M. H., Liu, B. L., You, Z. F.: The majorization theorem of connected graphs. Linear Algebra Appl. , 431 (1), 553–557 (2009)] and [Bıyıkoğlu, T., Leydold, J.: Graphs with given degree sequence and maximal spectral radius. Electron. J. Combin. , 15 (1), R119 (2008)]. Moreover, we prove that if π and π′ are two different non-increasing degree sequences of unicyclic graphs with π ⊲ π′ , G and G′ are the unicyclic graphs with the greatest spectral radii in C π and C′ π , respectively, then ρ ( G ) < ρ ( G′ ).