Probabilistic Transitive Closure of Fuzzy Cognitive Maps: Algorithm Enhancement and an Application to Work-Integrated Learning

Abstract

A fuzzy cognitive map (FCM) is made up of factors and direct impacts. In graph theory, a bipolar weighted digraph is used to model an FCM; its vertices represent the factors, and the arcs represent the direct impacts. Each direct impact is either positive or negative, and is assigned a weight; in the model considered in this thesis, each weight is interpreted as the probability of the impact. A directed walk from factor F to factor F' is interpreted as an indirect impact of F on F'. The probabilistic transitive closure (PTC) of an FCM (or bipolar weighted digraph) is a bipolar weighted digraph with the same set of factors, but with arcs corresponding to the indirect impacts in the given FCM. Fuzzy cognitive maps can be used to represent structured knowledge in diverse fields, which include science, engineering, and the social sciences. In [P. Niesink, K. Poulin, M. Sajna, Computing transitive closure of bipolar weighted digraphs, Discrete Appl. Math. 161 (2013), 217-243], it was shown that the transitive closure provides valuable new information for its corresponding FCM. In particular, it gives the total impact of each factor on each other factor, which includes both direct and indirect impacts. Furthermore, several algorithms were developed to compute the transitive closure of an FCM. Unfortunately, computing the PTC of an FCM is computationally hard and the implemented algorithms are not successful for large FCMs. Hence, the Reduction-Recovery Algorithm was proposed to make other (direct) algorithms more efficient. However, this algorithm has never been implemented before. In this thesis, we code the Reduction-Recovery Algorithm and compare its running time with the existing software. Also, we propose a new enhancement on the existing PTC algorithms, which we call the Separation-Reduction Algorithm. In particular, we state and prove a new theorem that describes how to reduce the input digraph to smaller components by using a separating vertex. In the application part of the thesis, we show how the PTC of an FCM can be used to compare different standpoints on the issue of work-integrated learning.