Top

Data Mining and Knowledge Discovery

Published in:

09-08-2023

Improving the core resilience of real-world hypergraphs

Authors: Manh Tuan Do, Kijung Shin

Published in: Data Mining and Knowledge Discovery | Issue 6/2023

Activate our intelligent search to find suitable subject content or patents.

search-config

AI-assisted search

Off

Abstract

Interactions that involve a group of people or objects are omnipresent in practice. Some examples include the list of recipients of an email, the group of co-authors of a publication, and the users participating in online discussion threads. These interactions are modeled as hypergraphs in which each hyperedge is a set of nodes constituting an interaction. In a hypergraph, the k-core is the sub-hypergraph within which the degree of each node is at least k. Investigating the k-core structures is valuable in revealing some properties of the hypergraph, one of which is the network behavior when facing attacks. Networks in practice are often prone to attacks by which the attacker removes a portion of the nodes or hyperedges to weaken some properties of the networks. The resilience of the k-cores is an indicator of the robustness of the network against such attacks. In this work, we investigate the core resilience of real-world hypergraphs against deletion attacks. How robust are the core structures of real-world hypergraphs in these attack scenarios? Given the complexity of a real-world hypergraph, how should we supplement the hypergraph with augmented hyperedges to enhance its core resilience? In light of several empirical observations regarding core resilience, we present a two-step method that preserves and strengthens the core structures of the hypergraphs.

previous article Hypercore decomposition for non-fragile hyperedges: concepts, algorithms, observations, and applications

next article i-Align: an interpretable knowledge graph alignment model

Dont have a licence yet? Then find out more about our products and how to get one now:

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!

inform now

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!

inform now

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!

inform now

Available only for authorised users

https://askubuntu.com

In this study, for the sake of simplicity, we choose to exclude self-loops (i.e., hyperedges of size 1) as they are not significantly relevant to robustness.

Identical rank values are each assigned the fractional rank equal to the average of their positions in the ascending order of the rank values.

The nodes having no incident hyperedges left are assigned core number 0 in this case.

Akoglu L, Faloutsos C (2013) Anomaly, event, and fraud detection in large network datasets. In: Proceedings of the 6th ACM international conference on web search and data mining (WSDM), pp 773–774, https://doi.org/10.1145/2433396.2433496

Amburg I, Veldt N, Benson A (2020) Clustering in graphs and hypergraphs with categorical edge labels. In: Proceedings of the web conference 2020 (WWW), pp 706–717. https://doi.org/10.1145/3366423.3380152

Aridhi S, Brugnara M, Montresor A, et al (2016) Distributed k-core decomposition and maintenance in large dynamic graphs. In: Proceedings of the 10th ACM international conference on distributed and event-based systems (DEBS), pp 161–168. https://doi.org/10.1145/2933267.2933299

de Arruda GF, Petri G, Moreno Y (2020) Social contagion models on hypergraphs. Phys Rev Res 2(2):023,032. https://doi.org/10.1103/PhysRevResearch.2.023032

Benson AR, Abebe R, Schaub MT, et al (2018a) Simplicial closure and higher-order link prediction. Proc Natl Acad Sci 115(48):E11,221–E11,230. https://doi.org/10.1073/pnas.1800683115doi:

Benson AR, Kumar R, Tomkins A (2018b) Sequences of sets. In: Proceedings of the 24th ACM SIGKDD international conference on knowledge discovery and data mining (KDD), pp 1148–1157. https://doi.org/10.1145/3219819.3220100

Bhawalkar K, Kleinberg J, Lewi K et al (2015) Preventing unraveling in social networks: the anchored k-core problem. SIAM J Discret Math 29(3):1452–1475. https://doi.org/10.1137/14097032XMathSciNetCrossRefMATH

Chen C, Zhu Q, Sun R et al (2021) Edge manipulation approaches for k-core minimization: metrics and analytics. IEEE Trans Knowl Data Eng 32(1):390–403. https://doi.org/10.1109/TKDE.2021.3085570CrossRef

Chien E, Pan C, Peng J, et al (2022) You are AllSet: a multiset function framework for hypergraph neural networks. In: Proceedings of the 10th international conference on learning representations (ICLR). https://doi.org/10.48550/arXiv.2106.13264

