Skip to Main Content
 

Global Search Box

 
 
 
 

Files

File List


dissertation.pdf (7.88 MB)

ETD Abstract Container

Abstract Header

Revisiting Network Sampling

Wang, Yu
http://orcid.org/0000-0002-8322-4899
http://rave.ohiolink.edu/etdc/view?acc_num=osu1546425835709593

Abstract Details

2019, Doctor of Philosophy, Ohio State University, Computer Science and Engineering.
Networks are an expressive tool to represent relational data in various domains: an email network in a corporate, a co-sponsorship network in Congress, a co-authorship network in academia, et cetera. Given the ubiquitousness of the Internet, we are able to collect relational data at an immense scale (Facebook, Twitter, et cetera.). With limited computation power or time constraint, sampling is usually an essential first step to analyzing large-scale networks. Sampling within the network context has been studied in the research community for many years, and has two prevalent branches: node sampling and edge sampling. This thesis discusses the design, inference, and applications of both node sampling and edge sampling. We show that well-designed sampling methods together with good estimators can not only speed up the inference but also improve the quality. Node sampling seeks to sample nodes from a network, and one of its applications is to infer the distribution of network statistics (node degree, node label, et cetera.). It is well known that (social) networks have community structure, and nodes within each community are similar to each other. Hence, to sample from each community can reduce the ``homophily'' of the sample, and achieve a better summary of the networks. Existing link-trace based and random walk based sampling approaches tend to sample from within a community, and hence the sample suffers from the homophily bias. Although random walk with teleportation and multiple random walkers can alleviate the problem, they are still inferior to uniform sampling regarding community diversity. Sampling from each community can indeed achieve high community coverage rate, but in most cases, we do not have ground truth communities, and community detection itself is very time-consuming. We propose the spread sampling algorithm, which can achieve higher community diversity than baselines with fixed sampling budget. Also, the running time is less than several widely used community detection algorithms. We analyze several statistical properties of the algorithm and present its application on community detection seeding, maximum independent set discovery and network A/B testing. Edge sampling seeks to sample pairs of nodes (dyads) from a network, and one of its applications is to infer the network topological structure. We discuss the application of edge sampling in the "Change Point Detection" problem, which is to detect change points from a sequence of network snapshots. Existing algorithms on change point detection use information of the whole network, and hence do not scale to large networks. We show that by sampling and tracking a group of dyads across snapshots, one can also capture the network evolutionary patterns, and can use the sampled dyads to detect change points. We find that uniform sampling can detect global change (network global level evolutionary pattern), while biased sampling can detect local change (evolutionary patterns associated with a particular node or a particular community). We propose an unbiased and consistent estimator for edge probability with theoretical guarantees, and empirically show that a fix-sized sample can capture the structure of a moderately large network reasonably well. This sampling based change point detection algorithm is compared against two state-of-the-art on several synthetic and real-world networks, and exhibits its superiority of both efficiency and high quality.
Srinivasan Parthasarathy (Advisor)
David Sivakoff (Committee Member)
Huan Sun (Committee Member)
Nicholas Funderburg (Committee Member)
118 p.
Computer Science; Statistics
Social Networks, Sampling, Dynamic Networks, Community Detection

Recommended Citations

Citations

  • Wang, Y. (2019). Revisiting Network Sampling [Doctoral dissertation, Ohio State University]. OhioLINK Electronic Theses and Dissertations Center. http://rave.ohiolink.edu/etdc/view?acc_num=osu1546425835709593

    APA Style (7th edition)

  • Wang, Yu. Revisiting Network Sampling. 2019. Ohio State University, Doctoral dissertation. OhioLINK Electronic Theses and Dissertations Center, http://rave.ohiolink.edu/etdc/view?acc_num=osu1546425835709593.

    MLA Style (8th edition)

  • Wang, Yu. "Revisiting Network Sampling." Doctoral dissertation, Ohio State University, 2019. http://rave.ohiolink.edu/etdc/view?acc_num=osu1546425835709593

    Chicago Manual of Style (17th edition)

osu1546425835709593
413
© 2019, some rights reserved.Creative Commons License Revisiting Network Sampling by Yu Wang is licensed under a Creative Commons Attribution-NonCommercial-NoDerivs 3.0 Unported License. Based on a work at etd.ohiolink.edu.
This open access ETD is published by The Ohio State University and OhioLINK.