This work addresses brain network analysis considering different clinical severity stages of cognitive dysfunction, based on resting-state electroencephalography (EEG). We use a cohort acquired in real-life clinical conditions, which contains EEG data of subjective cognitive impairment (SCI) patients, mild cognitive impairment (MCI) patients, and Alzheimer’s disease (AD) patients. We propose to exploit an epoch-based entropy measure to quantify the connectivity links in the networks. This entropy measure relies on a refined statistical modeling of EEG signals with Hidden Markov Models, which allow a better estimation of the spatiotemporal characteristics of EEG signals. We also propose to conduct a comparative study by considering three other measures largely used in the literature: phase lag index, coherence, and mutual information. We calculated such measures at different frequency bands and computed different local graph parameters considering different proportional threshold values for a binary network analysis. After applying a feature selection procedure to determine the most relevant features for classification performance with a linear Support Vector Machine algorithm, our study demonstrates the effectiveness of the statistical entropy measure for analyzing the brain network in patients with different stages of cognitive dysfunction.