Networks are a useful mathematical tool for capturing the complexity of the world. Using behavioral measures, we showed that human adults were sensitive to the high-level network structure underlying auditory sequences (such as communities) even when presented with incomplete information. Their performance was best explained by a mathematical model following associative learning principles and based on the integration of the transition probabilities between adjacent and non-adjacent elements with memory decay. In a follow up MEG study, we explored the neural correlates of this hypothesis. First, the comparison of the brain responses to tone transitions adhering or not to the community structure revealed an early difference, suggesting an automatic encoding of sequence structure. Second, time-resolved decoding allowed determining the duration and overlap of the representation of each tone. The decoding performance exhibited exponential decay, resulting in a significant overlap between the representations of successive tones, enabling associative learning through Hebbian rule.