本篇論文研究演化的動態過程中的隨機穩定性。演化過程中,突變(mutation)或變異隨時可能會發生。因此,演化中不存在安定(steady)或是穩定(stable)的狀態。但是當突變機率趨近於零時,有些狀態在長期間比其他狀態容易出現在過程中為人所觀察到。這些狀態稱為隨機穩定狀態(stochastically stable state)。我們發展出一具有一般性的演算法來找出所有的隨機穩定狀態。有別於傳統演算法,這套演算法大幅降低計算所需次數。透過這套演算法,我們定義了一個集合: stable set。我們發現,stable set包涵了所有的隨機穩定狀態。同時,我們也提出數個隨機穩定狀態的充份條件。這些發現代表著,分析演化模型的假設及均衡(equilibria)性質之間的關係是可行的。 / We study the behaviors of the evolutionary models with persistant noises through a general algorithm which describes the relationships among the stochastic potentials. That is, by constructing a closed loop on the graph of the directed trees, we show that the comparison among the stochastic potential is equivalent to the comparison among one-step transition costs. Hence, we are able to systematically analyze the properties of the stochastically stable states. Our main nding is that the set of the stochastically stable states is contained in a set, which we dene as a stable set. Each state in this set is difcult to escape from and is resistant to the attraction of any other states in the stable set. Based on this nding, related sufficient conditions for the stochastically stable states are presented, and some results in the literature are also reinterpreted. In addition, we show that this algorithm drastically reduces the necessary steps for characterizing the stochastically stable states. This means that the analysis on relationships between the assumptions of the model and the properties of equilibria are possible and promising.

京都大学 / 0048 / 新制・課程博士 / 博士(人間・環境学) / 甲第19200号 / 人博第741号 / 新制||人||178(附属図書館) / 27||人博||741(吉田南総合図書館) / 32192 / 京都大学大学院人間・環境学研究科共生人間学専攻 / (主査)教授 宇敷 重廣, 教授 森本 芳則, 准教授 木坂 正史 / 学位規則第4条第1項該当 / Doctor of Human and Environmental Studies / Kyoto University / DGAM

This thesis contains four essays that analyze the behaviors that evolve when populations of boundedly rational individuals interact strategically for a long period of time. Individuals are boundedly rational in the sense that their strategy choices are determined by simple rules of adaptation -- learning rules. Convergence results for general finite games are first obtained in a homogenous setting, where all populations consist either of stochastic imitators, who almost always imitate the most successful strategy in a sample from their own population's past strategy choices, or stochastic better repliers, who almost always play a strategy that gives at least as high expected payoff as a sample distribution of all populations' past play. Similar results are then obtained in a heterogeneous setting, where both of these learning rules are represented in each population. It is found that only strategies in certain sets are played in the limit, as time goes to infinity and the mutation rate tends to zero. Sufficient conditions for the selection of a Pareto efficient such set are also provided. Finally, the analysis is extended to natural selection among learning rules. The question is whether there exists a learning rule that is evolutionarily stable, in the sense that a population employing this learning rule cannot be invaded by individuals using a different rule. Monte Carlo simulations for a large class of learning rules and four different games indicate that only a learning rule that takes full account of hypothetical payoffs to strategies that are not played is evolutionarily stable in almost all cases. / Diss. Stockholm : Handelshögsk., 2001

