{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,2,21]],"date-time":"2025-02-21T15:49:29Z","timestamp":1740152969089,"version":"3.37.3"},"reference-count":40,"publisher":"Springer Science and Business Media LLC","issue":"2","license":[{"start":{"date-parts":[[2019,9,25]],"date-time":"2019-09-25T00:00:00Z","timestamp":1569369600000},"content-version":"tdm","delay-in-days":0,"URL":"http:\/\/www.springer.com\/tdm"},{"start":{"date-parts":[[2019,9,25]],"date-time":"2019-09-25T00:00:00Z","timestamp":1569369600000},"content-version":"vor","delay-in-days":0,"URL":"http:\/\/www.springer.com\/tdm"}],"funder":[{"DOI":"10.13039\/501100003382","name":"CREST, JST","doi-asserted-by":"crossref","award":["JPMJCR1402"],"award-info":[{"award-number":["JPMJCR1402"]}],"id":[{"id":"10.13039\/501100003382","id-type":"DOI","asserted-by":"crossref"}]},{"name":"KAKENHI, JSPS","award":["15K11985"],"award-info":[{"award-number":["15K11985"]}]}],"content-domain":{"domain":["link.springer.com"],"crossmark-restriction":false},"short-container-title":["Rev Socionetwork Strat"],"published-print":{"date-parts":[[2019,10]]},"DOI":"10.1007\/s12626-019-00054-0","type":"journal-article","created":{"date-parts":[[2019,9,25]],"date-time":"2019-09-25T15:48:02Z","timestamp":1569426482000},"page":"101-121","update-policy":"https:\/\/doi.org\/10.1007\/springer_crossmark_policy","source":"Crossref","is-referenced-by-count":1,"title":["What Graph Properties Are Constant-Time Testable?"],"prefix":"10.1007","volume":"13","author":[{"ORCID":"https:\/\/orcid.org\/0000-0001-6975-0422","authenticated-orcid":false,"given":"Hiro","family":"Ito","sequence":"first","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"297","published-online":{"date-parts":[[2019,9,25]]},"reference":[{"key":"54_CR1","doi-asserted-by":"publisher","first-page":"47","DOI":"10.1103\/RevModPhys.74.47","volume":"74","author":"R Albert","year":"2002","unstructured":"Albert, R., & Barab\u00e1si, A.-L. (2002). Statistical mechanics of complex networks. Review of Modern Physics, 74, 47\u201397.","journal-title":"Review of Modern Physics"},{"issue":"6","key":"54_CR2","doi-asserted-by":"publisher","first-page":"1703","DOI":"10.1137\/06064888X","volume":"37","author":"N Alon","year":"2008","unstructured":"Alon, N., Fischer, E., Newman, I., & Shapira, A. (2008). A combinatorial characterization of the testable graph properties: It\u2019s all about regularity. SIAM Journal on Computing, 37(6), 1703\u20131727.","journal-title":"SIAM Journal on Computing"},{"key":"54_CR3","doi-asserted-by":"publisher","first-page":"293","DOI":"10.1145\/100216.100254","volume":"1990","author":"N Alon","year":"1990","unstructured":"Alon, N., Seymour, P., & Thomas, R. (1990). Separator theorem for graphs with an excluded minor and its applications. Proceedings STOC, 1990, 293\u2013299.","journal-title":"Proceedings STOC"},{"key":"54_CR4","unstructured":"Alon, N., & Shapira, A. (2005). Every monotone graph property is testable. In Proceedings of STOC 2005 (pp.\u00a0128\u2013138). (Journal version: SIAM J. Comput., Vol.\u00a038, No.\u00a06, pp.\u00a01703\u20131727, (2008))."},{"key":"54_CR5","unstructured":"Alon, N., & Shapira, A. (2005). A characterization of the (natural) graph properties testable with one-sided error. In Proceedings of FOCS 2005 (pp.\u00a0429\u2013438) (Journal version: SIAM J. Comput., Vol.\u00a037, No.\u00a06, pp.\u00a01703\u20131727, (2008))."},{"key":"54_CR6","unstructured":"Babu, J., Khoury, A., & Newman, I. (2016). Every property of outerplanar graphs is testable. In Proceedings of RANDOM\u00a02016. LIPICS (pp. 1\u201321:19)."},{"key":"54_CR7","doi-asserted-by":"crossref","unstructured":"Benjamini, I., Schramm, O., & Shapira, A. (2008). Every minor-closed property of sparse graphs is testable. In Proceedings of STOC 2008. ACM (pp.\u00a0393\u2013402).","DOI":"10.1145\/1374376.1374433"},{"key":"54_CR8","unstructured":"Bottreau, A., & M\u00e9tivier, Y. (1998). Some remarks on the Kronecker product of graphs. In Information Processing Letters (vol. 68, pp.\u00a055\u201361). Amsterdam: Elsevier."},{"key":"54_CR9","doi-asserted-by":"publisher","first-page":"309","DOI":"10.1016\/S1389-1286(00)00083-9","volume":"33","author":"AZ Broder","year":"2000","unstructured":"Broder, A. Z., Kumar, S. R., Maghoul, F., Raghavan, R., Rajagoplalan, S., Stata, R., et al. (2000). Graph structure in the Web. Computer Networks, 33, 309\u2013320.","journal-title":"Computer Networks"},{"key":"54_CR10","first-page":"1263","volume":"2018","author":"D Cohen-Steiner","year":"2018","unstructured":"Cohen-Steiner, D., Kong, W., Sohler, C., & Valiant, G. (2018). Approximating the spectrum of a graph. Proceedings of SIGKDD, 2018, 1263\u20131271.","journal-title":"Proceedings of SIGKDD"},{"key":"54_CR11","doi-asserted-by":"publisher","first-page":"489","DOI":"10.1007\/s11786-010-0041-6","volume":"3","author":"C Cooper","year":"2010","unstructured":"Cooper, C., & Uehara, R. (2010). Scale free properties of random $$k$$-trees. Mathematics in Computer Science, 3, 489\u2013496.","journal-title":"Mathematics in Computer Science"},{"key":"54_CR12","volume-title":"Graph Theory","author":"R Diestel","year":"2016","unstructured":"Diestel, R. (2016). Graph Theory (5th ed.). Berlin: Springer.","edition":"5"},{"issue":"10","key":"54_CR13","doi-asserted-by":"publisher","first-page":"2667","DOI":"10.1016\/j.jfa.2008.01.010","volume":"254","author":"G Elek","year":"2008","unstructured":"Elek, G. (2008). $$L^2$$-spectral invariants and convergent sequence of finite graphs. Journal of Functional Analysis, 254(10), 2667\u20132689.","journal-title":"Journal of Functional Analysis"},{"key":"54_CR14","unstructured":"Fichtenberger, H., Peng, P., & Sohler, C. (2018). Every testable (infinite) property of bounded-degree graphs contains an infinite hyperfinite subproperty. \n                    arXiv: 1811.02937\n                    \n                   (also appeared in SODA2019)."},{"key":"54_CR15","doi-asserted-by":"publisher","first-page":"688","DOI":"10.1016\/j.tcs.2008.10.015","volume":"410","author":"Y Gao","year":"2009","unstructured":"Gao, Y. (2009). The degree distribution of random $$k$$-trees. Theoretical Computer Science, 410, 688\u2013695.","journal-title":"Theoretical Computer Science"},{"key":"54_CR16","doi-asserted-by":"publisher","DOI":"10.1017\/9781108135252","volume-title":"Introduction to Property Testing","author":"O Goldreich","year":"2017","unstructured":"Goldreich, O. (2017). Introduction to Property Testing. Cambridge: Cambridge University Press."},{"key":"54_CR17","doi-asserted-by":"publisher","first-page":"406","DOI":"10.1145\/258533.258627","volume":"1997","author":"O Goldreich","year":"1997","unstructured":"Goldreich, O., & Ron, D. (1997). Property testing in bounded degree graphs: Proc. STOC, 1997, 406\u2013415.","journal-title":"STOC"},{"issue":"02","key":"54_CR18","doi-asserted-by":"publisher","first-page":"534","DOI":"10.1137\/100789646","volume":"40","author":"O Goldreich","year":"2011","unstructured":"Goldreich, O., & Ron, D. (2011). On proximity-oblivious testing. SIAM Journal on Computing, 40(02), 534\u2013566.","journal-title":"SIAM Journal on Computing"},{"key":"54_CR19","unstructured":"Goldreich, O., & Trevisan, L. (2001). Three theorems regarding testing graph properties. In Proceedings FOCS 2001 (pp.\u00a0460\u2013469) (Journal version: Random Structures & Algorithms, Wiley, Vol.\u00a023, Issue\u00a01, pp.\u00a023\u201357, (2003))."},{"key":"54_CR20","unstructured":"Hassidim, A., Kelner, J.A., Nguyen, H.N., & Onak, K. (2009). Local graph partitions for approximation and testing. In: Proceedings FOCS 2009 (pp.\u00a022\u201331). IEEE."},{"key":"54_CR21","unstructured":"Ito, H. (2015). Every property is testable on a natural class of scale-free multigraphs, Cornell University (pp.\u00a01\u201312). \n                    arXiv:1504.00766"},{"key":"54_CR22","unstructured":"Ito, H. (2016). Every property is testable on a natural class of scale-free multigraphs. In: Proceedings of ESA\u00a02016, LIPICS (ISBN 978-3-95977-005-7) (vol.\u00a049, pp. 21:2\u201321:15)."},{"key":"54_CR23","doi-asserted-by":"crossref","unstructured":"Ito, H., & Iwama, K. (2009). Enumeration of isolated cliques and pseudo-cliques. In ACM Transactions on Algorithms (vol.\u00a05, Issue\u00a04, Article 40, pp.\u00a01\u201313).","DOI":"10.1145\/1597036.1597044"},{"key":"54_CR24","doi-asserted-by":"crossref","unstructured":"Ito, H., Iwama, K., & Osumi, T. (2005). Linear-time enumeration of isolated cliques. In Proceedings ESA2005, LNCS (vol. 3669, pp. 119\u2013130). Springer.","DOI":"10.1007\/11561071_13"},{"key":"54_CR25","first-page":"153","volume":"2010","author":"K Kawarabayashi","year":"2010","unstructured":"Kawarabayashi, K., & Reed, B. (2010). A separator theorem in minor-closed classes. Proceedings of FOCS, 2010, 153\u2013162.","journal-title":"Proceedings of FOCS"},{"key":"54_CR26","doi-asserted-by":"publisher","first-page":"1894","DOI":"10.1126\/science.1067014","volume":"294","author":"J Kleinberg","year":"2001","unstructured":"Kleinberg, J., & Lawrence, S. (2001). The structure of the web. Science, 294, 1894\u20131895.","journal-title":"Science"},{"key":"54_CR27","unstructured":"Kusumoto, M., & Yoshida, Y. (2014). Testing forest-isomorphizm in the adjacency list model. In Proceedings of ICALP2014\u00a0(1), LNSC 8572 (pp.\u00a0763\u2013774)."},{"key":"54_CR28","unstructured":"Levi, R., & Ron, D. (2013). A quasi-polynomial time partition oracle for graphs with an excluded mino. In Proceedings of ICALP 2013 (1), LNCS, 7965 (pp.\u00a0709\u2013720). Springer. (Journal version: ACM Transactions on Algorithms, Vol.\u00a011, No.\u00a03, Article\u00a024, pp.\u00a01\u201313, (2014))."},{"key":"54_CR29","doi-asserted-by":"crossref","unstructured":"Mahdian, M., & Xu, Y. (2007). Stochastic Kronecker graphs. In Proc. WAW 2007, LNCS, 4863. (pp.\u00a0179\u2013186). Springer.","DOI":"10.1007\/978-3-540-77004-6_14"},{"key":"54_CR30","doi-asserted-by":"crossref","unstructured":"Marko, S., & Ron, D. (2009). Approximating the distance to properties in bounded-degree and general sparse graphs. In ACM Transactions on Algorithms (Vol.\u00a05, Issue.\u00a02, Article\u00a0No.\u00a022).","DOI":"10.1145\/1497290.1497298"},{"key":"54_CR31","doi-asserted-by":"crossref","first-page":"167","DOI":"10.1137\/S003614450342480","volume":"45","author":"MEJ Newman","year":"2003","unstructured":"Newman, M. E. J. (2003). The structure and function of complex networks. SIAM Review, 45, 167\u2013256.","journal-title":"SIAM Review"},{"key":"54_CR32","unstructured":"Newman, I., & Sohler, C. (2011). Every property of hyperfinite graphs is testable. In PROC. STOC 2011, ACM (pp.\u00a0675\u2013784) (Journal version: SIAM\u00a0J.\u00a0Comput., Vol.\u00a042, No.\u00a03, pp.\u00a01095\u20131112, (2013))."},{"key":"54_CR33","unstructured":"Robertson, N., & Seymour, P.D. (1983\u20132012). Graph Minors I\u2013XXII. Journal of Combinatorial Theory, Series B."},{"issue":"5","key":"54_CR34","doi-asserted-by":"publisher","first-page":"661","DOI":"10.7155\/jgaa.00243","volume":"15","author":"T Shigezumi","year":"2011","unstructured":"Shigezumi, T., Uno, Y., & Watanabe, O. (2011). A new model for a scale-free hierarchical structure of isolated cliques. Journal of Graph Algorithms and Applications, 15(5), 661\u2013682.","journal-title":"Journal of Graph Algorithms and Applications"},{"key":"54_CR35","unstructured":"Szemer\u00e9di, E. (1978). Regular partitions of graphs. In J. C. Bermond, J. C. Fournier, M. Las Vergnas, & D. Sotteau (Eds.) Colloq. Internat. CNRS, Paris (pp.\u00a0399\u2013401)."},{"key":"54_CR36","unstructured":"S\u00e1rk\u00f6zy, G.N., Song, F., Szemer\u00e9di, E., & Trivedi, S. (2012). A practical regularity partitioning algorithm and its applications in clustering. (pp.\u00a01\u201313) Cornell University, Sept. 28. \n                    arXiv:1209.6540v1\n                    \n                  ."},{"key":"54_CR37","doi-asserted-by":"publisher","first-page":"440","DOI":"10.1038\/30918","volume":"393","author":"DJ Watts","year":"1998","unstructured":"Watts, D. J., & Strogatz, S. H. (1998). Collective dynamics of \u2018small-world\u2019 networks. Nature, 393, 440\u2013442.","journal-title":"Nature"},{"key":"54_CR38","unstructured":"Yoshida, Y., & Ito, H. (2008). Property testing on k-vertex connectivity of graphs. In: Proc. ICALP 2008, (1), LNCS, #5125 (pp.\u00a0539\u2013550). Springer (Journal version: Algorithmica, Vol. 62, No. 3\u20134, pp. 701\u2013712, (2012))."},{"key":"54_CR39","unstructured":"Yoshida, Y., Yamamoto, M., & Ito, H. (2009). An improved constant-time approximation algorithm for maximum matchings. In Proceedings of STOC 2009 (pp. 225\u2013234). (Journal version: SIAM J. Comput., Vol.\u00a041, No.\u00a04, pp.\u00a01074\u20131093, (2012))."},{"key":"54_CR40","doi-asserted-by":"publisher","first-page":"610","DOI":"10.1016\/j.physa.2005.09.042","volume":"364","author":"Z Zhang","year":"2006","unstructured":"Zhang, Z., Rong, L., & Comellas, F. (2006). High-dimensional random apollonian networks. Physica A: Statistical Mechanics and its Applications, 364, 610\u2013618.","journal-title":"Physica A: Statistical Mechanics and its Applications"}],"container-title":["The Review of Socionetwork Strategies"],"original-title":[],"language":"en","link":[{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/s12626-019-00054-0.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"text-mining"},{"URL":"http:\/\/link.springer.com\/article\/10.1007\/s12626-019-00054-0\/fulltext.html","content-type":"text\/html","content-version":"vor","intended-application":"text-mining"},{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/s12626-019-00054-0.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2020,9,24]],"date-time":"2020-09-24T02:11:14Z","timestamp":1600913474000},"score":1,"resource":{"primary":{"URL":"http:\/\/link.springer.com\/10.1007\/s12626-019-00054-0"}},"subtitle":["Dense Graphs, Sparse Graphs, and Complex Networks"],"short-title":[],"issued":{"date-parts":[[2019,9,25]]},"references-count":40,"journal-issue":{"issue":"2","published-print":{"date-parts":[[2019,10]]}},"alternative-id":["54"],"URL":"https:\/\/doi.org\/10.1007\/s12626-019-00054-0","relation":{},"ISSN":["2523-3173","1867-3236"],"issn-type":[{"type":"print","value":"2523-3173"},{"type":"electronic","value":"1867-3236"}],"subject":[],"published":{"date-parts":[[2019,9,25]]},"assertion":[{"value":"29 January 2019","order":1,"name":"received","label":"Received","group":{"name":"ArticleHistory","label":"Article History"}},{"value":"28 August 2019","order":2,"name":"accepted","label":"Accepted","group":{"name":"ArticleHistory","label":"Article History"}},{"value":"25 September 2019","order":3,"name":"first_online","label":"First Online","group":{"name":"ArticleHistory","label":"Article History"}}]}}