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 proceedingConference contributionAcademicpeer-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 languageEnglish
Title of host publicationAlgorithms and Models for the Web Graph
Subtitle of host publication15th International Workshop, WAW 2018, Moscow, Russia, May 17-18, 2018, Proceedings
EditorsA. Bonato, P. Pralat, A. Raigorodskii
Place of PublicationDordrecht
PublisherSpringer
Pages1-15
Number of pages15
ISBN (Electronic)978-3-319-92871-5
ISBN (Print)978-3-319-92870-8
DOIs
Publication statusPublished - 1 Jan 2018
Event15th Workshop on Algorithms and Models for the Web Graph, WAW 2018 - Moscow, Russian Federation
Duration: 17 May 201818 May 2018

Publication series

NameLecture Notes in Computer Science
Volume10836
ISSN (Print)0302-9743
ISSN (Electronic)1611-3349

Conference

Conference15th Workshop on Algorithms and Models for the Web Graph, WAW 2018
CountryRussian Federation
CityMoscow
Period17/05/1818/05/18

Fingerprint

Induced Subgraph
Random Graphs
Infinite Variance
Isomorphism Problem
Fast Algorithm
Connected graph
Power Law
Graph in graph theory

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). Dordrecht: 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 = "1",
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",

}

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 proceedingConference contributionAcademicpeer-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

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). https://doi.org/10.1007/978-3-319-92871-5_1