Isoperimetric Numbers of Randomly Perturbed Intersection Graphs

Research output: Contribution to journalArticlepeer-review

1 Citation (Scopus)
12 Downloads (Pure)

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.
Original languageEnglish
Article number452
JournalSymmetry
Volume11
Issue number4
DOIs
Publication statusPublished - 1 Apr 2019

Fingerprint

Dive into the research topics of 'Isoperimetric Numbers of Randomly Perturbed Intersection Graphs'. Together they form a unique fingerprint.

Cite this