Coevolutionary systems and PageRank

Research output: Contribution to journalArticle

Colleges, School and Institutes

External organisations

  • University of Nottingham Malaysia Campus
  • Nottingham Trent University, Nottingham

Abstract

Coevolutionary systems have been used successfully in various problem domains involving situations of strategic decision-making. Central to these systems is a mechanism whereby finite populations of agents compete for reproduction and
adapt in response to their interaction outcomes. Outcomes from their behavioral interactions express preferences over the candidate solutions they implement in competitive settings. A recent framework for precise characterizations of competitive coevolutionary systems was introduced. Its two main features are: (1) A directed graph (digraph) representation that fully captures the underlying structure arising from pairwise preferences over solutions. (2) Coevolutionary
processes are modelled as random walks on the digraph. Here, we study a deep connection between coevolutionary systems and PageRank, and develop a principled approach to measure and rank the performance (importance) of solutions (vertices) in coevolutionary digraphs. In PageRank formalism, B transfers part of its authority to A if A dominates B (there is an arc from B to A in the digraph), and so PageRank authority indicates the importance of a vertex. Upon suitable normalization, PageRank authorities have a natural interpretation of long-term visitation probabilities over the digraph by the coevolutionary random walk. We prove that PageRank for any coevolutionary system exists and derive closed-form expressions to calculate PageRank authorities. Changes to PageRank authorities due to changes in restart probability setting for any coevolutionary system are quantified precisely. Furthermore, PageRank authorities can be approximated effectively and our empirical studies show how they characterize coevolutionary digraphs with different underlying structures.

Details

Original languageEnglish
Article number103164
Number of pages46
JournalArtificial Intelligence
Publication statusPublished - 30 Aug 2019

Keywords

  • Coevolutionary systems, PageRank, Markov chains