Whole-brain anatomical connectivity in living humans can be modeled as a network with diffusion-MRI and tractography. Network nodes are associated with distinct grey-matter regions, while white-matter fiber bundles serve as interconnecting network links. However, the lack of a gold standard for regional parcellation in brain MRI makes the definition of nodes arbitrary, meaning that network nodes are defined using templates employing either random or anatomical parcellation criteria. Consequently, the number of nodes included in networks studied by different authors has varied considerably, from less than 100 up to more than 10(4). Here, we systematically and quantitatively assess the behavior, structure and topological attributes of whole-brain anatomical networks over a wide range of nodal scales, a variety of grey-matter parcellations as well as different diffusion-MRI acquisition protocols. We show that simple binary decisions about network organization, such as whether small-worldness or scale-freeness is evident, are unaffected by spatial scale, and that the estimates of various organizational parameters (e.g. small-worldness, clustering, path length, and efficiency) are consistent across different parcellation scales at the same resolution (i.e. the same number of nodes). However, these parameters vary considerably as a function of spatial scale; for example small-worldness exhibited a difference of 95% between the widely-used automated anatomical labeling (AAL) template (approximately 100 nodes) and a 4000-node random parcellation (sigma(AAL)=1.9 vs. sigma(4000)=53.6+/-2.2). These findings indicate that any comparison of network parameters across studies must be made with reference to the spatial scale of the nodal parcellation.