Dans cette thèse, nous nous intéressons à la stabilisation par rétroaction des systèmes quantiques ouverts soumis à des mesures imparfaites en temps continu. Tout d'abord, nous introduisons la théorie du filtrage quantique pour décrire l'évolution temporelle de l'opérateur de densité conditionnelle représentant un état quantique en interaction avec un environnement. Ceci est décrit par une équation différentielle stochastique à valeurs matricielles. Deuxièmement, nous étudions le comportement asymptotique des trajectoires quantiques associées à des systèmes de spin à N niveaux pour des états initiaux donnés, pour les cas avec et sans loi de rétroaction. Dans le cas sans loi de rétroaction, nous montrons la propriété de réduction de l'état quantique à vitesse exponentielle. Ensuite, nous fournissons des conditions suffisantes sur la loi de contrôle assurant une convergence presque sûre vers un état pur prédéterminé correspondant à un vecteur propre de l'opérateur de mesure. Troisièmement, nous étudions le comportement asymptotique des trajectoires de systèmes ouverts à plusieurs qubits pour des états initiaux donnés. Dans le cas sans loi de rétroaction, nous montrons la réduction exponentielle de l'état quantique pour les systèmes N-qubit avec deux canaux quantiques. Dans le cas particulier des systèmes à deux qubits, nous donnons des conditions suffisantes sur la loi de contrôle assurant la convergence asymptotique vers un état cible de Bell avec un canal quantique, et la convergence exponentielle presque sûre vers un état cible de Bell avec deux canaux quantiques. Ensuite, nous étudions le comportement asymptotique des trajectoires des systèmes quantiques ouverts de spin-1/2 avec les états initiaux inconnus soumis à des mesures imparfaites en temps continu, et nous fournissons des conditions suffisantes au contrôleur pour garantir la convergence de l'état estimé vers l'état quantique réel lorsque le temps tend vers l'infini. En conclusion, nous discutons de manière heuristique du problème de stabilisation exponentielle des systèmes de spin à N niveaux avec les états initiaux inconnus et nous proposons des lois de rétroaction candidates afin de stabiliser le système de manière exponentielle. / In this thesis, we focus on the feedback stabilization of open quantum systems undergoing imperfect continuous-time measurements. First, we introduce the quantum filtering theory to obtain the time evolution of the conditional density operator representing a quantum state in interaction with an environment. This is described by a matrix-valued stochastic differential equation. Second, we study the asymptotic behavior of quantum trajectories associated with N-level quantum spin systems for given initial states, for the cases with and without feedback law. For the case without feedback, we show the exponential quantum state reduction. Then, we provide sufficient conditions on the feedback control law ensuring almost sure exponential convergence to a predetermined pure state corresponding to an eigenvector of the measurement operator. Third, we study the asymptotic behavior of trajectories of open multi-qubit systems for given initial states. For the case without feedback, we show the exponential quantum state reduction for N-qubit systems with two quantum channels. Then, we focus on the two-qubit systems, and provide sufficient conditions on the feedback control law ensuring asymptotic convergence to a target Bell state with one quantum channel, and almost sure exponential convergence to a target Bell state with two quantum channels. Next, we investigate the asymptotic behavior of trajectories of open quantum spin-1/2 systems with unknown initial states undergoing imperfect continuous-time measurements, and provide sufficient conditions on the controller to guarantee the convergence of the estimated state towards the actual quantum state when time goes to infinity. Finally, we discuss heuristically the exponential stabilization problem for N-level quantum spin systems with unknown initial states and propose candidate feedback laws to stabilize exponentially the system.

