| LDR | | 00000nam u2200205 4500 |
| 001 | | 000000435197 |
| 005 | | 20200227163026 |
| 008 | | 200131s2019 ||||||||||||||||| ||eng d |
| 020 | |
▼a 9781085657464 |
| 035 | |
▼a (MiAaPQ)AAI27534743 |
| 035 | |
▼a (MiAaPQ)OhioLINKosu1546425835709593 |
| 040 | |
▼a MiAaPQ
▼c MiAaPQ
▼d 247004 |
| 082 | 0 |
▼a 004 |
| 100 | 1 |
▼a Wang, Yu. |
| 245 | 10 |
▼a Revisiting Network Sampling. |
| 260 | |
▼a [S.l.]:
▼b The Ohio State University.,
▼c 2019. |
| 260 | 1 |
▼a Ann Arbor:
▼b ProQuest Dissertations & Theses,
▼c 2019. |
| 300 | |
▼a 119 p. |
| 500 | |
▼a Source: Dissertations Abstracts International, Volume: 81-02, Section: B. |
| 500 | |
▼a Advisor: Parthasarathy, Srinivasan. |
| 502 | 1 |
▼a Thesis (Ph.D.)--The Ohio State University, 2019. |
| 506 | |
▼a This item must not be sold to any third party vendors. |
| 520 | |
▼a 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. |
| 590 | |
▼a School code: 0168. |
| 650 | 4 |
▼a Statistics. |
| 650 | 4 |
▼a Computer science. |
| 690 | |
▼a 0984 |
| 690 | |
▼a 0463 |
| 710 | 20 |
▼a The Ohio State University.
▼b Computer Science and Engineering. |
| 773 | 0 |
▼t Dissertations Abstracts International
▼g 81-02B. |
| 773 | |
▼t Dissertation Abstract International |
| 790 | |
▼a 0168 |
| 791 | |
▼a Ph.D. |
| 792 | |
▼a 2019 |
| 793 | |
▼a English |
| 856 | 40 |
▼u http://www.riss.kr/pdu/ddodLink.do?id=T15494145
▼n KERIS
▼z 이 자료의 원문은 한국교육학술정보원에서 제공합니다. |
| 980 | |
▼a 202002
▼f 2020 |
| 990 | |
▼a ***1008102 |
| 991 | |
▼a E-BOOK |