Link to the University of Pittsburgh Homepage
Link to the University Library System Homepage Link to the Contact Us Form

Power-hop: A pervasive observation for real complex networks

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).

[img]
Preview
PDF
Published Version
Available under License : See the attached license file.

Download (1MB)
[img] Plain Text (licence)
Available under License : See the attached license file.

Download (1kB)

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:
Share |

Details

Item Type: Article
Status: Published
Creators/Authors:
CreatorsEmailPitt UsernameORCID
Papalexakis, E
Hooi, B
Pelechrinis, Kkpele@pitt.eduKPELE
Faloutsos, C
Date: 1 March 2016
Date Type: Publication
Access Restriction: No restriction; Release the ETD for access worldwide immediately.
Journal or Publication Title: PLoS ONE
Volume: 11
Number: 3
DOI or Unique Handle: 10.1371/journal.pone.0151027
Institution: University of Pittsburgh
Schools and Programs: School of Information Sciences > Telecommunications
Refereed: Yes
PubMed Central ID: PMC4790966
Date Deposited: 01 Jul 2016 14:02
Last Modified: 27 Apr 2019 14:55
URI: http://d-scholarship.pitt.edu/id/eprint/28330

Metrics

Monthly Views for the past 3 years

Plum Analytics

Altmetric.com


Actions (login required)

View Item View Item