Skip to main content
Fachgebiete
Automobil + Motoren Bauwesen + Immobilien Business IT + Informatik Elektrotechnik + Elektronik Energie + Nachhaltigkeit Finance + Banking Management + Führung Marketing + Vertrieb Maschinenbau + Werkstoffe Versicherung + Risiko
DE
EN
Bücher
Zeitschriften
Themenseiten
Organisationspsychologie Projektmanagement Marketing Smart Manufacturing
Weitere Formate
Podcasts Webinare Technik Webinare Wirtschaft Kongresse Veranstaltungskalender Awards
Jetzt Einzelzugang starten
Zugang für Unternehmen
Referenzkunden
SLX-Digitalkonferenz: Zukunftswerkstatt 2024

Mehr Umsatz mit Top-Kontakten

Am 7. Mai erfahren Sie, wie Vertriebsteams Leadgenerierung, Leadnurturing und Leadstrategien effizient steuern können.
Erweiterte Suche
Anmelden
nach oben
Erschienen in:
Buchtitelbild

2018 | OriginalPaper | Buchkapitel

Finding Induced Subgraphs in Scale-Free Inhomogeneous Random Graphs

verfasst von : Ellen Cardinaels, Johan S. H. van Leeuwaarden, Clara Stegehuis

Erschienen in: Algorithms and Models for the Web Graph

Verlag: Springer International Publishing

Einloggen

Aktivieren Sie unsere intelligente Suche, um passende Fachinhalte oder Patente zu finden.

search-config
loading …

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.

Sie haben noch keine Lizenz? Dann Informieren Sie sich jetzt über unsere Produkte:

Springer Professional "Wirtschaft+Technik"

Online-Abonnement

Mit Springer Professional "Wirtschaft+Technik" erhalten Sie Zugriff auf:

  • über 102.000 Bücher
  • über 537 Zeitschriften

aus folgenden Fachgebieten:

  • Automobil + Motoren
  • Bauwesen + Immobilien
  • Business IT + Informatik
  • Elektrotechnik + Elektronik
  • Energie + Nachhaltigkeit
  • Finance + Banking
  • Management + Führung
  • Marketing + Vertrieb
  • Maschinenbau + Werkstoffe
  • Versicherung + Risiko

Jetzt Wissensvorsprung sichern!

Jetzt informieren

Springer Professional "Technik"

Online-Abonnement

Mit Springer Professional "Technik" erhalten Sie Zugriff auf:

  • über 67.000 Bücher
  • über 390 Zeitschriften

aus folgenden Fachgebieten:

  • Automobil + Motoren
  • Bauwesen + Immobilien
  • Business IT + Informatik
  • Elektrotechnik + Elektronik
  • Energie + Nachhaltigkeit
  • Maschinenbau + Werkstoffe




 

Jetzt Wissensvorsprung sichern!

Jetzt informieren

Springer Professional "Wirtschaft"

Online-Abonnement

Mit Springer Professional "Wirtschaft" erhalten Sie Zugriff auf:

  • über 67.000 Bücher
  • über 340 Zeitschriften

aus folgenden Fachgebieten:

  • Bauwesen + Immobilien
  • Business IT + Informatik
  • Finance + Banking
  • Management + Führung
  • Marketing + Vertrieb
  • Versicherung + Risiko




Jetzt Wissensvorsprung sichern!

