  We study the link structure of on-line social networks (OSNs), and introduce
a new model for such networks which may help infer their hidden underlying
reality. In the geo-protean (GEO-P) model for OSNs nodes are identified with
points in Euclidean space, and edges are stochastically generated by a mixture
of the relative distance of nodes and a ranking function. With high
probability, the GEO-P model generates graphs satisfying many observed
properties of OSNs, such as power law degree distributions, the small world
property, densification power law, and bad spectral expansion. We introduce the
dimension of an OSN based on our model, and examine this new parameter using
actual OSN data. We discuss how the geo-protean model may eventually be used as
a tool to group users with similar attributes using only the link structure of
the network.

Physics and Society;Social and Information Networks;Combinatorics