A carregar...
Publicação
Sampling methods and estimation of triangle count distributions in large networks
| Nome: | Descrição: | Tamanho: | Formato: | |
|---|---|---|---|---|
| 712.46 KB | Adobe PDF |
Orientador(es)
Resumo(s)
This paper investigates the distributions of triangle counts per vertex and edge, as a means for network
description, analysis, model building, and other tasks. The main interest is in estimating these distributions
through sampling, especially for large networks. A novel sampling method tailored for the estimation analysis is proposed, with three sampling designs motivated by several network access scenarios. An estimation
method based on inversion and an asymptotic method are developed to recover the entire distribution.
A single method to estimate the distribution using multiple samples is also considered. Algorithms are
presented to sample the network under the various access scenarios. Finally, the estimation methods on
synthetic and real-world networks are evaluated in a data study.
Descrição
Palavras-chave
Triangles Random sampling Distribution estimation Inversion approach Asymptotic approach Multiple samples Static and streaming graphs Power laws
Contexto Educativo
Citação
Editora
Cambridge University Press