A hybrid system is a dynamical system that exhibits both continuous and discrete dynamic behavior. Hybrid systems arise in a wide variety of important applications in diverse areas, ranging from biology to computer science to air traffic dynamics. The interaction of continuous- and discrete-time dynamics in a hybrid system often leads to very rich dynamical behavior and phenomena that are not encountered in purely continuous- or discrete-time systems. Investigating the dynamical behavior of hybrid systems is of great theoretical and practical importance. The objectives of this thesis are to develop the qualitative theory of nonlinear hybrid systems with impulses, time-delay, switching modes, and stochastic disturbances, to develop algorithms and perform analysis for hybrid systems with an emphasis on stability and control, and to apply the theory and methods to real-world application problems. Switched nonlinear systems are formulated as a family of nonlinear differential equations, called subsystems, together with a switching signal that selects the continuous dynamics among the subsystems. Uniform stability is studied emphasizing the situation where both stable and unstable subsystems are present. Uniformity of stability refers to both the initial time and a family of switching signals. Stabilization of nonlinear systems via state-dependent switching signal is investigated. Based on assumptions on a convex linear combination of the nonlinear vector fields, a generalized minimal rule is proposed to generate stabilizing switching signals that are well-defined and do not exhibit chattering or Zeno behavior. Impulsive switched systems are hybrid systems exhibiting both impulse and switching effects, and are mathematically formulated as a switched nonlinear system coupled with a sequence of nonlinear difference equations that act on the switched system at discrete times. Impulsive switching signals integrate both impulsive and switching laws that specify when and how impulses and switching occur. Invariance principles can be used to investigate asymptotic stability in the absence of a strict Lyapunov function. An invariance principle is established for impulsive switched systems under weak dwell-time signals. Applications of this invariance principle provide several asymptotic stability criteria. Input-to-state stability notions are formulated in terms of two different measures, which not only unify various stability notions under the stability theory in two measures, but also bridge this theory with the existent input/output theories for nonlinear systems. Input-to-state stability results are obtained for impulsive switched systems under generalized dwell-time signals. Hybrid time-delay systems are hybrid systems with dependence on the past states of the systems. Switched delay systems and impulsive switched systems are special classes of hybrid time-delay systems. Both invariance property and input-to-state stability are extended to cover hybrid time-delay systems. Stochastic hybrid systems are hybrid systems subject to random disturbances, and are formulated using stochastic differential equations. Focused on stochastic hybrid systems with time-delay, a fundamental theory regarding existence and uniqueness of solutions is established. Stabilization schemes for stochastic delay systems using state-dependent switching and stabilizing impulses are proposed, both emphasizing the situation where all the subsystems are unstable. Concerning general stochastic hybrid systems with time-delay, the Razumikhin technique and multiple Lyapunov functions are combined to obtain several Razumikhin-type theorems on both moment and almost sure stability of stochastic hybrid systems with time-delay. Consensus problems in networked multi-agent systems and global convergence of artificial neural networks are related to qualitative studies of hybrid systems in the sense that dynamic switching, impulsive effects, communication time-delays, and random disturbances are ubiquitous in networked systems. Consensus protocols are proposed for reaching consensus among networked agents despite switching network topologies, communication time-delays, and measurement noises. Focused on neural networks with discontinuous neuron activation functions and mixed time-delays, sufficient conditions for existence and uniqueness of equilibrium and global convergence and stability are derived using both linear matrix inequalities and M-matrix type conditions. Numerical examples and simulations are presented throughout this thesis to illustrate the theoretical results.

A hybrid system is a dynamical system that exhibits both continuous and discrete dynamic behavior. Hybrid systems arise in a wide variety of important applications in diverse areas, ranging from biology to computer science to air traffic dynamics. The interaction of continuous- and discrete-time dynamics in a hybrid system often leads to very rich dynamical behavior and phenomena that are not encountered in purely continuous- or discrete-time systems. Investigating the dynamical behavior of hybrid systems is of great theoretical and practical importance. The objectives of this thesis are to develop the qualitative theory of nonlinear hybrid systems with impulses, time-delay, switching modes, and stochastic disturbances, to develop algorithms and perform analysis for hybrid systems with an emphasis on stability and control, and to apply the theory and methods to real-world application problems. Switched nonlinear systems are formulated as a family of nonlinear differential equations, called subsystems, together with a switching signal that selects the continuous dynamics among the subsystems. Uniform stability is studied emphasizing the situation where both stable and unstable subsystems are present. Uniformity of stability refers to both the initial time and a family of switching signals. Stabilization of nonlinear systems via state-dependent switching signal is investigated. Based on assumptions on a convex linear combination of the nonlinear vector fields, a generalized minimal rule is proposed to generate stabilizing switching signals that are well-defined and do not exhibit chattering or Zeno behavior. Impulsive switched systems are hybrid systems exhibiting both impulse and switching effects, and are mathematically formulated as a switched nonlinear system coupled with a sequence of nonlinear difference equations that act on the switched system at discrete times. Impulsive switching signals integrate both impulsive and switching laws that specify when and how impulses and switching occur. Invariance principles can be used to investigate asymptotic stability in the absence of a strict Lyapunov function. An invariance principle is established for impulsive switched systems under weak dwell-time signals. Applications of this invariance principle provide several asymptotic stability criteria. Input-to-state stability notions are formulated in terms of two different measures, which not only unify various stability notions under the stability theory in two measures, but also bridge this theory with the existent input/output theories for nonlinear systems. Input-to-state stability results are obtained for impulsive switched systems under generalized dwell-time signals. Hybrid time-delay systems are hybrid systems with dependence on the past states of the systems. Switched delay systems and impulsive switched systems are special classes of hybrid time-delay systems. Both invariance property and input-to-state stability are extended to cover hybrid time-delay systems. Stochastic hybrid systems are hybrid systems subject to random disturbances, and are formulated using stochastic differential equations. Focused on stochastic hybrid systems with time-delay, a fundamental theory regarding existence and uniqueness of solutions is established. Stabilization schemes for stochastic delay systems using state-dependent switching and stabilizing impulses are proposed, both emphasizing the situation where all the subsystems are unstable. Concerning general stochastic hybrid systems with time-delay, the Razumikhin technique and multiple Lyapunov functions are combined to obtain several Razumikhin-type theorems on both moment and almost sure stability of stochastic hybrid systems with time-delay. Consensus problems in networked multi-agent systems and global convergence of artificial neural networks are related to qualitative studies of hybrid systems in the sense that dynamic switching, impulsive effects, communication time-delays, and random disturbances are ubiquitous in networked systems. Consensus protocols are proposed for reaching consensus among networked agents despite switching network topologies, communication time-delays, and measurement noises. Focused on neural networks with discontinuous neuron activation functions and mixed time-delays, sufficient conditions for existence and uniqueness of equilibrium and global convergence and stability are derived using both linear matrix inequalities and M-matrix type conditions. Numerical examples and simulations are presented throughout this thesis to illustrate the theoretical results.

