  Many link formation mechanisms for the evolution of social networks have been
successful to reproduce various empirical findings in social networks. However,
they have largely ignored the fact that individuals make decisions on whether
to create links to other individuals based on cost and benefit of linking, and
the fact that individuals may use perception of the network in their decision
making. In this paper, we study the evolution of social networks in terms of
perception-based strategic link formation. Here each individual has her own
perception of the actual network, and uses it to decide whether to create a
link to another individual. An individual with the least perception accuracy
can benefit from updating her perception using that of the most accurate
individual via a new link. This benefit is compared to the cost of linking in
decision making. Once a new link is created, it affects the accuracies of other
individuals' perceptions, leading to a further evolution of the actual network.
As for initial actual networks, we consider homogeneous and heterogeneous
cases. The homogeneous initial actual network is modeled by Erd\H{o}s-R\'enyi
(ER) random networks, while we take a star network for the heterogeneous case.
In any cases, individual perceptions of the actual network are modeled by ER
random networks with controllable linking probability. Then the stable link
density of the actual network is found to show discontinuous transitions or
jumps according to the cost of linking. As the number of jumps is the
consequence of the dynamical complexity, we discuss the effect of initial
conditions on the number of jumps to find that the dynamical complexity
strongly depends on how much individuals initially overestimate or
underestimate the link density of the actual network. For the heterogeneous
case, the role of the highly connected individual as an information spreader is
discussed.
