Individual differences are known to modulate brain responses to music. Recent neuroscience research suggests that each individual has unique and fundamentally stable functional brain connections irrespective of the task they perform. 77 participants’ functional Magnetic Resonance Imaging (fMRI) responses were measured while continuously listening to music. Using a graph-theory-based approach, we modeled whole-brain functional connectivity. We then calculate voxel-wise eigenvector centrality and subsequently use it to classify gender and musical expertise using binary Support Vector Machine (SVM). We achieved a cross-validated classification accuracy of 97% and 96% for gender and musical expertise, respectively. We also identify regions that contribute most to this classification. Thus, this study demonstrates that individual differences can be decoded from brain responses to music using a graph-based method with near-perfect precision.