Evolutionary Discovery of Binary-Similarity Correlations for Link Prediction

A relevant topic in complex networks research is modelling network links dynamics. Link Prediction techniques aim to assess the likelihood that a potential link will form between a pair of not connected networks nodes. The ability to forecast links formation is valuable in many application areas involving complex networks, ranging from e-commerce to biology, to social networks. Binary correlation indices are crucial in Link Prediction to assess nodes similarity for link formation. Formulating appropriate binary correlations is a time-consuming interactive and mostly empirical process, where researchers progressively evaluate and modify them to adjust their prediction ability to the specific characteristics of the network domain. Modelling the process of discovering optimal correlation indices is, therefore, a critical issue. This work proposes a novel approach based on evolutionary optimisation to determine new correlations, best suited to the domain, by the evolution of meta-correlation indices. The introduced original concept of meta-correlation index entails a parametric formula that represents classes of binary similarity indices subsuming existing ones, and generating, for appropriate parameters assignment, a particular instance of binary correlation. The proposed evolutionary framework uses the Differential Evolution algorithm for numerical optimisation. Experiments held on a variety of binary similarity measures and real network domains show that correlations, evolved from meta-correlations in the proposed framework, perform better than most previously binary correlation indices on the same domains, effectively exploring the correlation space and exploiting self-adaptive capabilities. The value of the proposed approach, obtaining satisfactory results in binary correlation discovery and adaptation to a specific domain for link prediction, is also represented by the potential extension and application to other research areas involving experimental evaluation of correlations indices.