  Similarity index measures the topological proximity of node pairs in a
complex network. Numerous similarity indices have been defined and
investigated, but the dependency of structure on the performance of similarity
indices has not been sufficiently investigated. In this study, we investigated
the relationship between the performance of similarity indices and structural
properties of a network by employing a two-state random network. A node in a
two-state network has binary types that are initially given, and a connection
probability is determined from the state of the node pair. The performance of
similarity indices affects the number of links and the ratio of
intra-connections to inter-connections. Similarity indices have different
characteristics depending on their type. Local indices perform well in
small-size networks and do not depend on whether the structure is
intra-dominant or inter-dominant. In contrast, global indices perform better in
large-size networks, and some such indices do not perform well in an
inter-dominant structure. We also found that link prediction performance and
the performance of similarity are correlated in both model networks and
empirical networks. This relationship implies that link prediction performance
can be used as an approximation for the performance of the similarity index
when metadata for node types are unavailable. This relationship may help to
find the appropriate index for given networks.
