In this paper, a novel electroencephalographic (EEG)-based method is introduced for the quantification of brain-electrical connectivity changes over a longitudinal evaluation of mild cognitive impaired (MCI) subjects. In the proposed method, a dissimilarity matrix is constructed by estimating the coupling strength between every pair of EEG signals, Hierarchical clustering is then applied to group the related electrodes according to the dissimilarity estimated on pairs of EEG recordings. Subsequently, the connectivity density of the electrodes network is calculated. The technique was tested over two different coupling strength descriptors: wavelet coherence (WC) and permutation Jaccard distance (PJD), a novel metric of coupling strength between time series introduced in this paper. Twenty-five MCI patients were enrolled within a follow-up program that consisted of two successive evaluations, at time T0 and at time T1, three months later. At T1, four subjects were diagnosed to have converted to Alzheimer's Disease (AD). When applying the PJD-based method, the converted patients exhibited a significantly increased PJD (p < 0.05), i.e., a reduced overall coupling strength, specifically in delta and θ bands and in the overall range (0.5-32 Hz). In addition, in contrast to stable MCI patients, converted patients exhibited a network density reduction in every subband (delta, θ, alpha, and beta). When WC was used as coupling strength descriptor, the method resulted in a less sensitive and specific outcome. The proposed method, mixing nonlinear analysis to a machine learning approach, appears to provide an objective evaluation of the connectivity density modifications associated to the MCI-AD conversion, just processing noninvasive EEG signals.