Introduction: The early diagnosis and classification of social anxiety disorder (SAD) are crucial clinical support tasks for medical practitioners in designing patient treatment programs to better supervise the progression and development of SAD. This paper proposes an effective method to classify the severity of SAD into different grading (severe, moderate, mild, and control) by using the patterns of brain information flow with their corresponding graphical networks. Methods: We quantified the directed information flow using partial directed coherence (PDC) and the topological networks by graph theory measures at four frequency bands (delta, theta, alpha, and beta). The PDC assesses the causal interactions between neuronal units of the brain network. Besides, the graph theory of the complex network identifies the topological structure of the network. Resting-state electroencephalogram (EEG) data were recorded for 66 patients with different severities of SAD (22 severe, 22 moderate, and 22 mild) and 22 demographically matched healthy controls (HC). Results: PDC results have found significant differences between SAD groups and HCs in theta and alpha frequency bands (p < 0.05). Severe and moderate SAD groups have shown greater enhanced information flow than mild and HC groups in all frequency bands. Furthermore, the PDC and graph theory features have been used to discriminate three classes of SAD from HCs using several machine learning classifiers. In comparison to the features obtained by PDC, graph theory network features combined with PDC have achieved maximum classification performance with accuracy (92.78), sensitivity (95.25), and specificity (94.12) using Support Vector Machine (SVM). Discussion: Based on the results, it can be concluded that the combination of graph theory features and PDC values may be considered an effective tool for SAD identification. Our outcomes may provide new insights into developing biomarkers for SAD diagnosis based on topological brain networks and machine learning algorithms. Copyright © 2023 Al-Ezzi, Kamel, Al-Shargabi, Al-Shargie, Al-Shargabi, Yahya and Al-Hiyali.