title: Power-Hop: A Pervasive Observation for Real Complex Networks.
abstract: 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.
authors.affiliation: Department of Computer Science, Carnegie Mellon University, Pittsburgh, PA, United States of America.
authors.forename: Evangelos
authors.initials: E
authors.lastname: Papalexakis
authors.affiliation: Machine Learning Department, Carnegie Mellon University, Pittsburgh, PA, United States of America.
authors.forename: Bryan
authors.initials: B
authors.lastname: Hooi
authors.affiliation: School of Information Sciences, University of Pittsburgh, Pittsburgh, PA, United States of America.
authors.forename: Konstantinos
authors.initials: K
authors.lastname: Pelechrinis
authors.affiliation: Department of Computer Science, Carnegie Mellon University, Pittsburgh, PA, United States of America.
authors.forename: Christos
authors.initials: C
authors.lastname: Faloutsos
mesh_terms: D006801:Humans; D008962:Models, Theoretical; D012944:Social Support