High-level cognitive processes, such as creative thinking, are still far from understood. Here, I focus on the role of the mental lexicon in realizing such complex, high-level capacities. Specifically, I focus on two related constructs – creative thinking and the personality trait Openness to Experience. I examine whether the way individuals search their memory can predict their levels of Openness and creativity. This is achieved by harnessing computational tools from network science and machine learning to develop prediction and classification models of Openness and creativity, based on performance on a common verbal fluency task, where participants have one minute to generate synonyms to the word hot. This synonym task is operationalized as a mental navigation task over a multidimensional representation of the mental lexicon – a cognitive multiplex network. In this cognitive multiplex network, nodes represent concepts, which are connected to each other across different layers of information (phonological, associative, semantic, and hypernym/hyponym layers). in Study 1, I examined the feasibility of using a cognitive multiplex network to classify and predict Openness. For each participant (N = 163), I compute various features of their mental navigation over the cognitive multiplex network, and use these features in building classification and prediction models. I find high accuracy in classifying participants into low- and high- Openness groups (75% classification accuracy), and good prediction ability of our model to predict individual differences in Openness (r = .31). These results support the use of computational modelling for the study and prediction of personality traits, based on cognitive capacities. In addition, our results suggest that people high in Openness engage in a distinct style of cognitive search through their mental lexicon, potentially supporting their heightened ability to think creatively. In Study 2, I will apply a similar method aiming to classify and predict creativity. Together, both studies will demonstrate the role of the mental lexicon in complex human behavior.