Finding induced subgraphs in scale-free inhomogeneous random graphs

Ellen Cardinaels; Johan S. H. van Leeuwaarden; Clara Stegehuis

doi:10.1007/978-3-319-92871-5_1

Finding induced subgraphs in scale-free inhomogeneous random graphs

Ellen Cardinaels, Johan S. H. van Leeuwaarden, Clara Stegehuis^*

^*Corresponding author for this work

Research output: Chapter in Book/Report/Conference proceeding › Conference contribution › Academic › peer-review

58 Downloads (Pure)

Abstract

We study the induced subgraph isomorphism problem on inhomogeneous random graphs with infinite variance power-law degrees. We provide a fast algorithm that determines for any connected graph $H$ on $k$ vertices if it exists as induced subgraph in a random graph with $n$ vertices. By exploiting the scale-free graph structure, the algorithm runs in $O(n k)$ time for small values of $k$. We test our algorithm on several real-world data sets.

Original language	English
Title of host publication	Algorithms and Models for the Web Graph
Subtitle of host publication	15th International Workshop, WAW 2018, Moscow, Russia, May 17-18, 2018, Proceedings
Editors	Anthony Bonato, Pawel Pralat, Andrei Raigorodskii
Publisher	Springer
Pages	1-15
Number of pages	14
ISBN (Electronic)	978-3-319-92871-5
ISBN (Print)	978-3-319-92870-8
DOIs	https://doi.org/10.1007/978-3-319-92871-5_1
Publication status	Published - 30 May 2018
Externally published	Yes
Event	International Workshop on Algorithms and Models for the Web-Graph 2018 - Moscow, Russian Federation Duration: 17 May 2018 → 18 May 2018

Workshop

Workshop	International Workshop on Algorithms and Models for the Web-Graph 2018
Abbreviated title	WAW 2018
Country/Territory	Russian Federation
City	Moscow
Period	17/05/18 → 18/05/18

Keywords

cs.DS
math.CO

Access to Document

10.1007/978-3-319-92871-5_1

findingAccepted author version, 518 KBLicence: CC BY

Cite this

Cardinaels, E., Leeuwaarden, J. S. H. V., & Stegehuis, C. (2018). Finding induced subgraphs in scale-free inhomogeneous random graphs. In A. Bonato, P. Pralat, & A. Raigorodskii (Eds.), Algorithms and Models for the Web Graph: 15th International Workshop, WAW 2018, Moscow, Russia, May 17-18, 2018, Proceedings (pp. 1-15). Springer. https://doi.org/10.1007/978-3-319-92871-5_1

@inproceedings{ce197cb8350e461da3926e1e2b4f8cb4,

title = "Finding induced subgraphs in scale-free inhomogeneous random graphs",

abstract = " We study the induced subgraph isomorphism problem on inhomogeneous random graphs with infinite variance power-law degrees. We provide a fast algorithm that determines for any connected graph $H$ on $k$ vertices if it exists as induced subgraph in a random graph with $n$ vertices. By exploiting the scale-free graph structure, the algorithm runs in $O(n k)$ time for small values of $k$. We test our algorithm on several real-world data sets. ",

keywords = "cs.DS, math.CO",

author = "Ellen Cardinaels and Leeuwaarden, {Johan S. H. van} and Clara Stegehuis",

year = "2018",

month = may,

day = "30",

doi = "10.1007/978-3-319-92871-5_1",

language = "English",

isbn = "978-3-319-92870-8",

pages = "1--15",

editor = "Anthony Bonato and Pawel Pralat and Andrei Raigorodskii",

booktitle = "Algorithms and Models for the Web Graph",

publisher = "Springer",

address = "Germany",

note = "International Workshop on Algorithms and Models for the Web-Graph 2018, WAW 2018 ; Conference date: 17-05-2018 Through 18-05-2018",

}

Cardinaels, E, Leeuwaarden, JSHV & Stegehuis, C 2018, Finding induced subgraphs in scale-free inhomogeneous random graphs. in A Bonato, P Pralat & A Raigorodskii (eds), Algorithms and Models for the Web Graph: 15th International Workshop, WAW 2018, Moscow, Russia, May 17-18, 2018, Proceedings. Springer, pp. 1-15, International Workshop on Algorithms and Models for the Web-Graph 2018, Moscow, Russian Federation, 17/05/18. https://doi.org/10.1007/978-3-319-92871-5_1

Finding induced subgraphs in scale-free inhomogeneous random graphs. / Cardinaels, Ellen; Leeuwaarden, Johan S. H. van; Stegehuis, Clara.
Algorithms and Models for the Web Graph: 15th International Workshop, WAW 2018, Moscow, Russia, May 17-18, 2018, Proceedings. ed. / Anthony Bonato; Pawel Pralat; Andrei Raigorodskii. Springer, 2018. p. 1-15.

Research output: Chapter in Book/Report/Conference proceeding › Conference contribution › Academic › peer-review

TY - GEN

T1 - Finding induced subgraphs in scale-free inhomogeneous random graphs

AU - Cardinaels, Ellen

AU - Leeuwaarden, Johan S. H. van

AU - Stegehuis, Clara

PY - 2018/5/30

Y1 - 2018/5/30

N2 - We study the induced subgraph isomorphism problem on inhomogeneous random graphs with infinite variance power-law degrees. We provide a fast algorithm that determines for any connected graph $H$ on $k$ vertices if it exists as induced subgraph in a random graph with $n$ vertices. By exploiting the scale-free graph structure, the algorithm runs in $O(n k)$ time for small values of $k$. We test our algorithm on several real-world data sets.

AB - We study the induced subgraph isomorphism problem on inhomogeneous random graphs with infinite variance power-law degrees. We provide a fast algorithm that determines for any connected graph $H$ on $k$ vertices if it exists as induced subgraph in a random graph with $n$ vertices. By exploiting the scale-free graph structure, the algorithm runs in $O(n k)$ time for small values of $k$. We test our algorithm on several real-world data sets.

KW - cs.DS

KW - math.CO

U2 - 10.1007/978-3-319-92871-5_1

DO - 10.1007/978-3-319-92871-5_1

M3 - Conference contribution

SN - 978-3-319-92870-8

SP - 1

EP - 15

BT - Algorithms and Models for the Web Graph

A2 - Bonato, Anthony

A2 - Pralat, Pawel

A2 - Raigorodskii, Andrei

PB - Springer

T2 - International Workshop on Algorithms and Models for the Web-Graph 2018

Y2 - 17 May 2018 through 18 May 2018

ER -

Finding induced subgraphs in scale-free inhomogeneous random graphs

Abstract

Workshop

Keywords

Access to Document

Fingerprint

Cite this