This study aimed to compare brain structural connectivity using graph theory between patients with alcohol dependence and social drinkers. The participants were divided into two groups; the alcohol group (N=23) consisting of patients who had been hospitalized and had abstained from alcohol for at least three months and the control group (N=22) recruited through advertisements and were social drinkers. All participants were evaluated using 3T magnetic resonance imaging. A total of 1000 repeated whole-brain tractographies with random parameters were performed using DSI Studio. Four hundred functionally defined cortical regions of interest (ROIs) were parcellated using FreeSurfer based on the Schaefer Atlas. The ROIs were overlaid on the tractography results to generate 1000 structural connectivity matrices per person, and 1000 matrices were averaged into a single matrix per subject. Graph analysis was performed through igraph R package. Graph measures were compared between the two groups using analysis of covariance, considering the effects of age and smoking pack years. The alcohol group showed lower local efficiency than the control group in the whole-brain (F=5.824, p=0.020), somato-motor (F=5.963, p=0.019), and default mode networks (F=4.422, p=0.042). The alcohol group showed a lower global efficiency (F=5.736, p=0.021) in the control network. The transitivity of the alcohol group in the dorsal attention network was higher than that of the control (F=4.257, p=0.046). Our results imply that structural stability of the whole-brain network is affected in patients with alcohol dependence, which can lead to ineffective information processing in cases of local node failure.