  Real-world networks are often complex and large with millions of nodes,
posing a great challenge for analysts to quickly see the big picture for more
productive subsequent analysis. We aim at facilitating exploration of
node-attributed networks by creating representations with conciseness,
expressiveness, interpretability, and multi-resolution views. We develop such a
representation as a {\it map} --- among the first to explore principled network
cartography for general networks. In parallel with common maps, ours has
landmarks, which aggregate nodes homogeneous in their traits and interactions
with nodes elsewhere, and roads, which represent the interactions between the
landmarks. We capture such homogeneity by the similar roles the nodes played.
Next, to concretely model the landmarks, we propose a probabilistic generative
model of networks with roles as latent factors. Furthermore, to enable
interactive zooming, we formulate novel model-based constrained optimization.
Then, we design efficient linear-time algorithms for the optimizations.
Experiments using real-world and synthetic networks show that our method
produces more expressive maps than existing methods, with up to 10 times
improvement in network reconstruction quality. We also show that our method
extracts landmarks with more homogeneous nodes, with up to 90\% improvement in
the average attribute/link entropy among the nodes over each landmark.
Sense-making of a real-world network using a map computed by our method
qualitatively verify the effectiveness of our method.
