Isoperimetric Numbers of Randomly Perturbed Intersection Graphs

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

[img]
Preview
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: https://doi.org/10.3390/sym11040452

Abstract

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: 11 Oct 2019 07:50
URI: http://nrl.northumbria.ac.uk/id/eprint/38672

Actions (login required)

View Item View Item

Downloads

Downloads per month over past year

View more statistics


Policies: NRL Policies | NRL University Deposit Policy | NRL Deposit Licence