Shotgun Assembly of Erd\H{o}s-R\'enyi Random Graphs Article Swipe
Graph shotgun assembly refers to the problem of reconstructing a graph from a collection of local neighborhoods. In this paper, we consider shotgun assembly of Erd\H{o}s-R\'enyi random graphs $G(n, p_n)$, where $p_n = n^{-\alpha}$ for $0 < \alpha < 1$. We consider both reconstruction up to isomorphism as well as exact reconstruction (recovering the vertex labels as well as the structure). We show that given the collection of distance-$1$ neighborhoods, $G$ is exactly reconstructable for $0 < \alpha < \frac{1}{3}$, but not reconstructable for $\frac{1}{2} < \alpha < 1$. Given the collection of distance-$2$ neighborhoods, $G$ is exactly reconstructable for $0 < \alpha < \frac{1}{2}$, but not reconstructable for $\frac{3}{4} < \alpha < 1$.
Related Topics
Concepts
Metadata
- Type
- article
- Language
- en
- Landing Page
- https://arxiv.org/pdf/2010.14661
- OA Status
- green
- Related Works
- 20
- OpenAlex ID
- https://openalex.org/W3097398657
All OpenAlex metadata
Raw OpenAlex JSON
- OpenAlex ID
-
https://openalex.org/W3097398657Canonical identifier for this work in OpenAlex
- Title
-
Shotgun Assembly of Erd\H{o}s-R\'enyi Random GraphsWork title
- Type
-
articleOpenAlex work type
- Language
-
enPrimary language
- Publication year
-
2020Year of publication
- Publication date
-
2020-10-27Full publication date if available
- Authors
-
Julia Gaudio, Elchanan MosselList of authors in order
- Landing page
-
https://arxiv.org/pdf/2010.14661Publisher landing page
- Open access
-
YesWhether a free full text is available
- OA status
-
greenOpen access status per OpenAlex
- OA URL
-
https://arxiv.org/pdf/2010.14661Direct OA link when available
- Concepts
-
Combinatorics, Vertex (graph theory), Isomorphism (crystallography), Graph, Random graph, Mathematics, Shotgun, Alpha (finance), Discrete mathematics, Crystallography, Chemistry, Crystal structure, Construct validity, Biochemistry, Statistics, Gene, PsychometricsTop concepts (fields/topics) attached by OpenAlex
- Cited by
-
0Total citation count in OpenAlex
- Related works (count)
-
20Other works algorithmically related by OpenAlex
Full payload
| id | https://openalex.org/W3097398657 |
|---|---|
| doi | |
| ids.mag | 3097398657 |
| ids.openalex | https://openalex.org/W3097398657 |
| fwci | 0.0 |
| type | article |
| title | Shotgun Assembly of Erd\H{o}s-R\'enyi Random Graphs |
| biblio.issue | |
| biblio.volume | |
| biblio.last_page | |
| biblio.first_page | |
| topics[0].id | https://openalex.org/T12923 |
| topics[0].field.id | https://openalex.org/fields/17 |
| topics[0].field.display_name | Computer Science |
| topics[0].score | 0.9937999844551086 |
| topics[0].domain.id | https://openalex.org/domains/3 |
| topics[0].domain.display_name | Physical Sciences |
| topics[0].subfield.id | https://openalex.org/subfields/1707 |
| topics[0].subfield.display_name | Computer Vision and Pattern Recognition |
| topics[0].display_name | Digital Image Processing Techniques |
| topics[1].id | https://openalex.org/T12536 |
| topics[1].field.id | https://openalex.org/fields/17 |
| topics[1].field.display_name | Computer Science |
| topics[1].score | 0.9677000045776367 |
| topics[1].domain.id | https://openalex.org/domains/3 |
| topics[1].domain.display_name | Physical Sciences |
| topics[1].subfield.id | https://openalex.org/subfields/1703 |
| topics[1].subfield.display_name | Computational Theory and Mathematics |
| topics[1].display_name | Topological and Geometric Data Analysis |
| topics[2].id | https://openalex.org/T10996 |
| topics[2].field.id | https://openalex.org/fields/17 |
| topics[2].field.display_name | Computer Science |
| topics[2].score | 0.9593999981880188 |
| topics[2].domain.id | https://openalex.org/domains/3 |
| topics[2].domain.display_name | Physical Sciences |
| topics[2].subfield.id | https://openalex.org/subfields/1704 |
| topics[2].subfield.display_name | Computer Graphics and Computer-Aided Design |
| topics[2].display_name | Computational Geometry and Mesh Generation |
| is_xpac | False |
| apc_list | |
| apc_paid | |
| concepts[0].id | https://openalex.org/C114614502 |
| concepts[0].level | 1 |
| concepts[0].score | 0.7767789363861084 |
| concepts[0].wikidata | https://www.wikidata.org/wiki/Q76592 |
| concepts[0].display_name | Combinatorics |
| concepts[1].id | https://openalex.org/C80899671 |
| concepts[1].level | 3 |
| concepts[1].score | 0.6691887378692627 |
| concepts[1].wikidata | https://www.wikidata.org/wiki/Q1304193 |
| concepts[1].display_name | Vertex (graph theory) |
| concepts[2].id | https://openalex.org/C203436722 |
| concepts[2].level | 3 |
| concepts[2].score | 0.5940203070640564 |
| concepts[2].wikidata | https://www.wikidata.org/wiki/Q902950 |
| concepts[2].display_name | Isomorphism (crystallography) |
| concepts[3].id | https://openalex.org/C132525143 |
| concepts[3].level | 2 |
| concepts[3].score | 0.49172475934028625 |
| concepts[3].wikidata | https://www.wikidata.org/wiki/Q141488 |
| concepts[3].display_name | Graph |
| concepts[4].id | https://openalex.org/C47458327 |
| concepts[4].level | 3 |
| concepts[4].score | 0.4841361939907074 |
| concepts[4].wikidata | https://www.wikidata.org/wiki/Q910404 |
| concepts[4].display_name | Random graph |
| concepts[5].id | https://openalex.org/C33923547 |
| concepts[5].level | 0 |
| concepts[5].score | 0.4611523449420929 |
| concepts[5].wikidata | https://www.wikidata.org/wiki/Q395 |
| concepts[5].display_name | Mathematics |
| concepts[6].id | https://openalex.org/C2781434637 |
| concepts[6].level | 3 |
| concepts[6].score | 0.44440746307373047 |
| concepts[6].wikidata | https://www.wikidata.org/wiki/Q486396 |
| concepts[6].display_name | Shotgun |
| concepts[7].id | https://openalex.org/C64943373 |
| concepts[7].level | 4 |
| concepts[7].score | 0.43992123007774353 |
| concepts[7].wikidata | https://www.wikidata.org/wiki/Q2651003 |
| concepts[7].display_name | Alpha (finance) |
| concepts[8].id | https://openalex.org/C118615104 |
| concepts[8].level | 1 |
| concepts[8].score | 0.3921279311180115 |
| concepts[8].wikidata | https://www.wikidata.org/wiki/Q121416 |
| concepts[8].display_name | Discrete mathematics |
| concepts[9].id | https://openalex.org/C8010536 |
| concepts[9].level | 1 |
| concepts[9].score | 0.2011350691318512 |
| concepts[9].wikidata | https://www.wikidata.org/wiki/Q160398 |
| concepts[9].display_name | Crystallography |
| concepts[10].id | https://openalex.org/C185592680 |
| concepts[10].level | 0 |
| concepts[10].score | 0.08749938011169434 |
| concepts[10].wikidata | https://www.wikidata.org/wiki/Q2329 |
| concepts[10].display_name | Chemistry |
| concepts[11].id | https://openalex.org/C115624301 |
| concepts[11].level | 2 |
| concepts[11].score | 0.052305787801742554 |
| concepts[11].wikidata | https://www.wikidata.org/wiki/Q895901 |
| concepts[11].display_name | Crystal structure |
| concepts[12].id | https://openalex.org/C49453240 |
| concepts[12].level | 3 |
| concepts[12].score | 0.0 |
| concepts[12].wikidata | https://www.wikidata.org/wiki/Q1592163 |
| concepts[12].display_name | Construct validity |
| concepts[13].id | https://openalex.org/C55493867 |
| concepts[13].level | 1 |
| concepts[13].score | 0.0 |
| concepts[13].wikidata | https://www.wikidata.org/wiki/Q7094 |
| concepts[13].display_name | Biochemistry |
| concepts[14].id | https://openalex.org/C105795698 |
| concepts[14].level | 1 |
| concepts[14].score | 0.0 |
| concepts[14].wikidata | https://www.wikidata.org/wiki/Q12483 |
| concepts[14].display_name | Statistics |
| concepts[15].id | https://openalex.org/C104317684 |
| concepts[15].level | 2 |
| concepts[15].score | 0.0 |
| concepts[15].wikidata | https://www.wikidata.org/wiki/Q7187 |
| concepts[15].display_name | Gene |
| concepts[16].id | https://openalex.org/C171606756 |
| concepts[16].level | 2 |
| concepts[16].score | 0.0 |
| concepts[16].wikidata | https://www.wikidata.org/wiki/Q506132 |
| concepts[16].display_name | Psychometrics |
| keywords[0].id | https://openalex.org/keywords/combinatorics |
| keywords[0].score | 0.7767789363861084 |
| keywords[0].display_name | Combinatorics |
| keywords[1].id | https://openalex.org/keywords/vertex |
| keywords[1].score | 0.6691887378692627 |
| keywords[1].display_name | Vertex (graph theory) |
| keywords[2].id | https://openalex.org/keywords/isomorphism |
| keywords[2].score | 0.5940203070640564 |
| keywords[2].display_name | Isomorphism (crystallography) |
| keywords[3].id | https://openalex.org/keywords/graph |
| keywords[3].score | 0.49172475934028625 |
| keywords[3].display_name | Graph |
| keywords[4].id | https://openalex.org/keywords/random-graph |
| keywords[4].score | 0.4841361939907074 |
| keywords[4].display_name | Random graph |
| keywords[5].id | https://openalex.org/keywords/mathematics |
| keywords[5].score | 0.4611523449420929 |
| keywords[5].display_name | Mathematics |
| keywords[6].id | https://openalex.org/keywords/shotgun |
| keywords[6].score | 0.44440746307373047 |
| keywords[6].display_name | Shotgun |
| keywords[7].id | https://openalex.org/keywords/alpha |
| keywords[7].score | 0.43992123007774353 |
| keywords[7].display_name | Alpha (finance) |
| keywords[8].id | https://openalex.org/keywords/discrete-mathematics |
| keywords[8].score | 0.3921279311180115 |
| keywords[8].display_name | Discrete mathematics |
| keywords[9].id | https://openalex.org/keywords/crystallography |
| keywords[9].score | 0.2011350691318512 |
| keywords[9].display_name | Crystallography |
| keywords[10].id | https://openalex.org/keywords/chemistry |
| keywords[10].score | 0.08749938011169434 |
| keywords[10].display_name | Chemistry |
| keywords[11].id | https://openalex.org/keywords/crystal-structure |
| keywords[11].score | 0.052305787801742554 |
| keywords[11].display_name | Crystal structure |
| language | en |
| locations[0].id | mag:3097398657 |
| locations[0].is_oa | True |
| locations[0].source.id | https://openalex.org/S4306400194 |
| locations[0].source.issn | |
| locations[0].source.type | repository |
| locations[0].source.is_oa | True |
| locations[0].source.issn_l | |
| locations[0].source.is_core | False |
| locations[0].source.is_in_doaj | False |
| locations[0].source.display_name | arXiv (Cornell University) |
| locations[0].source.host_organization | https://openalex.org/I205783295 |
| locations[0].source.host_organization_name | Cornell University |
| locations[0].source.host_organization_lineage | https://openalex.org/I205783295 |
| locations[0].license | |
| locations[0].pdf_url | |
| locations[0].version | submittedVersion |
| locations[0].raw_type | |
| locations[0].license_id | |
| locations[0].is_accepted | False |
| locations[0].is_published | False |
| locations[0].raw_source_name | arXiv (Cornell University) |
| locations[0].landing_page_url | https://arxiv.org/pdf/2010.14661 |
| authorships[0].author.id | https://openalex.org/A5073149598 |
| authorships[0].author.orcid | https://orcid.org/0000-0002-3078-1536 |
| authorships[0].author.display_name | Julia Gaudio |
| authorships[0].author_position | first |
| authorships[0].raw_author_name | Julia Gaudio |
| authorships[0].is_corresponding | False |
| authorships[1].author.id | https://openalex.org/A5013467728 |
| authorships[1].author.orcid | https://orcid.org/0000-0001-7812-7886 |
| authorships[1].author.display_name | Elchanan Mossel |
| authorships[1].author_position | last |
| authorships[1].raw_author_name | Elchanan Mossel |
| authorships[1].is_corresponding | False |
| has_content.pdf | False |
| has_content.grobid_xml | False |
| is_paratext | False |
| open_access.is_oa | True |
| open_access.oa_url | https://arxiv.org/pdf/2010.14661 |
| open_access.oa_status | green |
| open_access.any_repository_has_fulltext | False |
| created_date | 2025-10-10T00:00:00 |
| display_name | Shotgun Assembly of Erd\H{o}s-R\'enyi Random Graphs |
| has_fulltext | False |
| is_retracted | False |
| updated_date | 2025-10-10T17:16:08.811792 |
| primary_topic.id | https://openalex.org/T12923 |
| primary_topic.field.id | https://openalex.org/fields/17 |
| primary_topic.field.display_name | Computer Science |
| primary_topic.score | 0.9937999844551086 |
| primary_topic.domain.id | https://openalex.org/domains/3 |
| primary_topic.domain.display_name | Physical Sciences |
| primary_topic.subfield.id | https://openalex.org/subfields/1707 |
| primary_topic.subfield.display_name | Computer Vision and Pattern Recognition |
| primary_topic.display_name | Digital Image Processing Techniques |
| related_works | https://openalex.org/W3018556147, https://openalex.org/W2950585381, https://openalex.org/W2515981595, https://openalex.org/W3126108959, https://openalex.org/W2000630511, https://openalex.org/W1681620790, https://openalex.org/W341093106, https://openalex.org/W2164538103, https://openalex.org/W3023439304, https://openalex.org/W2047904296, https://openalex.org/W1967358236, https://openalex.org/W2118626701, https://openalex.org/W1983468063, https://openalex.org/W2951053782, https://openalex.org/W2997917651, https://openalex.org/W2418250709, https://openalex.org/W2953236912, https://openalex.org/W3204243990, https://openalex.org/W2296450182, https://openalex.org/W2061292276 |
| cited_by_count | 0 |
| locations_count | 1 |
| best_oa_location.id | mag:3097398657 |
| best_oa_location.is_oa | True |
| best_oa_location.source.id | https://openalex.org/S4306400194 |
| best_oa_location.source.issn | |
| best_oa_location.source.type | repository |
| best_oa_location.source.is_oa | True |
| best_oa_location.source.issn_l | |
| best_oa_location.source.is_core | False |
| best_oa_location.source.is_in_doaj | False |
| best_oa_location.source.display_name | arXiv (Cornell University) |
| best_oa_location.source.host_organization | https://openalex.org/I205783295 |
| best_oa_location.source.host_organization_name | Cornell University |
| best_oa_location.source.host_organization_lineage | https://openalex.org/I205783295 |
| best_oa_location.license | |
| best_oa_location.pdf_url | |
| best_oa_location.version | submittedVersion |
| best_oa_location.raw_type | |
| best_oa_location.license_id | |
| best_oa_location.is_accepted | False |
| best_oa_location.is_published | False |
| best_oa_location.raw_source_name | arXiv (Cornell University) |
| best_oa_location.landing_page_url | https://arxiv.org/pdf/2010.14661 |
| primary_location.id | mag:3097398657 |
| primary_location.is_oa | True |
| primary_location.source.id | https://openalex.org/S4306400194 |
| primary_location.source.issn | |
| primary_location.source.type | repository |
| primary_location.source.is_oa | True |
| primary_location.source.issn_l | |
| primary_location.source.is_core | False |
| primary_location.source.is_in_doaj | False |
| primary_location.source.display_name | arXiv (Cornell University) |
| primary_location.source.host_organization | https://openalex.org/I205783295 |
| primary_location.source.host_organization_name | Cornell University |
| primary_location.source.host_organization_lineage | https://openalex.org/I205783295 |
| primary_location.license | |
| primary_location.pdf_url | |
| primary_location.version | submittedVersion |
| primary_location.raw_type | |
| primary_location.license_id | |
| primary_location.is_accepted | False |
| primary_location.is_published | False |
| primary_location.raw_source_name | arXiv (Cornell University) |
| primary_location.landing_page_url | https://arxiv.org/pdf/2010.14661 |
| publication_date | 2020-10-27 |
| publication_year | 2020 |
| referenced_works_count | 0 |
| abstract_inverted_index.< | 36, 38, 76, 78, 85, 87, 101, 103, 110, 112 |
| abstract_inverted_index.= | 32 |
| abstract_inverted_index.a | 9, 12 |
| abstract_inverted_index.$0 | 35, 75, 100 |
| abstract_inverted_index.In | 17 |
| abstract_inverted_index.We | 40, 61 |
| abstract_inverted_index.as | 47, 49, 56, 58 |
| abstract_inverted_index.is | 71, 96 |
| abstract_inverted_index.of | 7, 14, 24, 67, 92 |
| abstract_inverted_index.to | 4, 45 |
| abstract_inverted_index.up | 44 |
| abstract_inverted_index.we | 20 |
| abstract_inverted_index.$G$ | 70, 95 |
| abstract_inverted_index.1$. | 39, 88, 113 |
| abstract_inverted_index.but | 80, 105 |
| abstract_inverted_index.for | 34, 74, 83, 99, 108 |
| abstract_inverted_index.not | 81, 106 |
| abstract_inverted_index.the | 5, 53, 59, 65, 90 |
| abstract_inverted_index.$p_n | 31 |
| abstract_inverted_index.both | 42 |
| abstract_inverted_index.from | 11 |
| abstract_inverted_index.show | 62 |
| abstract_inverted_index.that | 63 |
| abstract_inverted_index.this | 18 |
| abstract_inverted_index.well | 48, 57 |
| abstract_inverted_index.$G(n, | 28 |
| abstract_inverted_index.Given | 89 |
| abstract_inverted_index.Graph | 0 |
| abstract_inverted_index.exact | 50 |
| abstract_inverted_index.given | 64 |
| abstract_inverted_index.graph | 10 |
| abstract_inverted_index.local | 15 |
| abstract_inverted_index.where | 30 |
| abstract_inverted_index.\alpha | 37, 77, 86, 102, 111 |
| abstract_inverted_index.graphs | 27 |
| abstract_inverted_index.labels | 55 |
| abstract_inverted_index.p_n)$, | 29 |
| abstract_inverted_index.paper, | 19 |
| abstract_inverted_index.random | 26 |
| abstract_inverted_index.refers | 3 |
| abstract_inverted_index.vertex | 54 |
| abstract_inverted_index.exactly | 72, 97 |
| abstract_inverted_index.problem | 6 |
| abstract_inverted_index.shotgun | 1, 22 |
| abstract_inverted_index.assembly | 2, 23 |
| abstract_inverted_index.consider | 21, 41 |
| abstract_inverted_index.collection | 13, 66, 91 |
| abstract_inverted_index.(recovering | 52 |
| abstract_inverted_index.isomorphism | 46 |
| abstract_inverted_index.structure). | 60 |
| abstract_inverted_index.$\frac{1}{2} | 84 |
| abstract_inverted_index.$\frac{3}{4} | 109 |
| abstract_inverted_index.distance-$1$ | 68 |
| abstract_inverted_index.distance-$2$ | 93 |
| abstract_inverted_index.n^{-\alpha}$ | 33 |
| abstract_inverted_index.\frac{1}{2}$, | 104 |
| abstract_inverted_index.\frac{1}{3}$, | 79 |
| abstract_inverted_index.neighborhoods, | 69, 94 |
| abstract_inverted_index.neighborhoods. | 16 |
| abstract_inverted_index.reconstructing | 8 |
| abstract_inverted_index.reconstruction | 43, 51 |
| abstract_inverted_index.reconstructable | 73, 82, 98, 107 |
| abstract_inverted_index.Erd\H{o}s-R\'enyi | 25 |
| cited_by_percentile_year | |
| countries_distinct_count | 0 |
| institutions_distinct_count | 2 |
| sustainable_development_goals[0].id | https://metadata.un.org/sdg/11 |
| sustainable_development_goals[0].score | 0.7900000214576721 |
| sustainable_development_goals[0].display_name | Sustainable cities and communities |
| citation_normalized_percentile.value | 0.1203389 |
| citation_normalized_percentile.is_in_top_1_percent | False |
| citation_normalized_percentile.is_in_top_10_percent | False |