Chong, SY, Tiňo, P and He, J ORCID: https://orcid.org/0000-0002-5616-4691, 2019. Coevolutionary systems and PageRank. Artificial Intelligence, 277: 103164. ISSN 0004-3702
Preview |
Text
14811_He.pdf - Post-print Download (1MB) | Preview |
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. In competitive settings, agents choose which solutions to implement and outcomes from their behavioral interactions express preferences between the solutions. Recently, we have introduced a framework that provides both qualitative and quantitative characterizations of competitive coevolutionary systems. 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 modeled as random walks on the digraph. However, one needs to obtain prior, qualitative knowledge of the underlying structures of these coevolutionary digraphs to perform quantitative characterizations on coevolutionary systems and interpret the results. Here, we study a deep connection between coevolutionary systems and PageRank to address this issue. We develop a principled approach to measure and rank the performance (importance) of solutions (vertices) in a given coevolutionary digraph. 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). In this manner, PageRank authority indicates the importance of a vertex. PageRank authorities with suitable normalization have a natural interpretation of long-term visitation probabilities over the digraph by the coevolutionary random walk. We derive closed-form expressions to calculate PageRank authorities for any coevolutionary digraph. We can precisely quantify changes to the authorities due to modifications in restart probability for any coevolutionary system. Our empirical studies demonstrate how PageRank authorities characterize coevolutionary digraphs with different underlying structures.
Item Type: | Journal article |
---|---|
Publication Title: | Artificial Intelligence |
Creators: | Chong, S.Y., Tiňo, P. and He, J. |
Publisher: | Elsevier |
Date: | December 2019 |
Volume: | 277 |
ISSN: | 0004-3702 |
Identifiers: | Number Type 10.1016/j.artint.2019.103164 DOI S0004370218305848 Publisher Item Identifier |
Divisions: | Schools > School of Science and Technology |
Record created by: | Jonathan Gallacher |
Date Added: | 12 Sep 2019 14:14 |
Last Modified: | 31 May 2021 15:17 |
URI: | https://irep.ntu.ac.uk/id/eprint/37649 |
Actions (login required)
Edit View |
Statistics
Views
Views per month over past year
Downloads
Downloads per month over past year