Isoperimetric Numbers of Randomly Perturbed Intersection Graphs

Shang, Yilun (2019) Isoperimetric Numbers of Randomly Perturbed Intersection Graphs. Symmetry, 11 (4). ISSN 2073-8994

Text (Full text)
Shang - Isoperimetric Numbers of Randomly Perturbed Intersection Graphs OA.pdf - Published Version
Available under License Creative Commons Attribution 4.0.

Download (304kB) | Preview
Official URL:


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–isoperimetric number and the edge–isoperimetric number of the randomly perturbed intersection graph on n vertices are Ω(1/lnn) 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.

Item Type: Article
Uncontrolled Keywords: isoperimetric number; random graph; intersection graph; social network
Subjects: G100 Mathematics
Department: Faculties > Engineering and Environment > Computer and Information Sciences
Depositing User: Paul Burns
Date Deposited: 01 Apr 2019 14:37
Last Modified: 01 Aug 2021 12:20

Actions (login required)

View Item View Item


Downloads per month over past year

View more statistics