Objects such as documents, people, words or utilities, that are related in some way, for instance by citations, friendship, appearance in definitions or physical connections, may be conveniently represented using graphs or networks. An increasing number of such relational databases, as for instance the World Wide Web, digital libraries, social networking web sites or phone calls logs, are available. Relevant information may be hidden in these networks. A user may for instance need to get authority web pages on a particular topic or a list of similar documents from a digital library, or to determine communities of friends from a social networking site or a phone calls log. Unfortunately, extracting this information may not be easy. This thesis is devoted to the study of problems related to information extraction in large graphs with the help of dominant vectors of nonnegative matrices. The graph structure is indeed very useful to retrieve information from a relational database. The correspondence between nonnegative matrices and graphs makes Perron--Frobenius methods a powerful tool for the analysis of networks. In a first part, we analyze the fixed points of a normalized affine iteration used by a database matching algorithm. Then, we consider questions related to PageRank, a ranking method of the web pages based on a random surfer model and used by the well known web search engine Google. In a second part, we study optimal linkage strategies for a web master who wants to maximize the average PageRank score of a web site. Finally, the third part is devoted to the study of a nonlinear variant of PageRank. The simple model that we propose takes into account the mutual influence between web ranking and web surfing.

Systems whose time evolutions are entirely deterministic can nevertheless be studied probabilistically, <em>i. e. </em> in terms of the evolution of probability distributions rather than individual trajectories. This approach is central to the dynamics of ensembles (statistical mechanics) and systems with uncertainty in the initial conditions. It is also the basis of ergodic theory--the study of probabilistic invariants of dynamical systems--which provides one framework for understanding chaotic systems whose time evolutions are erratic and for practical purposes unpredictable. Delay differential equations (DDEs) are a particular class of deterministic systems, distinguished by an explicit dependence of the dynamics on past states. DDEs arise in diverse applications including mathematics, biology and economics. A probabilistic approach to DDEs is lacking. The main problems we consider in developing such an approach are (1) to characterize the evolution of probability distributions for DDEs, <em>i. e. </em> develop an analog of the Perron-Frobenius operator; (2) to characterize invariant probability distributions for DDEs; and (3) to develop a framework for the application of ergodic theory to delay equations, with a view to a probabilistic understanding of DDEs whose time evolutions are chaotic. We develop a variety of approaches to each of these problems, employing both analytical and numerical methods. In transient chaos, a system evolves erratically during a transient period that is followed by asymptotically regular behavior. Transient chaos in delay equations has not been reported or investigated before. We find numerical evidence of transient chaos (fractal basins of attraction and long chaotic transients) in some DDEs, including the Mackey-Glass equation. Transient chaos in DDEs can be analyzed numerically using a modification of the "stagger-and-step" algorithm applied to a discretized version of the DDE.

We describe the structure of those graphs that have largest spectral radius in the class of all connected graphs with a given degree sequence. We show that in such a graph the degree sequence is non-increasing with respect to an ordering of the vertices induced by breadth-first search. For trees the resulting structure is uniquely determined up to isomorphism. We also show that the largest spectral radius in such classes of trees is strictly monotone with respect to majorization. This paper is the revised final version of the preprint no. 35 of this research report series. (author´s abstract) / Series: Research Report Series / Department of Statistics and Mathematics

A semiregular tree is a tree where all non-pendant vertices have the same degree. Among all semiregular trees with fixed order and degree, a graph with minimal (adjacency / Laplacian) spectral radius is a caterpillar. Counter examples show that the result cannot be generalized to the class of trees with a given (non-constant) degree sequence. / Series: Research Report Series / Department of Statistics and Mathematics

A semiregular tree is a tree where all non-pendant vertices have the same degree. Belardo et al. (MATCH Commun. Math. Chem. 61(2), pp. 503-515, 2009) have shown that among all semiregular trees with a fixed order and degree, a graph with index is caterpillar. In this technical report we provide a different proof for this theorem. Furthermore, we give counter examples that show that this result cannot be generalized to the class of trees with a given (non-constant) degree sequence. / Series: Research Report Series / Department of Statistics and Mathematics

The Frobenius-Perron operator acting on integrable functions and the Koopman operator acting on essentially bounded functions for a given nonsingular transformation on the unit interval can be shown to have cyclic spectrum by referring to the theory of lattice homomorphisms on a Banach lattice. In this paper, it is verified directly that the peripheral point spectrum of the Frobenius-Perron operator and the point spectrum of the Koopman operator are fully cyclic. Under some restrictions on the underlying transformation, the Frobenius-Perron operator is known to be a well defined linear operator on the Banach space of functions of bounded variation. It is also shown that the peripheral point spectrum of the Frobenius-Perron operator on the functions of bounded variation is fully cyclic.

