乐胖代购免代理版

{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2024,6,11]],"date-time":"2024-06-11T21:10:56Z","timestamp":1718140256244},"reference-count":25,"publisher":"Wiley","issue":"1","license":[{"start":{"date-parts":[[2015,10,16]],"date-time":"2015-10-16T00:00:00Z","timestamp":1444953600000},"content-version":"vor","delay-in-days":0,"URL":"http:\/\/onlinelibrary.wiley.com\/termsAndConditions#vor"}],"funder":[{"name":"CONICYT via Basal in Applied Mathematics"},{"name":"N\u00facleo Milenio Informaci\u00f3n y Coordinaci\u00f3n en Redes ICM\/FIC","award":["RC130003"]},{"name":"Fondecyt","award":["1130061","1120309"]},{"name":"N\u00facleo Milenio Modelos Estoc\u00e1sticos de Sistemas Complejos y Desordenados","award":["NC130062"]}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":["Networks"],"published-print":{"date-parts":[[2016,1]]},"abstract":"In the broadcast version of the congested clique model,nodes communicate in synchronous rounds by writing\u2010bit messages on a whiteboard, which is visible to all of them. The joint input to the nodes is an undirected\u2010node graph, with nodereceiving the list of its neighbors in. Our goal is to design a protocol at the end of which the information contained in the whiteboard is enough for reconstructing. It has already been shown that there is a one\u2010round protocol for reconstructing graphs with bounded degeneracy. The main drawback of that protocol is that the degeneracyof the input graphmust be knowna priori<\/jats:italic>by the nodes. Moreover, the protocol fails when applied to graphs with degeneracy larger than. In this article, we address this issue by looking forrobust<\/jats:italic>reconstruction protocols, that is, protocols which always give the correct answer and work efficiently when the input is restricted to a certain class. We introduce a very simple, two\u2010round protocol that we call Robust\u2010<\/jats:sc>Reconstruction<\/jats:sc>. We prove that this protocol is robust for reconstructing the class of Barab\u00e1si\u2010Albert trees with (expected) message size. Moreover, we present computational evidence suggesting that Robust\u2010Reconstruction<\/jats:sc>also generates logarithmic size messages for arbitrary Barab\u00e1si\u2010Albert networks. Finally, we stress the importance of the preferential attachment mechanism (used in the construction of Barab\u00e1si\u2010Albert networks) by proving that Robust\u2010Reconstruction<\/jats:sc>does not<\/jats:italic>generate short messages for random recursive trees. \u00a9 2015 Wiley Periodicals, Inc. NETWORKS, Vol. 67(1), 82\u201391 2016<\/jats:p>","DOI":"10.1002\/net.21662","type":"journal-article","created":{"date-parts":[[2015,10,16]],"date-time":"2015-10-16T05:20:45Z","timestamp":1444972845000},"page":"82-91","source":"Crossref","is-referenced-by-count":1,"title":["Robust reconstruction of Barab\u00e1si\u2010Albert networks in the broadcast congested clique model"],"prefix":"10.1002","volume":"67","author":[{"given":"Pablo","family":"Moisset de Espan\u00e9s","sequence":"first","affiliation":[{"name":"Centro de Modelamiento Matem\u00e1tico (UMI 2807 CNRS), Universidad de Chile"}]},{"given":"Ivan","family":"Rapaport","sequence":"additional","affiliation":[{"name":"Centro de Modelamiento Matem\u00e1tico (UMI 2807 CNRS), Universidad de Chile"}]},{"given":"Daniel","family":"Remenik","sequence":"additional","affiliation":[{"name":"Centro de Modelamiento Matem\u00e1tico (UMI 2807 CNRS), Universidad de Chile"}]},{"given":"Ivan","family":"Rapaport","sequence":"additional","affiliation":[{"name":"Departamento de Ingenier\u00eda Matem\u00e1tica Universidad de Chile"}]},{"given":"Daniel","family":"Remenik","sequence":"additional","affiliation":[{"name":"Departamento de Ingenier\u00eda Matem\u00e1tica Universidad de Chile"}]},{"given":"Javiera","family":"Urrutia","sequence":"additional","affiliation":[{"name":"Departamento de Ingenier\u00eda Matem\u00e1tica Universidad de Chile"}]}],"member":"311","published-online":{"date-parts":[[2015,10,16]]},"reference":[{"key":"e_1_2_7_2_1","doi-asserted-by":"crossref","unstructured":"K.J.Ahn S.Guha andA.McGregor Analyzing graph structure via linear measurements Proc 23rd Ann ACM\u2010SIAM Symp Discrete Algorithms Kyoto Japan 2012 pp.459\u2013467.","DOI":"10.1137\/1.9781611973099.40"},{"key":"e_1_2_7_3_1","doi-asserted-by":"crossref","unstructured":"K.J.Ahn S.Guha andA.McGregor Graph sketches: Sparsification spanners and subgraphs Proc 31st ACM SIGMOD\u2010SIGACT\u2010SIGART Symp Principles of Database Systems Scottsdale AZ 2012 pp.5\u201314.","DOI":"10.1145\/2213556.2213560"},{"key":"e_1_2_7_4_1","doi-asserted-by":"publisher","DOI":"10.1126\/science.286.5439.509"},{"key":"e_1_2_7_5_1","doi-asserted-by":"crossref","unstructured":"F.Becker A.Fernandez Anta I.Rapaport andE.Re\u00e9mila Brief announcement: A hierarchy of congested clique models from broadcast to unicast Proc 2015 ACM Symp Principles Distributed Computing New York NY 2015 pp.167\u2013169.","DOI":"10.1145\/2767386.2767447"},{"key":"e_1_2_7_6_1","doi-asserted-by":"crossref","unstructured":"F.Becker A.Kosowski N.Nisse I.Rapaport andK.Suchan Allowing each node to communicate only once in a distributed system: Shared whiteboard models Proc 24th ACM Symp Parallelism in Algorithms and Architectures Pittsburgh PA 2012 pp.11\u201317.","DOI":"10.1145\/2312005.2312008"},{"key":"e_1_2_7_7_1","doi-asserted-by":"crossref","unstructured":"F.Becker M.Matamala N.Nisse I.Rapaport K.Suchan andI.Todinca Adding a referee to an interconnection network: What can(not) be computed in one round Proc 25th IEEE Int Symp Parallel and Distributed Processing Anchorage Alaska 2011 pp.508\u2013514.","DOI":"10.1109\/IPDPS.2011.55"},{"key":"e_1_2_7_8_1","doi-asserted-by":"crossref","unstructured":"F.Becker P.Montealegre I.Rapaport andI.Todinca The simultaneous number\u2010in\u2010hand communication model for networks: Private coins public coins and determinism Proc 21st Int Colloq Structural Information and Communication Complexity Takayama Japan 2014 pp.83\u201395.","DOI":"10.1007\/978-3-319-09620-9_8"},{"key":"e_1_2_7_9_1","volume-title":"Handbook of graphs and networks: From the genome to the internet","author":"Bornholdt S.","year":"2003"},{"key":"e_1_2_7_10_1","doi-asserted-by":"crossref","unstructured":"K.Censor\u2010Hillel P.Kaski J.H.Korhonen C.Lenzen A.Paz andJ.Suomela Algebraic methods in the congested clique Proc 2015 ACM Symp Principles of Distributed Computing Donostia\u2010San Sebasti\u00e1n Spain 2015 pp.143\u2013152.","DOI":"10.1145\/2767386.2767414"},{"key":"e_1_2_7_11_1","doi-asserted-by":"crossref","unstructured":"D.Dolev C.Lenzen andS.Peled \u201cTri tri again\u201d: Finding triangles and small subgraphs in a distributed setting\u2013(ext. abstract) Proc 26th Int Symp Distributed Computing Salvador Brazil 2012 pp.195\u2013209.","DOI":"10.1007\/978-3-642-33651-5_14"},{"key":"e_1_2_7_12_1","doi-asserted-by":"crossref","unstructured":"A.Drucker F.Kuhn andR.Oshman On the power of the congested clique model ACM Symp Principles of Distributed Computing Paris France 2014 pp.367\u2013376.","DOI":"10.1145\/2611462.2611493"},{"key":"e_1_2_7_13_1","doi-asserted-by":"publisher","DOI":"10.1002\/zamm.19230030407"},{"key":"e_1_2_7_14_1","doi-asserted-by":"crossref","unstructured":"S.Guha A.McGregor andD.Tench Vertex and hyperedge connectivity in dynamic graph streams Proc 34th ACM Symp Principles of Database Systems Melbourne Victoria Australia 2015 pp.241\u2013247.","DOI":"10.1145\/2745754.2745763"},{"key":"e_1_2_7_15_1","doi-asserted-by":"crossref","unstructured":"J.W.Hegeman G.Pandurangan S.V.Pemmaraju V.B.Sardeshmukh andM.Scquizzato Toward optimal bounds in the congested clique: Graph connectivity and MST Proc 2015 ACM Symp Principles of Distributed Computing New York NY 2015 pp.91\u2013100.","DOI":"10.1145\/2767386.2767434"},{"key":"e_1_2_7_16_1","doi-asserted-by":"crossref","unstructured":"J.W.HegemanandS.V.Pemmaraju Lessons from the congested clique applied to MapReduce Proc 21st Int Colloq Structural Information and Communication Complexity Takayama Japan 2014 pp.149\u2013164.","DOI":"10.1007\/978-3-319-09620-9_13"},{"key":"e_1_2_7_17_1","doi-asserted-by":"crossref","unstructured":"J.W.Hegeman S.V.Pemmaraju andV.Sardeshmukh Near\u2010constant\u2010time distributed algorithms on a congested clique Proc 28th Int Symp Distributed Computing Austin TX 2014 pp.514\u2013530.","DOI":"10.1007\/978-3-662-45174-8_35"},{"key":"e_1_2_7_18_1","unstructured":"S.HolzerandN.Pinsker Approximation of distances and shortest paths in the broadcast congest clique arXiv preprint arXiv:1412.3445 (2014)."},{"key":"e_1_2_7_19_1","doi-asserted-by":"crossref","unstructured":"J.Kari M.Matamala I.Rapaport andV.Salo Solving the induced subgraph problem in the randomized multiparty simultaneous messages model Proc 22nd Int Colloq Structural Information and Communication Complexity Montserrat Spain 2015 pp.370\u2013384.","DOI":"10.1007\/978-3-319-25258-2_26"},{"key":"e_1_2_7_20_1","doi-asserted-by":"crossref","unstructured":"C.Lenzen Optimal deterministic routing and sorting on the congested clique Proc 2013 ACM Symp Principles of Distributed Computing Montreal QC Canada 2013 pp.42\u201350.","DOI":"10.1145\/2484239.2501983"},{"key":"e_1_2_7_21_1","doi-asserted-by":"crossref","unstructured":"Z.Lotker E.Pavlov B.Patt\u2010Shamir andD.Peleg MST construction in O(log log n) communication rounds Proc 15th ACM Symp Parallelism in Algorithms and Architectures San Diego CA 2003 pp.94\u2013100.","DOI":"10.1145\/777426.777428"},{"key":"e_1_2_7_22_1","volume-title":"Polya urn models, Chapman & Hall\/CRC Texts in Statistical Science","author":"Mahmoud H.","year":"2008"},{"key":"e_1_2_7_23_1","doi-asserted-by":"publisher","DOI":"10.1016\/0025-5564(70)90071-4"},{"key":"e_1_2_7_24_1","doi-asserted-by":"crossref","unstructured":"B.Patt\u2010ShamirandM.Teplitsky The round complexity of distributed sorting: Extended abstract Proc 30th Ann ACM Symp Principles of Distributed Computing San Jose CA 2011 pp.249\u2013256.","DOI":"10.1145\/1993806.1993851"},{"key":"e_1_2_7_25_1","doi-asserted-by":"publisher","DOI":"10.1137\/1.9780898719772"},{"key":"e_1_2_7_26_1","unstructured":"V.RaghavanandJ.P.Spinrad Robust algorithms for restricted domains Proc 12th Ann Symp Discrete Algorithms Washington D.C. 2001 pp.460\u2013467."}],"container-title":["Networks"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/api.wiley.com\/onlinelibrary\/tdm\/v1\/articles\/10.1002%2Fnet.21662","content-type":"unspecified","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/api.wiley.com\/onlinelibrary\/tdm\/v1\/articles\/10.1002%2Fnet.21662","content-type":"application\/pdf","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/onlinelibrary.wiley.com\/doi\/pdf\/10.1002\/net.21662","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2024,6,11]],"date-time":"2024-06-11T20:56:34Z","timestamp":1718139394000},"score":1,"resource":{"primary":{"URL":"https:\/\/onlinelibrary.wiley.com\/doi\/10.1002\/net.21662"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2015,10,16]]},"references-count":25,"journal-issue":{"issue":"1","published-print":{"date-parts":[[2016,1]]}},"alternative-id":["10.1002\/net.21662"],"URL":"https:\/\/doi.org\/10.1002\/net.21662","archive":["Portico"],"relation":{},"ISSN":["0028-3045","1097-0037"],"issn-type":[{"value":"0028-3045","type":"print"},{"value":"1097-0037","type":"electronic"}],"subject":[],"published":{"date-parts":[[2015,10,16]]}}}