Papalexakis, E and Hooi, B and Pelechrinis, K and Faloutsos, C
(2016)
Power-hop: A pervasive observation for real complex networks.
PLoS ONE, 11 (3).
Abstract
© 2016 Papalexakis et al. This is an open access article distributed under the terms of the Creative Commons Attribution License, which permits unrestricted use, distribution, and reproduction in any medium, provided the original author and source are credited. 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 D 2 on a point-set, we consider the hop-count rto 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.
Share
| Citation/Export: |
|
| Social Networking: |
|
Details
Metrics
Monthly Views for the past 3 years
Plum Analytics
Altmetric.com
Actions (login required)
 |
View Item |
![[img]](http://d-scholarship.pitt.edu/style/images/fileicons/application_pdf.png)
![[img]](http://d-scholarship.pitt.edu/style/images/fileicons/text_plain.png)
![[feed]](/images/feed-icon-32x32.png){kind=icon}