상세정보
Export to Refworks부가기능
Revisiting Network Sampling
상세 프로파일
| 자료유형 | 학위논문 |
|---|---|
| 서명/저자사항 | Revisiting Network Sampling. |
| 개인저자 | Wang, Yu. |
| 단체저자명 | The Ohio State University. Computer Science and Engineering. |
| 발행사항 | [S.l.]: The Ohio State University., 2019. |
| 발행사항 | Ann Arbor: ProQuest Dissertations & Theses, 2019. |
| 형태사항 | 119 p. |
| 기본자료 저록 | Dissertations Abstracts International 81-02B. Dissertation Abstract International |
| ISBN | 9781085657464 |
| 학위논문주기 | Thesis (Ph.D.)--The Ohio State University, 2019. |
| 일반주기 |
Source: Dissertations Abstracts International, Volume: 81-02, Section: B.
Advisor: Parthasarathy, Srinivasan. |
| 이용제한사항 | This item must not be sold to any third party vendors. |
| 요약 | 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. |
| 일반주제명 | Statistics. Computer science. |
| 언어 | 영어 |
| 바로가기 | 
: 이 자료의 원문은 한국교육학술정보원에서 제공합니다. |
