Search

The importance of a node in a directed graph can be measured by its PageRank. The PageRank of a node is used in a number of application contexts - including ranking websites - and can be interpreted as the average portion of time spent at the node by an infinite random walk. We consider the problem of maximizing the PageRank of a node by selecting some of the edges from a set of edges that are under our control. By applying results from Markov decision theory, we show that an optimal solution to this problem can be found in polynomial time. It also indicates that the provided reformulation is well-suited for reinforcement learning algorithms. Finally, we show that, under the slight modification for which we are given mutually exclusive pairs of edges, the problem of PageRank optimization becomes NP-hard.

In this chapter we analyze a recent conjecture stating that the finiteness property holds for pairs of binary matrices. We show that the finiteness property holds for all pairs of binary matrices if and only if it holds for all sets of nonnegative rationalmatrices.We provide a similar result for matrices with positive and negative entries. We finally prove the conjecture for 2×2 matrices.

Overlap-free words are words over the alphabet A = {a, b} that do not contain factors of the form xvxvx, where x ∈ A and v ∈ A*. We analyze the asymptotic growth of the number un of overlapfree words of length n. We obtain explicit formulas for the minimal and maximal rates of growth of un in terms of spectral characteristics (the lower spectral radius and the joint spectral radius) of one set of matrices of dimension 20. Using these descriptions we provide estimates of the rates of growth that are within 0.4% and 0.03% of their exact value. The best previously known bounds were within 11% and 3% respectively. We prove that un actually has the same growth for "almost all" n. This "average" growth is distinct from the maximal and minimal rates and can also be expressed in terms of a spectral quantity (the Lyapunov exponent). We use this expression to estimate it.

The joint spectral radius of a set of matrices is a measure of the maximal asymptotic growth rate that can be obtained by forming long products of matrices taken from the set. This quantity appears in a number of application contexts, in particular it characterizes the growth rate of switched linear systems. The joint spectral radius is notoriously difficult to compute and to approximate. We introduce in this paper the first polynomial time approximations of guaranteed precision. We provide an approximation (p) over cap that is based on ellipsoid norms that can be computed by convex optimization and that is such that the joint spectral radius belongs to the interval [(p) over cap/ rootn (p) over cap] where n is the dimension of the matrices. We also provide a simple approximation for the special case where the entries of all the matrices are non-negative; in this case the approximation is proved to be within a factor at most m (m is the number of matrices) of the exact value.

We introduce a concept of similarity between vertices of directed graphs. Let GA and GB be two directed graphs with respectively nA and nB vertices. We define a nA × nB similarity matrix S whose real entry sij expresses how similar vertex i (in GA) is to vertex j (in GB): we say that sij is their similarity score. In the special case where GA = GB = G, the score sij is the similarity score between the vertices i and j of G and the square similarity matrix S is the self-similarity matrix of the graph G. We point out that Kleinberg's "hub and authority" method to identify web-pages relevant to a given query can be viewed as a special case of our definition in the case where one of the graphs has two vertices and a unique directed edge between them. In analogy to Kleinberg, we show that our similarity scores are given by the components of a dominant vector of a non-negative matrix and we propose a simple iterative method to compute them.

A configuration of a Turing machine is given by a tape content together with a particular state of the machine. Petr Kůrka has conjectured that every Turing machine - when seen as a dynamical system on the space of its configurations - has at least one periodic orbit. In this paper, we provide an explicit counter-example to this conjecture. We also consider counter machines and prove that, in this case, the problem of determining if a given machine has a periodic orbit in configuration space is undecidable.