On the Theoretical Properties of the Network Jackknife

The Internet is a giant, directed network of webpages pointing to other webpages. Facebook is an undirected network built via friendships between users. The ecological web is a directed network of different species with edges specified by'who-eats-whom' relationships. Protein-protein interactions are undirected networks consisting of pairs of baitprey proteins that bind to each other during coaffinity purification experiments arising in mass spectrometry analysis. In these application areas, it is often of interest to characterize a network using statistics such as the clustering coefficient, triangle density, or principal eigenvalues. There has been a substantial amount of work on approximating these quantities with small error on massive networks Assadi et al. (2018); Eden et al. (2017); Feige (2006); Goldreich and Ron (2008); Gonen et al. (2010); Kallaugher et al. (2019).