Alcohol dependence (AD) is characterized by corticostriatal impairments in individual brain areas such as the striatum. As yet however, complex brain network topology in AD and its association with disease progression are unknown. We applied graph theory to resting-state functional magnetic resonance imaging (RS-fMRI) to examine weighted global efficiency and local (clustering coefficient, degree, eigenvector centrality) network topology and the functional role of the striatum in 24 AD patients compared with 20 matched healthy controls (HC), and their association with dependence characteristics. Graph analyses were performed based on Pearson’s correlations between RS-fMRI timeseries, while correcting for age, gender and head motion. We found no significant group differences between AD patients and HC in network topology. Notably, within the patient group, but not in HC, the whole-brain network showed reduced average cluster coefficient with more severe alcohol use, whereas longer AD duration was associated with a global decrease in efficiency, degree and clustering coefficient. Additionally, within 4 a-priori chosen bilateral striatal nodes, alcohol use severity was associated with lower clustering coefficient in the left caudate. Longer AD duration was associated with reduced clustering coefficient in caudate and putamen, and reduced degree in bilateral caudate, but with increased eigenvector centrality in left posterior putamen. Especially changes in global network topology and clustering coefficient in anterior striatum remained strikingly robust after exploratory variations in network weight. Our results show adverse effects of AD on overall network integration and possibly on striatal efficiency, putatively contributing to the increasing behavioral impairments seen in chronically addicted patients.