The Structure of Bit-String Similarity Networks

Abstract

We study the structural properties of networks formed by random sets of bit strings—namely the ordered arrays of binary variables representing, for instance, genetic information or cultural profiles. Two bit strings are connected by a network link when they are sufficiently similar to each other, i.e., when their Hamming distance is below a certain threshold. Using both analytical and numerical techniques, we determine the degree distribution and the conditions for the existence of a giant component in this kind of network. In addition, we analyze their clustering, assortativity, and mean geodesic distance. We show that these properties combine features specific to random networks with characteristics that derive from the Hamming metrics implicit in the definition of similarity between bit strings.