Do MT, Yoon Se, Hooi B, et al (2020) Structural Patterns and Generative Models of Real-world Hypergraphs. In: Proceedings of the 26th ACM SIGKDD International Conference on Knowledge Discovery and Data Mining (KDD), pp 176–186. https://doi.org/10.1145/3394486.3403060

Feng Y, You H, Zhang Z, et al (2019) Hypergraph Neural Networks. In: Proceedings of the 33rd AAAI Conference on Artificial Intelligence (AAAI), pp 3558–3565. https://doi.org/10.1609/aaai.v33i01.33013558

Freitas S, Yang D, Kumar S, et al (2022) Graph vulnerability and robustness: A survey. IEEE Transactions on Knowledge and Data Engineering pp 5915–5934. https://doi.org/10.1109/TKDE.2022.3163672doi:

Gabert K, Pinar A, Çatalyürek ÜV (2021a) Shared-memory scalable k-core maintenance on dynamic graphs and hypergraphs. In: Proceedings of the 2021 IEEE international parallel and distributed processing symposium workshops (IPDPSW), IEEE, pp 998–1007. https://doi.org/10.1109/IPDPSW52791.2021.00158

Gabert K, Pinar A, Çatalyürek ÜV (2021b) A unifying framework to identify dense subgraphs on streams: graph nuclei to hypergraph cores. In: Proceedings of the 14th ACM international conference on web search and data mining (WSDM), pp 689–697. https://doi.org/10.1145/3437963.3441790

Giatsidis C, Thilikos DM, Vazirgiannis M (2011) Evaluating cooperation in communities with the k-Core Structure. In: Proceedings of the 2021 international conference on advances in social networks analysis and mining (ASONAM), pp 87–93. https://doi.org/10.1109/ASONAM.2011.65

Giroire F, Nisse N, Trolliet T et al (2022) Preferential attachment hypergraph with high modularity. Network Science 10(4):400–429. https://doi.org/10.1017/nws.2022.35CrossRef

Huang Z, Chung W, Ong TH, et al (2002) A Graph-Based Recommender System for Digital Library. In: Proceedings of the 2nd ACM/IEEE-CS Joint Conference on Digital Libraries (JCDL), pp 65–73. https://doi.org/10.1145/544220.544231

Hwang H, Lee S, Park C, et al (2022) AHP: Learning to Negative Sample for Hyperedge Prediction. In: Proceedings of the 45th International ACM SIGIR conference on research and development in information retrieval (SIGIR), pp 2237–2242. https://doi.org/10.1145/3477495.3531836

Iacopini I, Petri G, Barrat A et al (2019) Simplicial models of social contagion. Nat Commun 10(1):1–9. https://doi.org/10.1038/s41467-019-10431-6CrossRef

Kim S, Choe M, Yoo J, et al (2022) Reciprocity in directed hypergraphs: measures, findings, and generators. In: Proceedings of the 2022 IEEE international conference on data mining (ICDM), pp 1005–1010, https://doi.org/10.1109/ICDM54844.2022.00122

Kim S, Bu F, Choe M, et al (2023) How transitive are real-world group interactions?–Measurement and reproduction. arXiv preprint arXiv:2306.02358

Kitsak M, Gallos LK, Havlin S et al (2010) Identification of influential spreaders in complex networks. Nat Phys 6(11):888–893. https://doi.org/10.1038/nphys1746CrossRef

Klimt B, Yang Y (2004) The enron corpus: a new dataset for email classification research. In: Proceedings of the 15th European conference on machine learning (ECML), Springer, pp 217–226, https://doi.org/10.1007/978-3-540-30115-8_22

Kook Y, Ko J, Shin K (2020) Evolution of real-world hypergraphs: patterns and models without oracles. In: Proceedings of the 2020 IEEE international conference on data mining (ICDM), https://doi.org/10.1109/ICDM50108.2020.00036

Kumar T, Darwin K, Parthasarathy S, et al (2020) PHPRA: hyperedge prediction using resource allocation. In: Proceedings of the 12th ACM conference on web science, pp 135–143, https://doi.org/10.1145/3394231.3397903

Laishram R (2020) The resilience of k-cores in graphs. PhD thesis, Syracuse University

Laishram R, Sariyüce A, Eliassi-Rad T, et al (2018) Measuring and Improving the Core Resilience of Networks. In: Proceedings of the web conference 2018 (WWW), pp 609–618, https://doi.org/10.1145/3178876.3186127