Το θέμα της παρούσας μεταπτυχιακής διπλωματικής εργασίας είναι η εφαρμογή της θεωρίας των Σχεδόν Πλήρως Αναλυόμενων Στοχαστικών Συστημάτων (Nearly Completely Decomposable) σε μία σειρά προβλημάτων στα οποία παραδοσιακές προσεγγίσεις αποδεικνύονται ερμηνευτικά στείρες και υπολογιστικά κοστοβόρες. Στο πρώτο μέρος της διπλωματικής αφού κάνουμε μία διαισθητικού τύπου παρουσίαση της ιδέας της decomposability και συνοψίσουμε τα απαραίτητα στοιχεία του θεωρητικού υποβάθρου που χρησιμοποιούμε στα πλαίσια της εργασίας, παραθέτουμε τονπυρήνα της θεωρίας της decomposability, όπως αυτή θεμελιώνεται μαθηματικά από τον Courtois στην κλασική του μονογραφία. Τέλος, παραθέτουμε και μία υλοποίηση του KMS αλγορίθμου Συσσωμάτωσης/Αποσυσσωμάτωσης, για τη λύση NCD συστημάτων. Το δεύτερο μέρος του συγγράμματος, είναι αφιερωμένο στην εφαρμογή της NCD σε δύο ενδιαφέροντα προβλήματα εκτίμησης απόδοσης υπολογιστικών συστημάτων. Συγκεκριμένα, μελετούμε μία ιδιότυπη ουρά που εξυπηρετεί πελάτες διαφορετικών κλάσεων, με τις ανά κλάση αφίξεις να χαρακτηρίζονται από εναλλαγές μεταξύ περιόδων ηρεμίας και κινητικότητας και την εξυπηρέτηση να γίνεται σε δέσμες πελατών της ίδιας κλάσης. Το κίνητρο για τη μελέτη αυτής της ουράς εντοπίζεται στη bursty φύση της μεταγωγής πακέτων στα σύγχρονα δίκτυα αλλά και στους reassembly buffers των multicluster πολυεπεξεργαστικών συστημάτων. Η ανάλυση της ουράς με παραδοσιακές τεχνικές οδηγεί αναπόφευκτα σε μαρκοβιανή αλυσίδα πολύ μεγάλου χώρου κατάστασης. Εμείς, ξεκινάμε από το πλήρες στοχαστικό μητρώο και αφού διαμερίσουμε κατάλληλα το χώρο καταστάσεων, αποδεικνύουμε ικανές συνθήκες υπό τις οποίες το αρχικό σύστημα είναι δυνατόν να αναλυθεί σε πολλαπλά επίπεδα υποσυστημάτων, η αυτόνομη ανάλυση των οποίων δίνει μία πολύ καλή προσέγγιση της στάσιμης κατανομής του αρχικού συστήματος. Επίσης, παραθέτουμε και αποδεικνύουμε μία ικανή συνθήκη για μηδενικό σφάλμα προσέγγισης και την ερμηνεύουμε σε όρους προδιαγραφών του προβλήματος. Τέλος, θεωρούμε μία ειδική συμμετρική εκδοχή για την οποία καταφέρνουμε να δώσουμε μία κλειστή έκφραση της κατανομής πληρότητας της ουράς συναρτήσει της λύσης των υποσυστημάτων. Για να δείξουμε την απλοποίηση της ανάλυσης που επιφέρει η χρήση του NCD μοντέλου θεωρούμε ένα σενάριο για το οποίο προχωρούμε την ανάλυση σε βάθος και καταφέρνουμε να εξάγουμε χρήσιμες μετρικές στις οποίες, σε αντίθετη περίπτωση, θα ήταν ιδιαίτερα επίπονο να καταλήξει κανείς. Συγκεκριμένα, υπολογίζουμε την πιθανότητα blocking και δείχνουμε πως αυτή μειώνεται σχεδόν εκθετικά με το μέγεθος της ουράς. Βλέπουμε τελικά πως η εκμετάλλευση της NCD ιδιότητας από τη μία διευκολύνει την ανάλυση και από την άλλη παρέχει ανεκτίμητη διαίσθηση σχετικά με τη μεταβατική συμπεριφορά του συστήματος προς την κατάσταση στατιστικής ισορροπίας. Το δεύτερο μέρος της διπλωματικής κλείνει με τη μελέτη κριτηρίων υπό τα οποία, πολυεπεξεργαστικά συστήματα που χωρίζονται σε ομάδες ισχυρά αλληλεπιδρώντων επεξεργαστών, μπορούν να αναλυθούν με χρήση της θεωρίας NCD. Είναι γνωστό πως στα δίκτυα ουρών αναμονής συγκρίσιμων ρυθμών εξυπηρέτησης, η NCD του μητρώου πιθανοτήτων δρομολόγησης συνεπάγεται την NCD του δικτύου. Εμείς, θεωρούμε μία ειδική περίπτωση τέτοιων συστημάτων για την οποία δείχνουμε ένα, εύκολο να ελεγχθεί, κριτήριο για NCD. Τέλος, εξετάζουμε βαθύτερα το σφάλμα της προσέγγισης, και χρησιμοποιώντας ένα πρόσφατο αποτέλεσμα της θεωρίας των σχεδόν ασύζευκτων μαρκοβιανών αλυσίδων δίνουμε έναν επιπλέον ποιοτικό περιορισμό που πρέπει να ικανοποιούν τα εν λόγω συστήματα για να πάρει κανείς ικανοποιητική προσέγγιση από την ανάλυσή τους σε ανεξάρτητα block. Στο τρίτο μέρος της παρούσας εργασίας, εξετάζουμε την εφαρμογή της NCD στο πρόβλημα της κατάταξης ιστοσελίδων. Η πρόσφατη έρευνα έχει σχολιάσει την ειδική δομή του στοχαστικού μητρώου που προκύπτει από το γράφο του διαδικτύου· συγκεκριμένα, οι τοπολογικές ιδιότητες της αυτοoργάνωσης του Ιστού φαίνεται να παράγουν ένα στοχαστικό μητρώο με NCD δομή. Εμείς, αφού παραθέσουμε μία σύνοψη των μαθηματικών πίσω από τον αλγόριθμο PageRank, σχολιάζουμε και δικαιολογούμε διαισθητικά την NCD δομή του Ιστού αλλά και τη φύση των υποσυστημάτων. Τέλος, προτείνουμε έναν νέο αλγόριθμο κατάταξης με το όνομα NCDawareRank, o οποίος εκμεταλλεύεται την NCD ιδιότητα για να πετύχει ποιοτικότερο και ταχύτερο ranking. Μάλιστα, δίνουμε δύο εκδοχές του αλγορίθμου, μία σειριακή και μία παράλληλη, η οποία εκμεταλλεύεται την NCD του Ιστού και υπολογιστικά. Τα οφέλη που υπόσχεται ο NCDawareRank τα επιβεβαιώνουμε και πειραματικά εκτελώντας μία σειρά από πειράματα τόσο σε τεχνητά όσο και σε πραγματικά δεδομένα, αντιπαραβάλλοντας τα αποτελέσματα μας με αυτά του αλγορίθμου PageRank. O NCDawareRank φαίνεται μάλιστα να δίνει λύση σε ένα γνωστό πρόβλημα του PageRank: αυτό της μεροληψίας εναντίον νεοεισερχομένων σελίδων. Άλλο ένα, τέλος, παράπλευρο όφελος του αλγορίθμου NCDawareRank είναι αυτό της Levelwise κατάταξης, η οποία εκτός της σημασίας που έχει αφεαυτής, μπορεί να υποδείξει εξυπνότερο crawling ή ακόμα και αποδοτικότερα σχήματα ευρετηριοποίησης του Ιστού. Στο τέταρτο και τελευταίο μέρος της διπλωματικής εφαρμόζουμε την NCD στην εύρεση των στοχαστικά ευσταθών καταστάσεων μίας κατηγορίας εξελικτικών παιγνίων στα οποία εμφανίζονται πολυεπίπεδες στρατηγικές δυναμικές. Αφού παραθέσουμε κάποιες πρόσφατες παρατηρήσεις από τη βιβλιογραφία της οικονομετρίας σχετικά με την αξιοποίηση της NCD στην προσεγγιστική ανάλυσή τους, αποδεικνύουμε συνθήκες υπό τις οποίες είναι δυνατόν να πετύχει κανείς ακριβή ανάλυση. / The purpose of this master’s thesis is the application of the theory of Nearly Completelely Decomposable stochastic systems to a number of interesting problems for which tra- ditional techniques turn out to be both intuitively unappealing and computationally in- tractable. In the first part of this work, after introducing, the concept of decomposability in an intuitive way and summarizing the essential elements of the theoretical background that is necessary to follow the rest of the text, we present the fundamental mathematical principles of NCD as established by Courtois in his classic monograph. Finally, we give an implementation of the KMS iterative aggregation/disaggregation algorithm which is commonly used for the solution of NCD systems. The second part of the dissertation is devoted to the application of NCD to two inter- esting problems of Computer Systems Performance Evaluation. Specifically, we study an uncommon discrete time queue that serves customers from different classes, with the ar- rivals of each class characterized by alternating busy and idle periods. The service is done in batches of customers of the same class. The motivation behind the study of this queue, lies in the bursty nature of packet switching, as well as in the modern reassembly buffers of multicluster multiprocessor systems. The traditional analysis techniques of this queue inevitably lead to Markov chains with very large state space. We begin with the complete stochastic matrix and after careful partitioning of the state space, we give sufficient condi- tions under which the original system can be analysed through multi level decomposition into subsystems, the autonomous analysis of which results in a very good approximation to the stationary distribution of the original system. Furthermore, we present and prove a sufficient condition for an error-free approximation and we give an interpretation of this condition in terms of the specifications of the problem. Finally, we consider a special sym- metric version of the problem, for which we manage to derive a closed-form expression for the queue’s occupancy distribution as a function of the steady state probabilities of the subsystems. To demonstrate the simplification of the analysis brought by the NCD model, we con- sider a scenario in which we proceed to an in depth analysis and we manage to extract useful metrics the derivation of which, would be considerably harder without exploiting 13 Abstract 14 NCD. Specifically, we calculate the blocking probability and we show that it decreases almost exponentially with the size of the queue. From our analysis, it is clear that the exploitation of the NCD model increases significantly our ability to understand the dy- namics of our system and to interpret aspects of its transient behaviour towards statistical equilibrium. The second part of this work ends with the study of criteria under which multipro- cessing systems, that can be divided into groups of strongly interacting processors, can be analysed using the theory of NCD. It is known that in queueing networks with servers of comparable service rates, the NCD of the routing probability matrix implies the NCD of the network. We consider a special case of such systems and we derive an easy to check criterion for NCD. Finally, we look deeper into the error analysis of this approach, and using a recent result from the theory of nearly uncoupled Markov chains, we give an addi- tional qualitative constrain to be met by these systems in order to get a good approximation of their analysis into independent blocks. In the third part of this paper, we examine the application of NCD to the problem of ranking websites. Recent research has commented on the special structure of the stochastic matrix which corresponds to the web-graph. In particular, the topological properties of the Web seems to produce a NCD stochastic matrix. Here, after presenting briefly the mathe- matical basis of PageRank, we give a linear algebraic as well as an intuitive justification of the NCD Web structure and we discuss the nature of the subsystems. Finally, we propose a new ranking algorithm named NCDawareRank, which exploits NCD in order to achieve a fairer and faster ranking. Indeed, we give two versions of the algorithm, one serial and one parallel, in which we take advantage of the computational benefits of NCD as well. The advantages of NCDawareRank are then confirmed experimentally through a series of tests on both, artificial and real data. NCDawareRank seems to solve a known problem of PageRank: the bias against new websites. Finally, another side benefit of our algorithm is that it makes it easy to extract a level-wise ranking, which besides its importance in itself, may indicate smarter crawling or even more sophisticated and efficient indexing schemes of the Web. Finally, in the fourth part of this work we apply NCD to the problem of finding the stochastically stable states of a class of evolutionary games which involve multilevel strategic dynamics. After presenting some interesting recent results coming from the lit- erature of econometrics, we give conditions under which it is possible to get the exact stochastically stable states through the use of NCD.

