{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,10,12]],"date-time":"2025-10-12T03:36:02Z","timestamp":1760240162438,"version":"build-2065373602"},"reference-count":39,"publisher":"MDPI AG","issue":"4","license":[{"start":{"date-parts":[[2019,4,1]],"date-time":"2019-04-01T00:00:00Z","timestamp":1554076800000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/creativecommons.org\/licenses\/by\/4.0\/"}],"funder":[{"DOI":"10.13039\/100010052","name":"Northumbria University","doi-asserted-by":"publisher","award":["N\/A"],"award-info":[{"award-number":["N\/A"]}],"id":[{"id":"10.13039\/100010052","id-type":"DOI","asserted-by":"publisher"}]}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":["Symmetry"],"abstract":"<jats:p>Social networks describe social interactions between people, which are often modeled by intersection graphs. In this paper, we propose an intersection graph model that is induced by adding a sparse random bipartite graph to a given bipartite graph. Under some mild conditions, we show that the vertex\u2013isoperimetric number and the edge\u2013isoperimetric number of the randomly perturbed intersection graph on n vertices are \r\n          \r\n            \r\n              \r\n                \u03a9\r\n                (\r\n                1\r\n                \/\r\n                ln\r\n                n\r\n                )\r\n              \r\n            \r\n          \r\n         asymptomatically almost surely. Numerical simulations for small graphs extracted from two real-world social networks, namely, the board interlocking network and the scientific collaboration network, were performed. It was revealed that the effect of increasing isoperimetric numbers (i.e., expansion properties) on randomly perturbed intersection graphs is presumably independent of the order of the network.<\/jats:p>","DOI":"10.3390\/sym11040452","type":"journal-article","created":{"date-parts":[[2019,4,2]],"date-time":"2019-04-02T03:21:26Z","timestamp":1554175286000},"page":"452","update-policy":"https:\/\/doi.org\/10.3390\/mdpi_crossmark_policy","source":"Crossref","is-referenced-by-count":1,"title":["Isoperimetric Numbers of Randomly Perturbed Intersection Graphs"],"prefix":"10.3390","volume":"11","author":[{"ORCID":"https:\/\/orcid.org\/0000-0002-2817-3400","authenticated-orcid":false,"given":"Yilun","family":"Shang","sequence":"first","affiliation":[{"name":"Department of Computer and Information Sciences, Faculty of Engineering and Environment, Northumbria University, Newcastle NE1 8ST, UK"}]}],"member":"1968","published-online":{"date-parts":[[2019,4,1]]},"reference":[{"key":"ref_1","doi-asserted-by":"crossref","unstructured":"Newman, M.E.J. (2010). Networks: An Introduction, Oxford University Press.","DOI":"10.1093\/acprof:oso\/9780199206650.003.0001"},{"key":"ref_2","doi-asserted-by":"crossref","first-page":"215","DOI":"10.1016\/j.ipl.2004.03.007","article-title":"Bipartite structure of all complex networks","volume":"90","author":"Guillaume","year":"2004","journal-title":"Inf. Process. Lett."},{"key":"ref_3","unstructured":"Kadushin, C. (2012). Understanding Social Networks: Theories, Concepts, and Findings, Oxford University Press."},{"key":"ref_4","doi-asserted-by":"crossref","first-page":"440","DOI":"10.1038\/30918","article-title":"Collective dynamics of \u2018small-world\u2019 networks","volume":"393","author":"Watts","year":"1998","journal-title":"Nature"},{"key":"ref_5","doi-asserted-by":"crossref","first-page":"404","DOI":"10.1073\/pnas.98.2.404","article-title":"The structure of scientific collaboration networks","volume":"98","author":"Newman","year":"2001","journal-title":"Proc. Natl. Acad. Sci. USA"},{"key":"ref_6","doi-asserted-by":"crossref","unstructured":"Eschenauer, L., and Gligor, V. (2002, January 18\u201322). A key-management scheme for distributed sensor networks. Proceedings of the 9th ACM Conference on Computer and Communications Security, Washington, DC, USA.","DOI":"10.1145\/586110.586117"},{"key":"ref_7","doi-asserted-by":"crossref","first-page":"303","DOI":"10.4064\/fm-33-1-303-307","article-title":"Sur deux propri\u00e9t\u00e9s des classes d\u2019ensembles","volume":"33","author":"Marczewski","year":"1945","journal-title":"Fund. Math."},{"key":"ref_8","doi-asserted-by":"crossref","first-page":"131","DOI":"10.1017\/S0963548398003459","article-title":"On random intersection graphs: The subgraph problem","volume":"8","author":"Scheinerman","year":"1999","journal-title":"Comb. Probab. Comput."},{"key":"ref_9","unstructured":"Singer-Cohen, K.B. (1995). Random Intersection Graphs. [Ph.D. Thesis, Johns Hopkins University]."},{"key":"ref_10","doi-asserted-by":"crossref","unstructured":"Frieze, A., and Karo\u0144ski, M. (2016). Introduction to Random Graphs, Cambridge University Press.","DOI":"10.1017\/CBO9781316339831"},{"key":"ref_11","doi-asserted-by":"crossref","first-page":"R23","DOI":"10.37236\/295","article-title":"Degree distributions in general random intersection graphs","volume":"17","author":"Shang","year":"2010","journal-title":"Electron. J. Combin."},{"key":"ref_12","doi-asserted-by":"crossref","first-page":"11","DOI":"10.1007\/s10623-015-0124-0","article-title":"Graph-theoretic design and analysis of key predistribution schemes","volume":"81","author":"Kendall","year":"2016","journal-title":"Des. Codes Cryptogr."},{"key":"ref_13","doi-asserted-by":"crossref","first-page":"2121","DOI":"10.1109\/TAC.2016.2601564","article-title":"On connectivity and robustness in random intersection graphs","volume":"62","author":"Zhao","year":"2017","journal-title":"IEEE Trans. Autom. Contr."},{"key":"ref_14","doi-asserted-by":"crossref","first-page":"465","DOI":"10.7151\/dmgt.1955","article-title":"The chromatic number of random intersection graphs","volume":"37","author":"Rybarczyk","year":"2017","journal-title":"Discuss. Math. Graph Theory"},{"key":"ref_15","unstructured":"Lausen, B., Krolak-Schwerdt, S., and Boehmer, M. (2015). Recent progress in complex network analysis: Models of random intersection graphs. European Conference on Data Analysis, Springer."},{"key":"ref_16","unstructured":"Lausen, B., Krolak-Schwerdt, S., and Boehmer, M. (2015). Recent progress in complex network analysis: Properties of random intersection graphs. European Conference on Data Analysis, Springer."},{"key":"ref_17","doi-asserted-by":"crossref","first-page":"241","DOI":"10.1016\/S0195-6698(88)80014-3","article-title":"The isoperimetric number of random regular graphs","volume":"9","year":"1988","journal-title":"Eur. J. Comb."},{"key":"ref_18","doi-asserted-by":"crossref","first-page":"145","DOI":"10.1017\/S096354839700299X","article-title":"On the edge-expansion of graphs","volume":"6","author":"Alon","year":"1997","journal-title":"Comb. Probab. Comput."},{"key":"ref_19","doi-asserted-by":"crossref","first-page":"101","DOI":"10.1002\/rsa.20171","article-title":"The isoperimetric constant of the random graph process","volume":"32","author":"Benjamini","year":"2008","journal-title":"Random Struct. Algorithms"},{"key":"ref_20","doi-asserted-by":"crossref","first-page":"845","DOI":"10.1007\/s00222-014-0560-x","article-title":"Expansion of random graphs: New proofs, new results","volume":"201","author":"Puder","year":"2015","journal-title":"Invent. Math."},{"key":"ref_21","doi-asserted-by":"crossref","first-page":"439","DOI":"10.1090\/S0273-0979-06-01126-8","article-title":"Expander graphs and their applications","volume":"43","author":"Hoory","year":"2006","journal-title":"Bull. Am. Math. Soc."},{"key":"ref_22","doi-asserted-by":"crossref","first-page":"649","DOI":"10.1209\/epl\/i2005-10441-3","article-title":"Spectral scaling and good expansion properties in complex networks","volume":"73","author":"Estrada","year":"2006","journal-title":"Europhys. Lett."},{"key":"ref_23","doi-asserted-by":"crossref","first-page":"8577","DOI":"10.1073\/pnas.0601602103","article-title":"Modularity and community structure in networks","volume":"103","author":"Newman","year":"2006","journal-title":"Proc. Natl. Acad. Sci. USA"},{"key":"ref_24","doi-asserted-by":"crossref","first-page":"341","DOI":"10.1016\/S0375-9601(99)00757-4","article-title":"Renormalization group analysis of the small-world network model","volume":"263","author":"Newman","year":"1999","journal-title":"Phys. Lett. A"},{"key":"ref_25","doi-asserted-by":"crossref","first-page":"493","DOI":"10.18514\/MMN.2012.347","article-title":"A sharp threshold for rainbow connection in small-world networks","volume":"13","author":"Shang","year":"2012","journal-title":"Miskolc Math. Notes"},{"key":"ref_26","doi-asserted-by":"crossref","first-page":"33","DOI":"10.1002\/rsa.10070","article-title":"How many random edges make a dense graph Hamiltonian?","volume":"22","author":"Bohman","year":"2003","journal-title":"Random Struct. Algorithms"},{"key":"ref_27","doi-asserted-by":"crossref","first-page":"105","DOI":"10.1002\/rsa.10112","article-title":"Adding random edges to dense graphs","volume":"24","author":"Bohman","year":"2004","journal-title":"Random Struct. Algorithms"},{"key":"ref_28","doi-asserted-by":"crossref","first-page":"180","DOI":"10.1002\/rsa.20097","article-title":"On smoothed analysis in dense graphs and formulas","volume":"29","author":"Krivelevich","year":"2006","journal-title":"Random Struct. Algorithms"},{"key":"ref_29","doi-asserted-by":"crossref","first-page":"131","DOI":"10.1080\/15427951.2007.10129290","article-title":"Expansion and lack thereof in randomly perturbed graphs","volume":"4","author":"Flaxman","year":"2007","journal-title":"Internet Math."},{"key":"ref_30","doi-asserted-by":"crossref","first-page":"1654","DOI":"10.1137\/151002496","article-title":"Smoothed analysis on connected graphs","volume":"29","author":"Krivelevich","year":"2015","journal-title":"SIAM J. Discrete Math."},{"key":"ref_31","doi-asserted-by":"crossref","first-page":"37","DOI":"10.1239\/aap\/1427814580","article-title":"The mixing time of the Newman-Watts small-world model","volume":"47","author":"Lei","year":"2015","journal-title":"Adv. Appl. Probab."},{"key":"ref_32","doi-asserted-by":"crossref","first-page":"159","DOI":"10.1017\/S0963548318000366","article-title":"Tilings in randomly perturbed dense graphs","volume":"28","author":"Balogh","year":"2019","journal-title":"Combin. Probab. Comput."},{"key":"ref_33","doi-asserted-by":"crossref","first-page":"155","DOI":"10.1137\/15M1032910","article-title":"Bounded-degree spanning trees in randomly perturbed graphs","volume":"31","author":"Krivelevich","year":"2017","journal-title":"SIAM J. Discrete Math."},{"key":"ref_34","doi-asserted-by":"crossref","first-page":"155","DOI":"10.1016\/j.endm.2017.06.033","article-title":"Embedding spanning bounded degree subgraphs in randomly perturbed graphs","volume":"61","author":"Montgomery","year":"2017","journal-title":"Electron. Notes Discrete Math."},{"key":"ref_35","doi-asserted-by":"crossref","first-page":"274","DOI":"10.1016\/0095-8956(89)90029-4","article-title":"Isoperimetric numbers of graphs","volume":"47","author":"Mohar","year":"1989","journal-title":"J. Comb. Theory Ser. B"},{"key":"ref_36","doi-asserted-by":"crossref","first-page":"218","DOI":"10.1016\/j.jctb.2008.06.004","article-title":"On tree width, bramble size, and expansion","volume":"99","author":"Grohe","year":"2009","journal-title":"J. Comb. Theory Ser. B"},{"key":"ref_37","doi-asserted-by":"crossref","first-page":"44","DOI":"10.1016\/j.scaman.2010.10.002","article-title":"For the few not the many? The effects of affirmative action on presence, prominence, and social capital of women directors in Norway","volume":"27","author":"Seierstad","year":"2011","journal-title":"Scand. J. Manag."},{"key":"ref_38","doi-asserted-by":"crossref","first-page":"436","DOI":"10.1002\/rsa.20114","article-title":"Coloring complete bipartite graphs from random lists","volume":"29","author":"Krivelevich","year":"2006","journal-title":"Random Struct. Algorithms"},{"key":"ref_39","doi-asserted-by":"crossref","first-page":"117","DOI":"10.1007\/s11464-011-0165-2","article-title":"Joint probability generating function for degrees of active\/passive random intersection graphs","volume":"7","author":"Shang","year":"2012","journal-title":"Front. Math. China"}],"container-title":["Symmetry"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/www.mdpi.com\/2073-8994\/11\/4\/452\/pdf","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,10,11]],"date-time":"2025-10-11T12:42:02Z","timestamp":1760186522000},"score":1,"resource":{"primary":{"URL":"https:\/\/www.mdpi.com\/2073-8994\/11\/4\/452"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2019,4,1]]},"references-count":39,"journal-issue":{"issue":"4","published-online":{"date-parts":[[2019,4]]}},"alternative-id":["sym11040452"],"URL":"https:\/\/doi.org\/10.3390\/sym11040452","relation":{},"ISSN":["2073-8994"],"issn-type":[{"type":"electronic","value":"2073-8994"}],"subject":[],"published":{"date-parts":[[2019,4,1]]}}}