{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,1,15]],"date-time":"2026-01-15T21:51:42Z","timestamp":1768513902916,"version":"3.49.0"},"publisher-location":"Cham","reference-count":32,"publisher":"Springer International Publishing","isbn-type":[{"value":"9783319267838","type":"print"},{"value":"9783319267845","type":"electronic"}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":[],"published-print":{"date-parts":[[2015]]},"DOI":"10.1007\/978-3-319-26784-5_3","type":"book-chapter","created":{"date-parts":[[2015,12,9]],"date-time":"2015-12-09T10:07:47Z","timestamp":1449655667000},"page":"29-41","source":"Crossref","is-referenced-by-count":4,"title":["Hyperbolicity, Degeneracy, and Expansion of Random Intersection Graphs"],"prefix":"10.1007","author":[{"given":"Matthew","family":"Farrell","sequence":"first","affiliation":[]},{"given":"Timothy D.","family":"Goodrich","sequence":"additional","affiliation":[]},{"given":"Nathan","family":"Lemons","sequence":"additional","affiliation":[]},{"given":"Felix","family":"Reidl","sequence":"additional","affiliation":[]},{"given":"Fernando","family":"S\u00e1nchez Villaamil","sequence":"additional","affiliation":[]},{"given":"Blair D.","family":"Sullivan","sequence":"additional","affiliation":[]}],"member":"297","published-online":{"date-parts":[[2015,12,9]]},"reference":[{"issue":"3","key":"3_CR1","doi-asserted-by":"publisher","first-page":"1081","DOI":"10.1214\/13-AAP942","volume":"24","author":"FG Ball","year":"2014","unstructured":"Ball, F.G., Sirl, D.J., Trapman, P.: Epidemics on random intersection graphs. Ann. Appl. Probab. 24(3), 1081\u20131128 (2014)","journal-title":"Ann. Appl. Probab."},{"issue":"1\u20132","key":"3_CR2","doi-asserted-by":"publisher","first-page":"171","DOI":"10.1007\/s10623-010-9481-x","volume":"64","author":"SR Blackburn","year":"2012","unstructured":"Blackburn, S.R., Stinson, D.R., Upadhyay, J.: On the complexity of the herding attack and some related attacks on hash functions. Des. Codes Crypt. 64(1\u20132), 171\u2013193 (2012)","journal-title":"Des. Codes Crypt."},{"key":"3_CR3","doi-asserted-by":"publisher","first-page":"1254","DOI":"10.1214\/12-AAP874","volume":"23","author":"M Bloznelis","year":"2013","unstructured":"Bloznelis, M.: Degree and clustering coefficient in sparse random intersection graphs. Ann. Appl. Probab. 23, 1254\u20131289 (2013)","journal-title":"Ann. Appl. Probab."},{"key":"3_CR4","doi-asserted-by":"publisher","first-page":"1","DOI":"10.1214\/EJP.v18-2277","volume":"18","author":"M Bloznelis","year":"2013","unstructured":"Bloznelis, M., Jaworski, J., Kurauskas, V.: Assortativity and clustering of sparse random intersection graphs. Electron. J. Probab. 18, 1\u201324 (2013)","journal-title":"Electron. J. Probab."},{"key":"3_CR5","series-title":"Grundlehren Der Mathematischen Wissenschaften","volume-title":"Metric Spaces of Non-Positive Curvature","author":"M Bridson","year":"2009","unstructured":"Bridson, M., H\u00e4fliger, A.: Metric Spaces of Non-Positive Curvature. Grundlehren Der Mathematischen Wissenschaften. Springer, Heidelberg (2009)"},{"key":"3_CR6","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"278","DOI":"10.1007\/978-3-642-35261-4_31","volume-title":"Algorithms and Computation","author":"W Chen","year":"2012","unstructured":"Chen, W., Fang, W., Hu, G., Mahoney, M.W.: On the hyperbolicity of small-world and tree-like random graphs. In: Chao, K.-M., Hsu, T., Lee, D.-T. (eds.) ISAAC 2012. LNCS, vol. 7676, pp. 278\u2013288. Springer, Heidelberg (2012)"},{"key":"3_CR7","doi-asserted-by":"crossref","unstructured":"Chepoi, V., Dragan, F.F., Estellon, B., Habib, M., Vax\u00e8s, Y.: Diameters, centers, and approximating trees of $$\\delta $$ \u03b4 -hyperbolic geodesic spaces and graphs. In: Symposium on Computational Geometry, pp. 59\u201368 (2008)","DOI":"10.1145\/1377676.1377687"},{"key":"3_CR8","doi-asserted-by":"publisher","first-page":"661","DOI":"10.1017\/S0269964809990064","volume":"23","author":"M Deijfen","year":"2009","unstructured":"Deijfen, M., Kets, W.: Random intersection graphs with tunable degree distribution and clustering. Probab. Eng. Informational Sci. 23, 661\u2013674 (2009)","journal-title":"Probab. Eng. Informational Sci."},{"key":"3_CR9","unstructured":"Demaine, E.D., Reidl, F., Rossmanith, P., S\u00e1nchez Villaamil, F., Sikdar, S., Sullivan, B.D.: Structural sparsity of complex networks: Bounded expansion in random models and real-world graphs. CoRR, abs\/1406.2587 (2014)"},{"issue":"5","key":"3_CR10","doi-asserted-by":"crossref","first-page":"36","DOI":"10.1145\/2499483","volume":"60","author":"Z Dvo\u0159\u00e1k","year":"2013","unstructured":"Dvo\u0159\u00e1k, Z., Kr\u00e1l\u2019, D., Thomas, R.: Testing first-order properties for subclasses of sparse graphs. J. ACM 60(5), 36 (2013)","journal-title":"J. ACM"},{"key":"3_CR11","doi-asserted-by":"crossref","unstructured":"Farrell, M., Goodrich, T., Lemons, N., Reidl, F., S\u00e1nchez Villaamil, F., Sullivan, B.D.: Hyperbolicity, degeneracy, and expansion of random intersection graphs. CoRR, abs\/1409.8196 (2014)","DOI":"10.1007\/978-3-319-26784-5_3"},{"key":"3_CR12","doi-asserted-by":"publisher","first-page":"243","DOI":"10.1007\/978-3-642-24466-7_25","volume-title":"Challenges at the Interface Of Data Analysis Computer Science And Optimization","author":"E Godehardt","year":"2012","unstructured":"Godehardt, E., Jarowski, J., Rybarczyk, K.: Clustering coefficients of random intersection graphs. In: Gaul, W.A., Geyer-Schulz, A., Schmidt-Thieme, L., Kunze, J. (eds.) Challenges at the Interface Of Data Analysis Computer Science And Optimization, pp. 243\u2013253. Springer, Heidelberg (2012)"},{"key":"3_CR13","series-title":"Mathematical Sciences Research Institute Publications","doi-asserted-by":"publisher","first-page":"75","DOI":"10.1007\/978-1-4613-9586-7_3","volume-title":"Essays in Group Theory","author":"M Gromov","year":"1987","unstructured":"Gromov, M.: Hyperbolic groups. In: Gersten, S.M. (ed.) Essays in Group Theory. Mathematical Sciences Research Institute Publications, vol. 8, pp. 75\u2013263. Springer, New York (1987)"},{"key":"3_CR14","doi-asserted-by":"publisher","first-page":"2152","DOI":"10.1016\/j.disc.2006.05.013","volume":"306","author":"J Jaworski","year":"2006","unstructured":"Jaworski, J., Karo\u0144ski, M., Stark, D.: The degree of a typical vertex in generalized random intersection graph models. Discrete Math. 306, 2152\u20132165 (2006)","journal-title":"Discrete Math."},{"issue":"2","key":"3_CR15","doi-asserted-by":"publisher","first-page":"157","DOI":"10.1002\/jgt.20275","volume":"57","author":"E Jonckheere","year":"2008","unstructured":"Jonckheere, E., Lohsoonthorn, P., Bonahon, F.: Scaled Gromov hyperbolic graphs. J. Graph Theory 57(2), 157\u2013180 (2008)","journal-title":"J. Graph Theory"},{"key":"3_CR16","doi-asserted-by":"publisher","first-page":"131","DOI":"10.1017\/S0963548398003459","volume":"8","author":"M Karo\u0144ski","year":"1999","unstructured":"Karo\u0144ski, M., Scheinerman, E.K., Singer-Cohen, K.B.: On random intersection graphs: the subgraph problem. Combin. Probab. Comput. 8, 131\u2013159 (1999)","journal-title":"Combin. Probab. Comput."},{"key":"3_CR17","doi-asserted-by":"crossref","unstructured":"Kleinberg, R.: Geographic routing using hyperbolic space. In: Proceedings of the 26th INFOCOM, pp. 1902\u20131909 (2007)","DOI":"10.1109\/INFCOM.2007.221"},{"key":"3_CR18","doi-asserted-by":"publisher","first-page":"066108","DOI":"10.1103\/PhysRevE.84.066108","volume":"84","author":"O Narayan","year":"2011","unstructured":"Narayan, O., Saniee, I.: Large-scale curvature of networks. Phys. Rev. E 84, 066108 (2011)","journal-title":"Phys. Rev. E"},{"issue":"3","key":"3_CR19","doi-asserted-by":"publisher","first-page":"760","DOI":"10.1016\/j.ejc.2006.07.013","volume":"29","author":"J Ne\u0161et\u0159il","year":"2008","unstructured":"Ne\u0161et\u0159il, J., Ossona de Mendez, P.: Grad and classes with bounded expansion I. and II. Eur. J. Comb. 29(3), 760\u2013791 (2008)","journal-title":"Eur. J. Comb."},{"issue":"3","key":"3_CR20","doi-asserted-by":"publisher","first-page":"868","DOI":"10.2178\/jsl\/1278682204","volume":"75","author":"J Ne\u0161et\u0159il","year":"2010","unstructured":"Ne\u0161et\u0159il, J., Ossona de Mendez, P.: First order properties on nowhere dense structures. J. Symbolic Logic 75(3), 868\u2013887 (2010)","journal-title":"J. Symbolic Logic"},{"issue":"4","key":"3_CR21","doi-asserted-by":"publisher","first-page":"600","DOI":"10.1016\/j.ejc.2011.01.006","volume":"32","author":"J Ne\u0161et\u0159il","year":"2011","unstructured":"Ne\u0161et\u0159il, J., Ossona de Mendez, P.: On nowhere dense graphs. Eur. J. Comb. 32(4), 600\u2013617 (2011)","journal-title":"Eur. J. Comb."},{"key":"3_CR22","series-title":"Algorithms and Combinatorics","doi-asserted-by":"crossref","DOI":"10.1007\/978-3-642-27875-4","volume-title":"Sparsity: Graphs, Structures, and Algorithms","author":"J Ne\u0161et\u0159il","year":"2012","unstructured":"Ne\u0161et\u0159il, J., Ossona de Mendez, P.: Sparsity: Graphs, Structures, and Algorithms. Algorithms and Combinatorics, vol. 28. Springer, Heidelberg (2012)"},{"issue":"3","key":"3_CR23","doi-asserted-by":"publisher","first-page":"350","DOI":"10.1016\/j.ejc.2011.09.008","volume":"33","author":"J Ne\u0161et\u0159il","year":"2012","unstructured":"Ne\u0161et\u0159il, J., Ossona de Mendez, P., Wood, D.R.: Characterisations and examples of graph classes with bounded expansion. Eur. J. Comb. 33(3), 350\u2013373 (2012)","journal-title":"Eur. J. Comb."},{"issue":"2","key":"3_CR24","doi-asserted-by":"publisher","first-page":"026118","DOI":"10.1103\/PhysRevE.64.026118","volume":"64","author":"MEJ Newman","year":"2001","unstructured":"Newman, M.E.J., Strogatz, S.H., Watts, D.J.: Random graphs with arbitrary degree distributions and their applications. Phys. Rev. E 64(2), 026118 (2001)","journal-title":"Phys. Rev. E"},{"key":"3_CR25","doi-asserted-by":"publisher","first-page":"1998","DOI":"10.1016\/j.disc.2011.05.029","volume":"311","author":"K Rybarczyk","year":"2011","unstructured":"Rybarczyk, K.: Diameter, connectivity, and phase transition of the uniform random intersection graph. Discrete Math. 311, 1998\u20132019 (2011)","journal-title":"Discrete Math."},{"key":"3_CR26","unstructured":"Rybarczyk, K.: The coupling method for inhomogeneous random intersection graphs. Preprint. arXiv:1301.0466 (2013)"},{"key":"3_CR27","unstructured":"Singer-Cohen, K.: Random intersection graphs. Ph.D. thesis, Department of Mathematical Sciences, The Johns Hopkins University (1995)"},{"key":"3_CR28","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.: Collective dynamics of \u2018small-world\u2019 networks. Nature 393, 440\u2013442 (1998)","journal-title":"Nature"},{"key":"3_CR29","doi-asserted-by":"crossref","unstructured":"Zhao, J.: Minimum node degree and k-connectivity in wireless networks with unreliable links. In: 2014 IEEE International Symposium on Information Theory (ISIT), pp. 246\u2013250. IEEE (2014)","DOI":"10.1109\/ISIT.2014.6874832"},{"key":"3_CR30","unstructured":"Zhao, J., Yagan, O., Gligor, V.: On $$k$$ k -connectivity and minimum vertex degree in random $$s$$ s -intersection graphs. In: ANALCO (2015)"},{"key":"3_CR31","doi-asserted-by":"crossref","unstructured":"Zhao, J., Yagan, O., Gligor, V.: Connectivity in secure wireless sensor networks under transmission constraints. In: 2014 52nd Annual Allerton Conference on Communication, Control, and Computing, pp. 1294\u20131301. IEEE (2014)","DOI":"10.1109\/ALLERTON.2014.7028605"},{"key":"3_CR32","doi-asserted-by":"crossref","unstructured":"Zhao, J., Yagan, O., Gligor, V.: On the strengths of connectivity and robustness in general random intersection graphs. In: 2014 IEEE 53rd Annual Conference on Decision and Control (CDC), pp. 3661\u20133668. IEEE (2014)","DOI":"10.1109\/CDC.2014.7039959"}],"container-title":["Lecture Notes in Computer Science","Algorithms and Models for the Web Graph"],"original-title":[],"link":[{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/978-3-319-26784-5_3","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,5,31]],"date-time":"2025-05-31T18:18:44Z","timestamp":1748715524000},"score":1,"resource":{"primary":{"URL":"http:\/\/link.springer.com\/10.1007\/978-3-319-26784-5_3"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2015]]},"ISBN":["9783319267838","9783319267845"],"references-count":32,"URL":"https:\/\/doi.org\/10.1007\/978-3-319-26784-5_3","relation":{},"ISSN":["0302-9743","1611-3349"],"issn-type":[{"value":"0302-9743","type":"print"},{"value":"1611-3349","type":"electronic"}],"subject":[],"published":{"date-parts":[[2015]]}}}