Tail-scope: Using friends to estimate heavy tails of degree distributions in large-scale complex networks

Abstract

Many complex networks in natural and social phenomena have often been characterized by heavy-tailed degree distributions. However, due to rapidly growing size of network data and concerns on privacy issues about using these data, it becomes more difficult to analyze complete data sets. Thus, it is crucial to devise effective and efficient estimation methods for heavy tails of degree distributions in large-scale networks only using local information of a small fraction of sampled nodes. Here we propose a tail-scope method based on local observational bias of the friendship paradox. We show that the tail-scope method outperforms the uniform node sampling for estimating heavy tails of degree distributions, while the opposite tendency is observed in the range of small degrees. In order to take advantages of both sampling methods, we devise the hybrid method that successfully recovers the whole range of degree distributions. Our tail-scope method shows how structural heterogeneities of large-scale complex networks can be used to effectively reveal the network structure only with limited local information.

arXiv comment9 pages, 6 figures

References in corpus (17)

• Emergence of scaling in random networks
• Community detection in graphs
• Power-law distributions in empirical data
• Error and attack tolerance of complex networks
• Epidemic spreading in scale-free networks
• Lethality and centrality in protein networks
• Assortative mixing in networks
• Statistical physics of social dynamics
• Efficient Immunization Strategies for Computer Networks and Populations
• Social Network Sensors for Early Detection of Contagious Outbreaks
• Characterizing and modeling citation dynamics
• Performance of Social Network Sensors During Hurricane Sandy
• Competing activation mechanisms in epidemics on networks
• Generalized friendship paradox in complex networks: The case of scientific collaboration
• Interactions of cultures and top people of Wikipedia from ranking of 24 language editions
• Generalized friendship paradox in networks with tunable degree-attribute correlation
• Quick Detection of High-degree Entities in Large Directed Networks

Cited by in corpus (9)

• Bursty Human Dynamics
• Heri-Graphs: A Workflow of Creating Datasets for Multi-modal Machine Learning on Graphs of Heritage Values and Attributes with Social Media
• What Do Your Friends Think? Efficient Polling Methods for Networks Using Friendship Paradox
• Deep Learning for Learning Graph Representations
• Stylized facts in social networks: Community-based static modeling
• On the uniqueness theorem for pseudo-additive entropies
• Sampling networks by nodal attributes
• Cooperative Multi-Agent Bandits with Heavy Tails
• Mean-Field Theory for Heider Balance under Heterogeneous Social Temperatures