  The interactions among human beings represent the backbone of our societies.
How people interact, establish new connections, and allocate their activities
among these links can reveal a lot of our social organization. Despite focused
attention by very diverse scientific communities, we still lack a
first-principles modeling framework able to account for the birth and evolution
of social networks. Here, we tackle this problem by looking at social
interactions as a way to explore a very peculiar space, namely the adjacent
possible space, i.e., the set of individuals we can meet at any given point in
time during our lifetime. We leverage on a recent mathematical formalization of
the adjacent possible space to propose a first-principles theory of social
exploration based on simple microscopic rules defining how people get in touch
and interact. The new theory predicts both microscopic and macroscopic features
of social networks. The most striking feature captured on the microscopic side
is the probability for an individual, with already $k$ connections, to acquire
a new acquaintance. On the macroscopic side, the model reproduces the main
static and dynamic features of social networks: the broad distribution of
degree and activities, the average clustering coefficient and the innovation
rate at the global and local level. The theory is born out in three diverse
real-world social networks: the network of mentions between Twitter users, the
network of co-authorship of the American Physical Society and a
mobile-phone-call network.

Physics and Society