Neste trabalho é apresentada uma abordagem fuzzy para a estabilização de uma classe de sistemas não-lineares com parâmetros descritos por saltos Markovianos. Uma nova modelagem fuzzy de sistemas é formulada para representar esta classe de sistemas na vizinhança de pontos de operação escolhidos. A estrutura deste sistema fuzzy é composta de dois níveis, um para descrição dos saltos Markovianos e outro para descrição das não-linearidades no estado do sistema. Condições suficientes para a estabilização estocástica do sistema fuzzy considerado são derivadas usando uma função de Lyapunov acoplada. O projeto de controle fuzzy é então formulado a partir de um conjunto de desigualdades matriciais lineares. Em adição, um exemplo de aplicação, envolvendo a representação da operação de um sistema elétrico de potência em esquema de co-geração por um sistema com saltos Markovianos, é construído para validação dos resultados. / This work deals with the fuzzy-model-based control design for a class of Markovian jump nonlinear systems. A new fuzzy system modeling is proposed to approximate the dynamics of this class of systems. The structure of the new fuzzy system is composed of two levels, a crisp level which describes the Markovian jumps and a fuzzy level which describes the system nonlinearities. A sufficient condition on the existence of a stochastically stabilizing controller using a Lyapunov function approach is presented. The fuzzy-model-based control design is formulated in terms of a set of linear matrix inequalities. In addition, simulation results for a single-machine infinite-bus power system in cogeneration scheme, whose operation is modeled as an Markovian jump nonlinear system, are presented to illustrate the applicability of the technique.