Laishram R, Erdem Sar A, Eliassi-Rad T, et al (2020) Residual core maximization: an efficient algorithm for maximizing the size of the k-core. In: Proceedings of the 2020 SIAM international conference on data mining (SDM), pp 325–333. https://doi.org/10.1137/1.9781611976236.37

Lee G, Ko J, Shin K (2020) Hypergraph motifs: concepts, algorithms, and discoveries. Proc VLDB Endow 13(11):2256–2269. https://doi.org/10.14778/3407790.3407823CrossRef

Lee G, Choe M, Shin K (2021) How do hyperedges overlap in real-world hypergraphs?-Patterns, measures, and generators. In: Proceedings of the web conference 2021 (WWW), pp 3396–3407. https://doi.org/10.1145/3442381.3450010

Lei S, Maniu S, Mo L, et al (2015) Online influence maximization. In: Proceedings of the 21th ACM SIGKDD international conference on knowledge discovery and data mining (KDD), pp 645–654. https://doi.org/10.1145/2783258.2783271

Leng M, Sun L, Jn Bian et al (2013) An O(m) algorithm for cores decomposition of undirected hypergraph. J Chin Comput Syst 34(11):2568–2573

Li P, Milenkovic O (2017) Inhomogeneous hypergraph clustering with applications. In: Proceedings of the 31st international conference on neural information processing systems, pp 2305–2315. https://doi.org/10.48550/arXiv.1709.01249s

Li RH, Yu JX, Mao R (2013) Efficient core maintenance in large dynamic graphs. IEEE Trans Knowl Data Eng 26(10):2453–2465. https://doi.org/10.1109/TKDE.2013.158CrossRef

Lin Z, Zhang F, Lin X et al (2021) Hierarchical core maintenance on large dynamic graphs. Proc VLDB Endow 14(5):757–770. https://doi.org/10.14778/3446095.3446099CrossRef

Linghu Q, Zhang F, Lin X, et al (2020) Global reinforcement of social networks: the anchored coreness problem. In: Proceedings of the 2020 ACM SIGMOD international conference on management of data (SIGMOD), pp 2211–2226. https://doi.org/10.1145/3318464.3389744

Liu Q, Huang Y, Metaxas DN (2011) Hypergraph with sampling for image retrieval. Pattern Recogn 44(10–11):2255–2262. https://doi.org/10.1016/j.patcog.2010.07.014CrossRefMATH

Ma X, Ma F, Yin J et al (2018) Cascading failures of k uniform hyper-network based on the hyper adjacent matrix. Physica A 510:281–289. https://doi.org/10.1016/j.physa.2018.06.122MathSciNetCrossRefMATH

Medya S, Ma T, Silva A, et al (2020) A game theoretic approach for core resilience. In: Proceedings of the 29th international joint conference on artificial intelligence (IJCAI), pp 3473–3479. https://doi.org/10.24963/ijcai.2020/480

Mei G, Tu J, Xiao L et al (2021) An efficient graph clustering algorithm by exploiting k-core decomposition and motifs. Comput Electric Eng 96(107):564. https://doi.org/10.1016/j.compeleceng.2021.107564CrossRef

Ouyang M, Toulouse M, Thulasiraman K et al (2002) Multilevel cooperative search for the circuit/hypergraph partitioning problem. IEEE Trans Comput Aided Des Integr Circuits Syst 21(6):685–693. https://doi.org/10.1109/TCAD.2002.1004312CrossRef

Peng H, Qian C, Zhao D, et al (2022) Targeting attack hypergraph networks. Chaos Interdiscip J Nonlinear Sci 32(7):073,121. https://doi.org/10.1063/5.0090626

Peng Y, Zhang Y, Zhang W, et al (2018) Efficient Probabilistic K-Core Computation on Uncertain Graphs. In: Proceedings of the IEEE 34th international conference on data engineering (ICDE), pp 1192–1203. https://doi.org/10.1109/ICDE.2018.00110

Rota Bulò S, Pelillo M (2013) A game-theoretic approach to hypergraph clustering. IEEE Trans Pattern Anal Mach Intell 35(6):1312–1327. https://doi.org/10.1109/TPAMI.2012.226CrossRef

Seidman SB (1983) Network structure and minimum degree. Soc Netw 5(3):269–287. https://doi.org/10.1016/0378-8733(83)90028-XMathSciNetCrossRef