Includes abstract. Includes bibliographical references.

No description available.

Pairwise comparison matrices (PCMs) play a key role in multi-criteria decision making, especially in the analytic hierarchy process. It could be necessary for an expert to compare alternatives based on various criteria. However, for a variety of reasons, such as lack of time or insufficient knowledge, it may happen that the expert cannot provide judgments on all pairs of alternatives. In this case, an incomplete pairwise comparison matrix is formed. In the first research part, an optimization algorithm is proposed for the optimal completion of an incomplete PCM. It is intended to numerically minimize a constrained eigenvalue problem, in which the objective function is difficult to write explicitly in terms of variables. Numerical simulations are carried out to examine the performance of the algorithm. The simulation results show that the proposed algorithm is capable of solving the minimization of the constrained eigenvalue problem. In the second part, a comparative analysis of eleven completion methods is studied. The similarity of the eleven completion methods is analyzed on the basis of numerical simulations and hierarchical clustering. Numerical simulations are performed for PCMs of different orders considering various numbers of missing comparisons. The results suggest the existence of a cluster of five extremely similar methods, and a method significantly dissimilar from all the others. In the third part, the filling in patterns (arrangements of known comparisons) of incomplete PCMs based on their graph representation are investigated under given conditions: regularity, diameter and number of vertices, but without prior information. Regular and quasi-regular graphs with minimal diameter are proposed. Finally, the simulation results indicate that the proposed graphs indeed provide better weight vectors than alternative graphs with the same number of comparisons. This research problem’s contributions include a list of (quasi-)regular graphs with diameters of 2 and 3, and vertices from 5 up to 24.

Cette recherche interroge la monarchie française en situation de crise en partant d’un pari politique hors norme, celui des prélats catholiques qui misèrent sur Henri IV, roi protestant. Elle étudie les diverses facettes de l’action politique de ces hommes et reconstruit les mécanismes de leur travail de légitimation du premier Bourbon, en privilégiant les premières années du règne. Centrer l’enquête sur ces années permet de restituer à cette période sa dimension d’incertitude vécue par les acteurs de la monarchie, qui se trouve généralement écrasée par le poids de l’histoire de la pacification, après l’édit de Nantes. Ce choix d’un temps court rend possible l’étude attentive des cérémonies possédant une grande importance symbolique, tels que l’abjuration et le sacre royaux. Trop souvent ces événements sont uniquement décrits, racontés par l’historiographie. L’analyse proposée ici s’attache à l’inverse à leur redonner leur dimension problématique, à réfléchir sur les choix stratégiques faits par le pouvoir, notamment en ce qui concerne leur publication, comme une seconde mise en scène, imprimée. En adoptant un angle d’observation centré sur l’engagement, tantôt exposé, tantôt discret du groupe de prélats (Jacques du Perron, Claude d’Angennes et leurs pairs), il devient possible d’appréhender la monarchie en tant qu’œuvre collective d’acteurs multiples qui agissent pour assurer sa survie. En proposant ainsi une alternative à la vision navarro-centrée qui domine largement l’historiographie, cette approche permet d’aborder d’une nouvelle façon la sortie des guerres de Religion et de révéler des acteurs peu connus, qui néanmoins jouent un rôle crucial dans ce processus. / This dissertation investigates the French monarchy during a moment of crisis, focusing on an exceptional political bet made by a number of catholic prelates who chose to support Henri IV, a Protestant king. Their varied political actions are studied here, and the mechanisms of their work of legitimation of the first Bourbon are reconstructed, with a particular attention to the first years of his reign. The emphasis on these years offers the opportunity to give back to this period its dimension of uncertainty, as lived by the actors of the monarchy, a dimension that is generally erased under the weight of the history of the pacification, beginning with the Edict of Nantes. The choice of a short period allows a careful analysis of ceremonies of great symbolic importance, such as the royal abjuration and coronation. Too often these events have been merely narrated by historiography. This analysis, however, seeks to reconstruct their problematic dimension. Specific attention will be paid to the choices made when these events were published, which constituted a second staging of the act in printed form. With the focal point placed on the political commitment of the prelates, which at times was explicit, and at other times remained discreetly hidden away, it becomes possible to understand the monarchy as the collective work of multiple actors who endeavoured to ensure its survival. Thus, by proposing an alternative reading of events to the Navarro-centric vision that largely dominates historiography, this approach discusses the end of the Wars of Religion from a new perspective, which uncovers lesser known actors, who nonetheless played a crucial role in this process.