In the traditional framework of network formation models, a set of agents is assumed to be xed. On the other hand, this paper in- vestigates how a network changes upon the arrival of a new agent. More precisely, for the given set of agents, suppose that a pairwise stable network is initially constructed. When a new agent enters the network, the initial network may not be pairwise stable. A new net- work will be constructed through an improving path from the initial network. Eventually, for the new set of agents, a pairwise stable net- work or networks in a closed cycle will be obtained. Comparing the new networks with the initial network, we propose four di®erent pop- ulation invariance properties of a network: link invariance, distance invariance, connectedness invariance, and network invariance. First, we show that pairwise stability is incompatible with link invariance under mild assumptions on allocation rules. However, if we consider specic models, positive results can be obtained. For instance, in the symmetric connections model, pairwise stability implies connectedness invariance.