Shin K, Eliassi-Rad T, Faloutsos C (2016) Corescope: Graph Mining Using k-Core Analysis-Patterns, Anomalies and Algorithms. In: Proceedings of the IEEE 16th international conference on data mining (ICDM), pp 469–478. https://doi.org/10.1109/ICDM.2016.0058

Sinha A, Shen Z, Song Y, et al (2015) An overview of microsoft academic service (MAS) and applications. In: Proceedings of the web conference 2015 (WWW), pp 243–246. https://doi.org/10.1145/2740908.2742839

Sun B, Chan THH, Sozio M (2020) Fully dynamic approximate k-core decomposition in hypergraphs. ACM Trans Knowl Discov Data 14(4):1–21. https://doi.org/10.1145/3385416CrossRef

Tan S, Guan Z, Cai D, et al (2014) Mapping users across networks by manifold alignment on hypergraph. In: Proceedings of the 28th AAAI conference on artificial intelligence (AAAI), pp 159–165. https://doi.org/10.1609/aaai.v28i1.8720

Vitter JS (1987) An efficient algorithm for sequential random sampling. ACM Trans Math Softw 13(1):58–67. https://doi.org/10.1145/21465.21474CrossRef

Yadati N, Nimishakavi M, Yadav P, et al (2019) HyperGCN: a new method of training graph convolutional networks on hypergraphs. In: Proceedings of the 33rd international conference on neural information processing systems (NeurIPS), pp 1511–1522. https://doi.org/10.48550/arXiv.1809.02589

Yadati N, Nitin V, Nimishakavi M, et al (2020) NHP: neural hypergraph link prediction. In: Proceedings of the 29th ACM international conference on information and knowledge management (CIKM), pp 1705–1714. https://doi.org/10.1145/3340531.3411870

Yang D, Qu B, Yang J, et al (2019) Revisiting user mobility and social relationships in LBSNs: a hypergraph embedding approach. In: Proceedings of the web conference 2019 (WWW), pp 2147–2157. https://doi.org/10.1145/3308558.3313635

Yin H, Benson AR, Leskovec J, et al (2017) Local higher-order graph clustering. In: Proceedings of the 23rd ACM SIGKDD international conference on knowledge discovery and data mining (KDD), pp 555–564. https://doi.org/10.1145/3097983.3098069

Zhang F, Zhang Y, Qin L, et al (2017) Finding critical users for social network engagement: the collapsed k-core problem. In: Proceedings of the 31st AAAI conference on artificial intelligence (AAAI), pp 245–251. https://doi.org/10.1609/aaai.v31i1.10482

Zhou Z, Zhang F, Lin X, et al (2019) K-core maximization: an edge addition approach. In: Proceedings of the 28th international joint conference on artificial intelligence (IJCAI), pp 4867–4873. https://doi.org/10.24963/ijcai.2019/676

Zhu W, Chen C, Wang X, et al (2018) K-Core Minimization: An Edge Manipulation Approach. In: Proceedings of the 27th ACM international conference on information and knowledge management (CIKM), pp 1667–1670. https://doi.org/10.1145/3269206.3269254

Zhu Y, Guan Z, Tan S et al (2016) Heterogeneous hypergraph embedding for document recommendation. Neurocomputing 216:150–162. https://doi.org/10.1016/j.neucom.2016.07.030CrossRef

Title: Improving the core resilience of real-world hypergraphs
Authors: Manh Tuan Do
Kijung Shin
Publication date: 09-08-2023
Publisher: Springer US
Published in: Data Mining and Knowledge Discovery / Issue 6/2023
Print ISSN: 1384-5810
Electronic ISSN: 1573-756X
DOI: https://doi.org/10.1007/s10618-023-00958-0

Springer Professional

Abstract

Please log in to get access to your license.

Dont have a licence yet? Then find out more about our products and how to get one now:

Springer Professional "Wirtschaft+Technik"

Springer Professional "Technik"

Springer Professional "Wirtschaft"

Other articles of this Issue 6/2023

Symmetry properties and asymmetry evaluation of Bayesian Confirmation Measures

i-Align: an interpretable knowledge graph alignment model

Interplay between topology and edge weights in real-world graphs: concepts, patterns, and an algorithm

An alternative for data visualization using space-filling curve

Column-coherent matrix decomposition

Explainable contextual anomaly detection using quantile regression forests

Premium Partner