Jetzt informieren
Nächstes Kapitel The Asymptotic Normality of the Global Clustering Coefficient in Sparse Random Intersection Graphs
Literatur
1.
Albert, R., Jeong, H., Barabási, A.L.: Internet: diameter of the world-wide web. Nature 401(6749), 130–131 (1999)CrossRef
2.
Boguñá, M., Pastor-Satorras, R.: Class of correlated random networks with hidden variables. Phys. Rev. E 68, 036112 (2003)CrossRef
3.
Bollobás, B., Janson, S., Riordan, O.: The phase transition in inhomogeneous random graphs. Random Struct. Algorithms 31(1), 3–122 (2007)MathSciNetCrossRef
4.
Brach, P., Cygan, M., Łacki, J., Sankowski, P.: Algorithmic complexity of power law networks. In: Proceedings of the Twenty-Seventh Annual ACM-SIAM Symposium on Discrete Algorithms, SODA 2016, pp. 1306–1325. Society for Industrial and Applied Mathematics, Philadelphia (2016)
5.
Britton, T., Deijfen, M., Martin-Löf, A.: Generating simple random graphs with prescribed degree distribution. J. Stat. Phys. 124(6), 1377–1397 (2006)MathSciNetCrossRef
6.
Chung, F., Lu, L.: The average distances in random graphs with given expected degrees. Proc. Natl. Acad. Sci. USA 99(25), 15879–15882 (2002) (electronic)MathSciNetCrossRef
7.
Clauset, A., Shalizi, C.R., Newman, M.E.J.: Power-law distributions in empirical data. SIAM Rev. 51(4), 661–703 (2009)MathSciNetCrossRef
8.
Faloutsos, M., Faloutsos, P., Faloutsos, C.: On power-law relationships of the internet topology. ACM SIGCOMM Comput. Commun. Rev. 29, 251–262 (1999)CrossRef
9.
10.
Fountoulakis, N., Friedrich, T., Hermelin, D.: On the average-case complexity of parameterized clique. Theor. Comput. Sci. 576, 18–29 (2015)MathSciNetCrossRef
11.
Friedrich, T., Krohmer, A.: Cliques in hyperbolic random graphs. In: INFOCOM Proceedings 2015, pp. 1544–1552. IEEE (2015)
12.
Friedrich, T., Krohmer, A.: Parameterized clique on inhomogeneous random graphs. Disc. Appl. Math. 184, 130–138 (2015)MathSciNetCrossRef
13.
Garey, M.R., Johnson, D.S., Garey, M.R.: Computers and Intractability: A Guide to the Theory of NP-Completeness. W H FREEMAN & CO (2011)
14.
Grochow, J.A., Kellis, M.: Network motif discovery using subgraph enumeration and symmetry-breaking. In. RECOMB, pp. 92–106 (2007)
15.
Heydari, H., Taheri, S.M.: Distributed maximal independent set on inhomogeneous random graphs. In: 2017 2nd Conference on Swarm Intelligence and Evolutionary Computation (CSIEC). IEEE, March 2017
16.
van der Hofstad, R.: Random Graphs and Complex Networks, vol. 1. Cambridge University Press, Cambridge (2017)CrossRef
17.
van der Hofstad, R., van Leeuwaarden, J.S.H., Stegehuis, C.: Optimal subgraph structures in scale-free networks. arXiv:​1709.​03466 (2017)
18.
Janson, S., Łuczak, T., Norros, I.: Large cliques in a power-law random graph. J. Appl. Probab. 47(04), 1124–1135 (2010)MathSciNetCrossRef
19.
Jeong, H., Tombor, B., Albert, R., Oltvai, Z.N., Barabási, A.L.: The large-scale organization of metabolic networks. Nature 407(6804), 651–654 (2000)CrossRef
20.
21.
Kashtan, N., Itzkovitz, S., Milo, R., Alon, U.: Efficient sampling algorithm for estimating subgraph concentrations and detecting network motifs. Bioinformatics 20(11), 1746–1758 (2004)CrossRef
22.
23.
24.
Norros, I., Reittu, H.: On a conditionally poissonian graph process. Adv. Appl. Probab. 38(01), 59–75 (2006)MathSciNetCrossRef
25.
Omidi, S., Schreiber, F., Masoudi-Nejad, A.: MODA: an efficient algorithm for network motif discovery in biological networks. Genes Genetic Syst. 84(5), 385–395 (2009)CrossRef
26.
27.
Schreiber, F., Schwobbermeyer, H.: MAVisto: a tool for the exploration of network motifs. Bioinformatics 21(17), 3572–3574 (2005)CrossRef
28.
Vázquez, A., Pastor-Satorras, R., Vespignani, A.: Large-scale topological and dynamical properties of the internet. Phys. Rev. E 65, 066130 (2002)CrossRef
29.
Williams, V.V., Wang, J.R., Williams, R., Yu, H.: Finding four-node subgraphs in triangle time. In: Proceedings of the Twenty-Sixth Annual ACM-SIAM Symposium on Discrete Algorithms, SODA 2015, pp. 1671–1680. Society for Industrial and Applied Mathematics, Philadelphia (2015)
Metadaten
Titel
Finding Induced Subgraphs in Scale-Free Inhomogeneous Random Graphs
verfasst von
Ellen Cardinaels
Johan S. H. van Leeuwaarden
Clara Stegehuis
Copyright-Jahr
2018
Buch
Algorithms and Models for the Web Graph

Print ISBN: 978-3-319-92870-8

Electronic ISBN: 978-3-319-92871-5

Copyright-Jahr: 2018

DOI
https://doi.org/10.1007/978-3-319-92871-5_1