The purpose of this study was to demonstrate the potential alterations in structural network properties related to physical activity (PA) in healthy elderly. We recruited 76 elderly individuals with normal cognition from Samsung Medical Center in Seoul, Korea. All participants underwent the Cambridge Neuropsychological Test Automated Battery and 3.0T brain magnetic resonance imaging (MRI). Participants were subdivided into quartiles according to the International Physical Activity Questionnaire scores, which represents the amount of PA. Through graph theory based analyses, we compared global and local network topologies according to PA quartile. The higher PA group demonstrated better performance in speed processing compared to the lower PA group. Regional nodal strength also significantly increased in the higher PA group, which involved the bilateral middle frontal, bilateral inferior parietal, right medial orbitofrontal, right superior and middle temporal gyri. These results were further replicated when the highest and the lowest quartile groups were compared in terms of regional nodal strengths and local efficiency. Our findings that the regional nodal strengths associated with the attentional network were increased in the higher PA group suggest the preventive effects of PA on age-related cognitive decline, especially in attention.