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

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

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(nk) 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	A. Bonato, P. Pralat, A. Raigorodskii
Place of Publication	Dordrecht
Publisher	Springer
Pages	1-15
Number of pages	15
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 - 1 Jan 2018
Event	15th Workshop on Algorithms and Models for the Web Graph, WAW 2018 - Moscow, Russian Federation Duration: 17 May 2018 → 18 May 2018

Publication series

Name	Lecture Notes in Computer Science
Volume	10836
ISSN (Print)	0302-9743
ISSN (Electronic)	1611-3349

Conference

Conference	15th Workshop on Algorithms and Models for the Web Graph, WAW 2018
Country/Territory	Russian Federation
City	Moscow
Period	17/05/18 → 18/05/18

Access to Document

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

Cite this

Cardinaels, E., van Leeuwaarden, J. S. H., & 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). (Lecture Notes in Computer Science; Vol. 10836). Springer. https://doi.org/10.1007/978-3-319-92871-5_1

Cardinaels, Ellen ; van Leeuwaarden, Johan S.H. ; Stegehuis, Clara. / Finding induced subgraphs in scale-free inhomogeneous random graphs. Algorithms and Models for the Web Graph: 15th International Workshop, WAW 2018, Moscow, Russia, May 17-18, 2018, Proceedings. editor / A. Bonato ; P. Pralat ; A. Raigorodskii. Dordrecht : Springer, 2018. pp. 1-15 (Lecture Notes in Computer Science).

@inproceedings{feb87fe50f7c4c5196dddc1d37d779f1,

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(nk) time for small values of k. We test our algorithm on several real-world data sets.",

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

year = "2018",

month = jan,

day = "1",

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

language = "English",

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

series = "Lecture Notes in Computer Science",

publisher = "Springer",

pages = "1--15",

editor = "A. Bonato and P. Pralat and A. Raigorodskii",

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

address = "Germany",

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

}

Cardinaels, E , van Leeuwaarden, JSH & 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. Lecture Notes in Computer Science, vol. 10836, Springer, Dordrecht, pp. 1-15, 15th Workshop on Algorithms and Models for the Web Graph, WAW 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 ; van Leeuwaarden, Johan S.H.; Stegehuis, Clara.
Algorithms and Models for the Web Graph: 15th International Workshop, WAW 2018, Moscow, Russia, May 17-18, 2018, Proceedings. ed. / A. Bonato; P. Pralat; A. Raigorodskii. Dordrecht: Springer, 2018. p. 1-15 (Lecture Notes in Computer Science; Vol. 10836).

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 - van Leeuwaarden, Johan S.H.

AU - Stegehuis, Clara

PY - 2018/1/1

Y1 - 2018/1/1

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(nk) 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(nk) time for small values of k. We test our algorithm on several real-world data sets.

UR - http://www.scopus.com/inward/record.url?scp=85048226583&partnerID=8YFLogxK

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

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

M3 - Conference contribution

AN - SCOPUS:85048226583

SN - 978-3-319-92870-8

T3 - Lecture Notes in Computer Science

SP - 1

EP - 15

BT - Algorithms and Models for the Web Graph

A2 - Bonato, A.

A2 - Pralat, P.

A2 - Raigorodskii, A.

PB - Springer

CY - Dordrecht

T2 - 15th Workshop on Algorithms and Models for the Web Graph, WAW 2018

Y2 - 17 May 2018 through 18 May 2018

ER -

Cardinaels E , van Leeuwaarden JSH, Stegehuis C. Finding induced subgraphs in scale-free inhomogeneous random graphs. In Bonato A, Pralat P, Raigorodskii A, editors, Algorithms and Models for the Web Graph: 15th International Workshop, WAW 2018, Moscow, Russia, May 17-18, 2018, Proceedings. Dordrecht: Springer. 2018. p. 1-15. (Lecture Notes in Computer Science). doi: 10.1007/978-3-319-92871-5_1

Finding induced subgraphs in scale-free inhomogeneous random graphs

Abstract

Publication series

Conference

Access to Document

Other files and links

Fingerprint

Cite this