Power-Hop: A Pervasive Observation for Real Complex Networks

• Published in: PloS one 2016-03, Vol.11 (3), p.e0151027-e0151027
• Main Authors: Papalexakis, Evangelos, Hooi, Bryan, Pelechrinis, Konstantinos, Faloutsos, Christos
• Format: Article
• Language: English
• Subjects: Analysis; Biology and Life Sciences; Computer and Information Sciences; Computer science; Datasets; Fractals; Hops; Humans; Internet; Models, Theoretical; Networks; People and Places; Physical Sciences; Power law; Scaling; Social networks; Social organization; Social Sciences; Social Support
• ISSN: 1932-6203; 1932-6203
• DOI: 10.1371/journal.pone.0151027

Complex networks have been shown to exhibit universal properties, with one of the most consistent patterns being the scale-free degree distribution, but are there regularities obeyed by the r-hop neighborhood in real networks? We answer this question by identifying another power-law pattern that describes the relationship between the fractions of node pairs C(r) within r hops and the hop count r. This scale-free distribution is pervasive and describes a large variety of networks, ranging from social and urban to technological and biological networks. In particular, inspired by the definition of the fractal correlation dimension D2 on a point-set, we consider the hop-count r to be the underlying distance metric between two vertices of the network, and we examine the scaling of C(r) with r. We find that this relationship follows a power-law in real networks within the range 2 ≤ r ≤ d, where d is the effective diameter of the network, that is, the 90-th percentile distance. We term this relationship as power-hop and the corresponding power-law exponent as power-hop exponent h. We provide theoretical justification for this pattern under successful existing network models, while we analyze a large set of real and synthetic network datasets and we show the pervasiveness of the power-hop.