An Efficient Visibility Graph Similarity Algorithm and Its Application on Sleep Stages Classification

This paper presents an efficient horizontal visibility directed graph similarity algorithm (HVDS) by taking the advantages of two synchronization measuring methods in graph theory: phase locking value (PLV) and visibility graph similarity (VGS). It develops a new linear horizontal visibility graph constructing algorithm, analyzes its constructing complexity, and tests its feature performance via the sleep stages identification application. Six features are extracted, separately, from HVDS, PLV and VGS as the input to a support vector machine to classify the seven sleep stages. 11,120 data segments are used for the experiments with each segment lasts 30 seconds. The training sets are selected from a single subject and the testing sets are selected from multiple subjects. 10-cross-validation is employed to evaluate the performances of the PLV, VGS and HVDS methods. The experimental results show that the PLV, VGS and HVDS algorithms produce an average classification accuracy of 72.3%, 81.5% and 82.6%, respectively. The speed of the HVDS is 39 times faster than the VGS algorithm.