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
MTZ-Fachkongress

Antriebe und Energiesysteme von morgen


Austausch von Automobil- und Energiewirtschaft

Am 14./15. Mai geht es in Chemnitz um die Mobilitätswende durch Elektro- und Wasserstofffahrzeuge.
Erweiterte Suche
Anmelden
nach oben
Erschienen in:
Mapping Low-Resolution Edges to High-Resolution Paths: The Case of Traffic Measurements in Cities Kapitel lesen Erstes Kapitel lesen

2024 | OriginalPaper | Buchkapitel

Computing Motifs in Hypergraphs

verfasst von : Duarte Nóbrega, Pedro Ribeiro

Erschienen in: Complex Networks XV

Verlag: Springer Nature Switzerland

Einloggen

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

search-config
loading …

Abstract

Motifs are overrepresented and statistically significant sub-patterns in a network, whose identification is relevant to uncover its underlying functional units. Recently, its extraction has been performed on higher-order networks, but due to the complexity arising from polyadic interactions, and the similarity with known computationally hard problems, its practical application is limited. Our main contribution is a novel approach for hyper-subgraph census and higher-order motif discovery, allowing for motifs with sizes 3 or 4 to be found efficiently, in real-world scenarios. It is consistently an order of magnitude faster than a baseline state-of-art method, while using less memory and supporting a wider range of base algorithms.

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 Modeling Both Pairwise Interactions and Group Effects in Polarization on Interaction Networks
Nächstes Kapitel Extending Network Tools to Explore Trends in Temporal Granular Trade Networks
Fußnoten
1
All the hypergraph images were created using [8].
 
Literatur
1.
Aparicio, D., Paredes, P., Ribeiro, P.: A scalable parallel approach for subgraph census computation. In: Euro-Par 2014: Parallel Processing Workshops, Revised Selected Papers, pp. 194–205 (2014)
2.
Chen, L., Qu, X., Cao, M., Zhou, Y., Li, W., Liang, B., Li, W., He, W., Feng, C., Jia, X., He, Y.: Identification of breast cancer patients based on human signaling network motifs. Sci. Rep. 3(1), 1–7 (2013)CrossRef
3.
Chodrow, P.S.: Configuration models of random hypergraphs. J. Complex Netw. 8(3), cnaa018 (2020)
4.
Cook, S.A.: The complexity of theorem-proving procedures. In: Proceedings of the Third Annual ACM Symposium on Theory of Computing, STOC ’71, pp. 151–158 (1971)
5.
Dey, A.K., Gel, Y.R., Vincent Poor, H.: What network motifs tell us about resilience and reliability of complex networks. Proc. Natl. Acad. Sci. 116(39), 19368–19373 (2019)CrossRef
6.
Hong-Lin, X., Han-Bing, Y., Cui-Fang, G., Ping, Z.: Social network analysis based on network motifs. J. Appl. Math. 2014 (2014)
7.
Lee, G., Ko, J., Shin, K.: Hypergraph motifs: concepts, algorithms, and discoveries. Proc. VLDB Endowment 13(12), 2256–2269 (2020)CrossRef
8.
Lotito, Q.F., Contisciani, M., De Bacco, C., Di Gaetano, L., Gallo, L., Montresor, A., Musciotto, F., Ruggeri, N., Battiston, F.: Hypergraphx: a library for higher-order network analysis. J. Complex Netw. 11(3), cnad019 (2023)
9.
Lotito, Q.F., Musciotto, F., Battiston, F., Montresor, A.: Exact and sampling methods for mining higher-order motifs in large hypergraphs. Computing 1–20 (2023)
10.
Lotito, Q.F., Musciotto, F., Montresor, A., Battiston, F.: Higher-order motif analysis in hypergraphs. Commun. Phys. 5(1), 79 (2022)CrossRef
11.
12.
Milo, R., Shen-Orr, S., Itzkovitz, S., Kashtan, N., Chklovskii, D., Alon, U.: Network motifs: Simple building blocks of complex networks. Science 298(5594), 824–827 (2002)CrossRef
13.
Milo, R., Itzkovitz, S., Kashtan, N., Levitt, R., Shen-Orr, S., Ayzenshtat, I., Sheffer, M., Alon, U.: Superfamilies of evolved and designed networks. Science 303(5663), 1538–1542 (2004)CrossRef
14.
Molloy, M., Reed, B.: A critical point for random graphs with a given degree sequence. Random Struct. Algorithms 6(2–3), 161–180 (1995)MathSciNetCrossRef
15.
Nettleton, D.F.: Data mining of social networks represented as graphs. Comput. Sci. Rev. 7, 1–34 (2013)CrossRef
16.
Nordman, D.J., Berry, J.W., Phillips, C.A., Fostvedt, L.A., Wilson, A.G., Seshadhri, C.: Why do simple algorithms for triangle enumeration work in the real world? Internet Math. 11(6), 11 (2015)MathSciNet
17.
Paredes, P., Ribeiro, P.: Towards a faster network-centric subgraph census. In: 2013 IEEE/ACM International Conference on Advances in Social Networks Analysis and Mining (ASONAM 2013), pp. 264–271 (2013)
18.
Paredes, P., Ribeiro, P.: Rand-fase: fast approximate subgraph census. Soc. Netw. Anal. Min. 5(1), 17 (2015)CrossRef
19.
Ribeiro, P., Paredes, P., Silva, M.E., Aparicio, D., Silva, F.: A survey on subgraph counting: concepts, algorithms, and applications to network motifs and graphlets. ACM Comput. Surv. (CSUR) 54(2), 1–36 (2021)CrossRef
20.
Ribeiro, P., Silva, F.: G-tries: an efficient data structure for discovering network motifs. In: Proceedings of the 2010 ACM Symposium on Applied Computing, pp. 1559–1566 (2010)
21.
Washio, T., Motoda, H.: State of the art of graph-based data mining. ACM SIGKDD Explorat. Newsl 5(1), 59–68 (2003)CrossRef
22.
Wernicke, S.: Efficient detection of network motifs. IEEE/ACM Trans. Comput. Biol. Bioinf. 3(4), 347–359 (2006)CrossRef
Metadaten
Titel
Computing Motifs in Hypergraphs
verfasst von
Duarte Nóbrega
Pedro Ribeiro
Copyright-Jahr
2024
Buch
Complex Networks XV

Print ISBN: 978-3-031-57514-3

Electronic ISBN: 978-3-031-57515-0

Copyright-Jahr: 2024

DOI
https://doi.org/10.1007/978-3-031-57515-0_5

Premium Partner

    Bildnachweise