Neste trabalho é apresentada uma abordagem fuzzy para a estabilização de uma classe de sistemas não-lineares com parâmetros descritos por saltos Markovianos. Uma nova modelagem fuzzy de sistemas é formulada para representar esta classe de sistemas na vizinhança de pontos de operação escolhidos. A estrutura deste sistema fuzzy é composta de dois níveis, um para descrição dos saltos Markovianos e outro para descrição das não-linearidades no estado do sistema. Condições suficientes para a estabilização estocástica do sistema fuzzy considerado são derivadas usando uma função de Lyapunov acoplada. O projeto de controle fuzzy é então formulado a partir de um conjunto de desigualdades matriciais lineares. Em adição, um exemplo de aplicação, envolvendo a representação da operação de um sistema elétrico de potência em esquema de co-geração por um sistema com saltos Markovianos, é construído para validação dos resultados. / This work deals with the fuzzy-model-based control design for a class of Markovian jump nonlinear systems. A new fuzzy system modeling is proposed to approximate the dynamics of this class of systems. The structure of the new fuzzy system is composed of two levels, a crisp level which describes the Markovian jumps and a fuzzy level which describes the system nonlinearities. A sufficient condition on the existence of a stochastically stabilizing controller using a Lyapunov function approach is presented. The fuzzy-model-based control design is formulated in terms of a set of linear matrix inequalities. In addition, simulation results for a single-machine infinite-bus power system in cogeneration scheme, whose operation is modeled as an Markovian jump nonlinear system, are presented to illustrate the applicability of the technique.