Conference proceeding
On the number of star samples to find a vertex or edge with given degree in a graph
2017 51ST ANNUAL CONFERENCE ON INFORMATION SCIENCES AND SYSTEMS (CISS)
01 Jan 2017
Featured in Collection : UN Sustainable Development Goals @ Drexel
Abstract
A (single) star sample of a large graph consists of a vertex, its neighbors, and the degrees of each neighbor. Estimators are derived for the expected number of star samples required to find any vertex with a given degree l, and to find any edge with given degrees {k, l}, when the star vertex is selected with replacement, independently and uniformly at random. A modified construction of the classic Erdos-Renyi (ER) graph is given, wherein a random number of edges are placed independently and uniformly at random on the set of vertices. Three results are given: i) although the modified ER graph is a multigraph, the fraction of multiple edges is exponentially small in the edge probability, ii) the random degrees under the classic ER and modified ER constructions have equal means and the variances have a ratio near one for small edge probability, and iii) the probability of a star sample containing a vertex with a target degree is approximately equal to a simple combinatorial quantity under the modified ER construction. This quantity is our primary approximation of the performance under star sampling, requiring knowledge only of certain natural summary statistics for the graph. Numerical results comparing the actual and approximate number of star samples required to find vertices and edges with target degrees are given for both synthetic ER graphs and for real-world graphs from the SNAP repository.
Metrics
8 Record Views
Details
- Title
- On the number of star samples to find a vertex or edge with given degree in a graph
- Creators
- Jonathan Stokes - Drexel Univ, Dept Elect & Comp Engn, Philadelphia, PA 19104 USASteven Weber - Drexel UniversityIEEE
- Publication Details
- 2017 51ST ANNUAL CONFERENCE ON INFORMATION SCIENCES AND SYSTEMS (CISS)
- Conference
- 2017 51ST ANNUAL CONFERENCE ON INFORMATION SCIENCES AND SYSTEMS (CISS), 51st
- Publisher
- IEEE
- Number of pages
- 6
- Grant note
- IIS-1250786 / National Science Foundation; National Science Foundation (NSF)
- Resource Type
- Conference proceeding
- Language
- English
- Academic Unit
- Electrical and Computer Engineering
- Identifiers
- 991019170447704721
UN Sustainable Development Goals (SDGs)
This output has contributed to the advancement of the following goals:
InCites Highlights
These are selected metrics from InCites Benchmarking & Analytics tool, related to this output
- Web of Science research areas
- Computer Science, Information Systems
- Engineering, Electrical & Electronic