Bootstrapped Inference for Degree Distributions in Large Sparse Networks

Add to your list(s) Download to your calendar using vCal

• Yulia Gel (University of Texas at Dallas; University of Waterloo)
• Wednesday 07 December 2016, 12:00-12:30
• Seminar Room 1, Newton Institute.

If you have a question about this talk, please contact INI IT.

DLAW03 - New developments in data privacy

We propose a new method of nonparametric bootstrap to quantify estimation uncertainties in functions of network degree distribution in large ultra sparse networks. Both network degree distribution and network order are assumed to be unknown. The key idea is based on adaptation of the ``blocking'' argument, developed for bootstrapping of time series and re-tiling of spatial data, to random networks. We first sample a set of multiple ego networks of varying orders that form a patch, or a network block analogue, and then resample the data within patches. To select an optimal patch size, we develop a new computationally efficient and data-driven cross-validation algorithm. In our simulation study, we show that the new fast patchwork bootstrap (FPB) outperforms competing approaches by providing sharper and better calibrated confidence intervals for functions of a network degree distribution, including the cases of networks in an ultra sparse regime. We illustrate the FPB in application to analysis of social networks and discuss its potential utility for nonparametric anomaly detection and privacy-preserving data mining.

This talk is part of the Isaac Newton Institute Seminar Series series.

This talk is included in these lists:

• All CMS events
• Cambridge Centre for Data-Driven Discovery (C2D3)
• Cambridge talks
• Chris Davis' list
• Featured lists
• INI info aggregator
• Interested Talks
• Isaac Newton Institute Seminar Series
• School of Physical Sciences
• Seminar Room 1, Newton Institute
• Trust & Technology Initiative - interesting events
• bld31
• ndk22's list
• ob366-ai4er
• rp587

Note that ex-directory lists are not shown.