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
Themenseiten
Organisationspsychologie Projektmanagement Marketing Smart Manufacturing
Bücher
Zeitschriften
Weitere Formate
Podcasts Webinare Technik Webinare Wirtschaft Kongresse Veranstaltungskalender Awards
Jetzt Einzelzugang starten
Zugang für Unternehmen
Referenzkunden
ATZ-Fachkongress

Chassis.tech plus 2024


4 Kongresse in einer Veranstaltung

Treffen Sie in München die Fachleute von Chassis, Lenkung, Bremsen sowie Reifen/Räder.
Erweiterte Suche
Anmelden
nach oben
Erschienen in:
Modularity of the ABCD Random Graph Model with Community Structure Kapitel lesen Erstes Kapitel lesen

2023 | OriginalPaper | Buchkapitel

DC-RST: A Parallel Algorithm for Random Spanning Trees in Network Analytics

verfasst von : Lucas Henke, Dinesh Mehta

Erschienen in: Complex Networks and Their Applications XI

Verlag: Springer International Publishing

Einloggen

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

search-config
loading …

Abstract

The Mantel Test, discovered in the 1960s, determines whether two distance metrics on a graph are related. We describe DC-RST, an algorithm to accelerate a key step of a network science statistical computation associated with DimeCost, an approach that is faster the Mantel Test. DC-RST is a parallel, divide-and-conquer algorithm to compute a random spanning tree of a complete graph on n vertices. Relative to an implementation of Wilson’s sequential random-walk algorithm, on a system with 48 cores, DC-RST was up to 4X faster when first creating random partitions and up to 20X faster without this sub-step. DC-RST is shown to be a suitable replacement for Wilson’s sequential algorithm through a combination of theoretical and statistical results.

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
Vorheriges Kapitel A More Powerful Heuristic for Balancing an Unbalanced Graph
Nächstes Kapitel A Stochastic Approach for Extracting Community-Based Backbones
Fußnoten
1
Note: distance metrics are assumed to be symmetric.
 
2
The \(L_p\)-norm for \(p \ge 1\) of a vector \(\vec {x}\) is a commonly used measure of “distance” in machine learning for clustering, and is defined by \(||\vec {x}||_p = (|x_1|^p + |x_2|^p + \cdots + |x_n|^p)^\frac{1}{p}\). Note that \(L_\infty (\vec {x}) = \max \{|x_1|, |x_2|, ..., |x_n| \}\) is the limit of the \(L_p\) norm as \(p \longrightarrow \infty \).
 
Literatur
1.
Mantel, N.: The detection of disease clustering and a generalized regression approach. Cancer Res. 27 (1967)
2.
Bourbour, S., Mehta, D.P., Navidi, W.C.: Improved methods to compare distance metrics in networks using uniform random spanning trees (dimecost). Networks 76 (2020)
3.
Anari, N., Hu, N., Saberi, A., Schild, A.: Sampling arborescences in parallel. In: Innovations in Theoretical Computer Science (2021)
4.
Dray, S., Dufour, A.-B.: The ade4 package: implementing the duality diagram for ecologists. J. Stat. Softw. 22(4), 1–20 (2007)CrossRef
5.
Schneider, J.W., Borlund, P.: Matrix comparison, part 2: measuring the resemblance between proximity measures or ordination results by use of the mantel and Procrustes statistics. J. Am. Soc. Inf. Sci. Technol. 58 (2007)
6.
Sokal, R.R., Rohlf, F.J.: The comparison of dendrograms by objective methods. TAXON 11 (1962)
7.
Corliss, J.O., Sneath, P.H.A., Sokal, R.R.: Numerical taxonomy: the principles and practice of numerical classification. Trans. Am. Microsc. Soc. 93 (1974)
8.
Cooper-Ellis, S., Pielou, E.C.: The interpretation of ecological data. A primer on classification and ordination. Bryologist 97 (1994)
9.
Ricaut, F.X., Auriol, V., Cramon-Taubadel, N.V., Keyser, C., Murail, P., Ludes, B., Crubézy, E.: Comparison between morphological and genetic data to estimate biological relationship: the case of the Egyin Gol necropolis (Mongolia). Am. J. Phys. Anthropol. 143 (2010)
10.
Smouse, P.E., Long, J.C., Sokal, R.R.: Multiple regression and correlation extensions of the mantel test of matrix correspondence. Syst. Zool. 35 (1986)
11.
Kouri, T.M., Awale, M., Slyby, J.K., Reymond, J.L., Mehta, D.P.: “Social” network of isomers based on bond count distance: algorithms. J. Chem. Inf. Model. 54 (2014)
12.
Aldous, D.J.: The random walk construction of uniform spanning trees and uniform labelled trees. SIAM J. Discr. Math. 3 (1990)
13.
Broder, A.: Generating random spanning trees (1989)
14.
Lovász, L.: Random walks on graphs: a survey. Combinatorics 2 (1993)
15.
Wilson, D.B.: Generating Random Spanning Trees More Quickly Than the Cover Time, vol. Part F129452 (1996)
16.
Bacher, A., Bodini, O., Hollender, A., Lumbroso, J.: Mergeshuffle: A Very Fast, Parallel Random Permutation Algorithm, vol. 2113 (2018)
Metadaten
Titel
DC-RST: A Parallel Algorithm for Random Spanning Trees in Network Analytics
verfasst von
Lucas Henke
Dinesh Mehta
Copyright-Jahr
2023
Buch
Complex Networks and Their Applications XI

Print ISBN: 978-3-031-21130-0

Electronic ISBN: 978-3-031-21131-7

Copyright-Jahr: 2023

DOI
https://doi.org/10.1007/978-3-031-21131-7_4

Premium Partner

    Bildnachweise