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
The VLDB Journal
Erschienen in: The VLDB Journal 3/2023

20.09.2022 | Regular Paper

Toward maintenance of hypercores in large-scale dynamic hypergraphs

Erschienen in: The VLDB Journal | Ausgabe 3/2023

Einloggen

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

search-config
loading …

Abstract

In this paper, we study hypercore maintenance in large-scale dynamic hypergraphs. A hypergraph, whose hyperedges may contain a set of vertices rather than two vertices in pairwise graphs, can represent complex interactions in more sophisticated applications. However, the exponential number of hyperedges incurs unaffordable costs to recompute the hypercore number of vertices and hyperedges when updating a hypergraph. This motivates us to propose an efficient approach for exact hypercore maintenance with the intention of significantly reducing the hypercore updating time comparing with recomputation approaches. The proposed algorithms can pinpoint the vertices and hyperedges whose hypercore numbers have to be updated by only traversing a small sub-hypergraph. We also propose an index called Core-Index that can facilitate our maintenance algorithms. Extensive experiments on real-world and temporal hypergraphs demonstrate the superiority of our algorithms in terms of efficiency.
Vorheriger Artikel Learning-based query optimization for multi-probe approximate nearest neighbor search
Nächster Artikel PARROT: pattern-based correlation exploitation in big partitioned data series

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
Fußnoten
Literatur
1.
Abello, J., Resende, M.G.C., Sudarsky, S.: Massive quasi-clique detection. In: 5th Latin American Symposium of Theoretical Informatics Proceedings. LATIN, Lecture Notes in Computer Science, vol. 2286, pp. 598–612. Springer, Cancun, Mexico (2002)
2.
Alvarez-Hamelin, J.I., Dall’Asta, L., Barrat, A., Vespignani, A.: Large scale networks fingerprinting and visualization using the k-core decomposition. In: Neural Information Processing Systems, pp. 41–50. (2005)
3.
4.
Arya, D., Worring, M.: Exploiting relational information in social networks using geometric deep learning on hypergraphs. In: Proceedings of the International Conference on Multimedia Retrieval, ICMR, pp. 117–125. ACM (2018)
5.
Batagelj, V., Zaversnik, M.: An o(m) algorithm for cores decomposition of networks. CoRR cs.DS/0310049 (2003)
6.
Benson, A.R., Abebe, R., Schaub, M.T., Jadbabaie, A., Kleinberg, J.M.: Simplicial closure and higher-order link prediction. Proc. Natl. Acad. Sci. USA 115(48), E11221–E11230 (2018)CrossRef
7.
Bu, J., Tan, S., Chen, C., Wang, C., Wu, H., Zhang, L., He, X.: Music recommendation by unified hypergraph: combining social media information and music content. In: Proceedings of the 18th International Conference on Multimedia, pp. 391–400. ACM (2010)
8.
Chang, L., Qin, L.: Cohesive subgraph computation over large sparse graphs. In: 35th IEEE International Conference on Data Engineering, ICDE, pp. 2068–2071. IEEE (2019)
9.
Chang, L., Yu, J.X., Qin, L., Lin, X., Liu, C., Liang, W.: Efficiently computing k-edge connected components via graph decomposition. In: Proceedings of the ACM SIGMOD International Conference on Management of Data, pp. 205–216. ACM (2013). https://​doi.​org/​10.​1145/​2463676.​2465323
10.
Chen, J., Saad, Y.: Dense subgraph extraction with application to community detection. IEEE Trans. Knowl. Data Eng. 24(7), 1216–1230 (2012)CrossRef
11.
12.
13.
Cheng, J., Ke, Y., Chu, S., Özsu, M.T.: Efficient core decomposition in massive networks. In: Proceedings of the 27th International Conference on Data Engineering, ICDE, pp. 51–62. (2011)
14.
Chlamtáč, E., Dinitz, M., Konrad, C., Kortsarz, G., Rabanca, G.: The densest k-subhypergraph problem. SIAM J. Discrete Math. 32(2), 1458–1477 (2018)MathSciNetCrossRefMATH
15.
Chodrow, P.S., Mellor, A.: Annotated hypergraphs: models and applications. Appl. Netw. Sci. 5, 9 (2020)CrossRef
16.
Cohen, J.: Trusses: cohesive subgraphs for social network analysis. Natl. Secur. Agency Techn. Rep. 16, 3–29 (2008)
17.
18.
Das, A., Svendsen, M., Tirthapura, S.: Incremental maintenance of maximal cliques in a dynamic graph. VLDB J. 28(3), 351–375 (2019)CrossRef
19.
Do, M.T., Yoon, S., Hooi, B., Shin, K.: Structural patterns and generative models of real-world hypergraphs. In: KDD ’20: The 26th ACM SIGKDD Conference on Knowledge Discovery and Data Mining, pp. 176–186. ACM (2020)
20.
Fang, Y., Yu, K., Cheng, R., Lakshmanan, L.V.S., Lin, X.: Efficient algorithms for densest subgraph discovery. Proc. VLDB Endow. 12(11), 1719–1732 (2019)CrossRef
21.
Fatemi, B., Taslakian, P., Vázquez, D., Poole, D.: Knowledge hypergraphs: extending knowledge graphs beyond binary relations. CoRR abs/1906.00137 (2019)
22.
Feng, Y., You, H., Zhang, Z., Ji, R., Gao, Y.: Hypergraph neural networks. In: The Thirty-First Innovative Applications of Artificial Intelligence Conference, pp. 3558–3565. AAAI Press (2019)
23.
24.
Gabert, K., Pinar, A., Çatalyürek, Ü.V.: A unifying framework to identify dense subgraphs on streams: graph nuclei to hypergraph cores. In: WSDM ’21, The Fourteenth ACM International Conference on Web Search and Data Mining, pp. 689–697. ACM (2021). https://​doi.​org/​10.​1145/​3437963.​3441790
25.
Gabert, K., Pinar, A., Çatalyürek, Ü.V.: A unifying framework to identify dense subgraphs on streams: graph nuclei to hypergraph cores. In: WSDM ’21, The Fourteenth ACM International Conference on Web Search and Data Mining, pp. 689–697. ACM (2021). https://​doi.​org/​10.​1145/​3437963.​3441790
26.
Gionis, A., Tsourakakis, C.E.: Dense subgraph discovery: KDD 2015 tutorial. In: Proceedings of the 21th ACM SIGKDD International Conference on Knowledge Discovery and Data Mining, pp. 2313–2314. ACM (2015)
27.
Hu, S., Wu, X., Chan, T.H.: Maintaining densest subsets efficiently in evolving hypergraphs. In: Proceedings of Conference on Information and Knowledge Management, CIKM, pp. 929–938. ACM (2017)
28.
Hua, Q., Shi, Y., Yu, D., Jin, H., Yu, J., Cai, Z., Cheng, X., Chen, H.: Faster parallel core maintenance algorithms in dynamic graphs. IEEE Trans. Parallel Distrib. Syst. 31(6), 1287–1300 (2020)CrossRef
29.
Huang, J., Zhang, R., Yu, J.X.: Scalable hypergraph learning and processing. In: 2015 IEEE International Conference on Data Mining, ICDM, pp. 775–780. IEEE Computer Society (2015)
30.
31.
Hwang, T., Tian, Z., Kuang, R., Kocher, J.A.: Learning on weighted hypergraphs to integrate protein interactions and gene expressions for cancer outcome prediction. In: Proceedings of the 8th IEEE International Conference on Data Mining ICDM, pp. 293–302. (2008)
32.
Jiang, J., Mitzenmacher, M., Thaler, J.: Parallel peeling algorithms. ACM Trans. Parallel Comput. 3(1), 7:1-7:27 (2016)CrossRef
33.
Jin, H., Wang, N., Yu, D., Hua, Q., Shi, X., Xie, X.: Core maintenance in dynamic graphs: a parallel approach based on matching. IEEE Trans. Parallel Distrib. Syst. 29(11), 2416–2428 (2018)CrossRef
34.
Karypis, G., Aggarwal, R., Kumar, V., Shekhar, S.: Multilevel hypergraph partitioning: applications in VLSI domain. IEEE Trans. Very Large Scale Integr. Syst. 7(1), 69–79 (1999)CrossRef
35.
36.
Leng, M., Sun, L.: Comparative experiment of the core property of weighted hyper-graph based on the ispd98 benchmark. J. Inf. Comput. 10(8), 2279–2290 (2013)CrossRef
37.
Leng, M., Sun, L., Bian, J., Ma, Y.: An \(o(m)\) algorithm for cores decomposition of undirected hypergraph. J. Chin. Comput. Syst. 34(11), 2568–2573 (2013)
38.
Li, D., Xu, Z., Li, S., Sun, X.: Link prediction in social networks based on hypergraph. In: 22nd International World Wide Web Conference, WWW Companion Volume, pp. 41–42. International World Wide Web Conferences Steering Committee/ACM (2013)
39.
Li, J., He, J., Zhu, Y.: E-tail product return prediction via hypergraph-based local graph cut. In: Y. Guo, F. Farooq (eds.) Proceedings of the 24th ACM International Conference on Knowledge Discovery & Data Mining, KDD, pp. 519–527. ACM (2018)
40.
41.
Lin, J.H., Guo, Q., Dong, W., ying Tang, L., Liu, J.: Identifying the node spreading influence with largest k-core values. Phys. Lett. A 378, 3279–3284 (2014)CrossRefMATH
42.
Liu, Q., Huang, Y., Metaxas, D.N.: Hypergraph with sampling for image retrieval. Pattern Recogn. 44(10–11), 2255–2262 (2011)CrossRefMATH
43.
Luo, Q., Yu, D., Cai, Z., Lin, X., Cheng, X.: Hypercore maintenance in dynamic hypergraphs. In: International Conference on Data Engineering, pp. 2051–2056 (2021)
44.
45.
Luo, Q., Yu, D., Li, F., Dou, Z., Cai, Z., Yu, J., Cheng, X.: Distributed core decomposition in probabilistic graphs. In: 8th International Conference Computational Data and Social Networks Proceedings. Lecture Notes in Computer Science, vol. 11917, pp. 16–32. Springer, Ho Chi Minh City, Vietnam (2019)
46.
47.
Ouyang, M., Toulouse, M., Thulasiraman, K., Glover, F.W., Deogun, J.S.: Multilevel cooperative search for the circuit/hypergraphpartitioning problem. IEEE Trans. Comput. Aided Des. Integr. Circuits Syst. 21(6), 685–693 (2002)CrossRef
48.
49.
Sariyüce, A.E., Gedik, B., Jacques-Silva, G., Wu, K., Çatalyürek, Ü.V.: Incremental k-core decomposition: algorithms and evaluation. VLDB J. 25(3), 425–447 (2016)CrossRef
50.
Sariyüce, A.E., Seshadhri, C., Pinar, A., Çatalyürek, Ü.V.: Finding the hierarchy of dense subgraphs using nucleus decompositions. In: Proceedings of the 24th International Conference on World Wide Web, pp. 927–937. ACM (2015). https://​doi.​org/​10.​1145/​2736277.​2741640
51.
52.
53.
Shun, J.: Practical parallel hypergraph algorithms. In: PPoPP ’20: 25th ACM SIGPLAN Symposium on Principles and Practice of Parallel Programming, pp. 232–249. ACM (2020)
54.
Sun, B., Chan, T.H., Sozio, M.: Fully dynamic approximate k-core decomposition in hypergraphs. ACM Trans. Knowl. Discov. Data 14(4), 39:1-39:21 (2020)CrossRef
55.
Tan, H., Ngo, C., Wu, X.: Modeling video hyperlinks with hypergraph for web video reranking. In: Proceedings of the 16th International Conference on Multimedia, pp. 659–662. ACM (2008)
56.
Tan, S., Guan, Z., Cai, D., Qin, X., Bu, J., Chen, C.: Mapping users across networks by manifold alignment on hypergraph. In: Proceedings of the Twenty-Eighth AAAI Conference on Artificial Intelligence, pp. 159–165. AAAI Press (2014)
57.
Tsourakakis, C.E.: The k-clique densest subgraph problem. In: Proceedings of the 24th International Conference on World Wide Web, WWW, pp. 1122–1132. ACM (2015)
58.
Tsourakakis, C.E., Bonchi, F., Gionis, A., Gullo, F., Tsiarli, M.A.: Denser than the densest subgraph: extracting optimal quasi-cliques with quality guarantees. In: The 19th ACM SIGKDD International Conference on Knowledge Discovery and Data Mining, pp. 104–112. ACM (2013)
59.
60.
Wang, N., Yu, D., Jin, H., Qian, C., Xie, X., Hua, Q.: Parallel algorithm for core maintenance in dynamic graphs. In: K. Lee, L. Liu (eds.) 37th IEEE International Conference on Distributed Computing Systems, ICDCS, pp. 2366–2371. IEEE Computer Society (2017)
61.
Wen, D., Qin, L., Zhang, Y., Lin, X., Yu, J.X.: I/O efficient core graph decomposition at web scale. In: 32nd IEEE International Conference on Data Engineering, ICDE, pp. 133–144. (2016)
62.
Yang, D., Qu, B., Yang, J., Cudré-Mauroux, P.: Revisiting user mobility and social relationships in lbsns: A hypergraph embedding approach. In: The World Wide Web Conference, WWW, pp. 2147–2157. ACM (2019)
63.
64.
65.
Zhang, M., Cui, Z., Jiang, S., Chen, Y.: Beyond link prediction: Predicting hyperlinks in adjacency space. In: Proceedings of the Thirty-Second AAAI Conference on Artificial Intelligence, pp. 4430–4437. AAAI Press (2018)
66.
Zheng, X., Luo, Y., Sun, L., Ding, X., Zhang, J.: A novel social network hybrid recommender system based on hypergraph topologic structure. World Wide Web 21(4), 985–1013 (2018)CrossRef
67.
Zhou, D., Huang, J., Schölkopf, B.: Learning with hypergraphs: Clustering, classification, and embedding. In: Proceedings of the Twentieth Annual Conference on Neural Information Processing Systems, pp. 1601–1608. MIT Press (2006)
68.
Zhu, Y., Guan, Z., Tan, S., Liu, H., Cai, D., He, X.: Heterogeneous hypergraph embedding for document recommendation. Neurocomputing 216, 150–162 (2016)CrossRef
Metadaten
Titel
Toward maintenance of hypercores in large-scale dynamic hypergraphs
Publikationsdatum
20.09.2022
Erschienen in
The VLDB Journal / Ausgabe 3/2023
Print ISSN: 1066-8888
Elektronische ISSN: 0949-877X
DOI
https://doi.org/10.1007/s00778-022-00763-z

Weitere Artikel der Ausgabe 3/2023

The VLDB Journal 3/2023 Zur Ausgabe

Regular Paper

HERMES: data placement and schema optimization for enterprise knowledge bases

Regular Paper

PARROT: pattern-based correlation exploitation in big partitioned data series

Regular Paper

Multi-constraint shortest path using forest hop labeling

Regular Paper

Enhancing domain-aware multi-truth data fusion using copy-based source authority and value similarity

Regular Paper

Efficient kNN query for moving objects on time-dependent road networks

Regular Paper

Learning-based query optimization for multi-probe approximate nearest neighbor search