# Hypergraph-Clustering Method Based on an Improved Apriori Algorithm
## 2 Related Theoretical Foundations
### DSP Algorithm in Hypergraph Partitioning  
In this section, we introduce a hypergraph-partitioning algorithm based on dense subgraph partition, abbreviated as DSP [28]; this algorithm can spontaneously and effectively partition hypergraphs into dense subgraphs, called DPs. Based on the idea of divide-and-conquer, DSP is suitable for parallel processing and can be applied to large-scale hypergraphs efficiently. Therefore, we used it to obtain enough sub-clusters. Figure 2: An example of constructing hypergraphs with association rules. The gray part in the table represents the itemsets that are deleted because they are below the support threshold, and the gray arrows point to these deleted itemsets. The colored circles represent the connected hyperedges, and the hyperedges in frequent 2-itemsets are used as transitions. Finally, only \(\{v_{1},v_{2},v_{3}\}\) is retained and connected by hyperedge \(e_{1}\). A permutation \(P\) of a set of elements represents a specific order in which the elements are arranged according to a certain rule, and its sub-permutation \(R\) refers to a continuous sequence of \(P\). For a hypergraph \(H=(V,E)\), the density \(\rho(e_{i})=weight(e_{i})/|V(e_{i})|\), which is the ratio of the weight of the hyperedge \(e_{i}\) to the number of vertices included. Similarly, the density of hypergraphs can be obtained. The sub-hypergraph with the maximum density in hypergraph \(H\) is called the densest sub-hypergraph. There is only one densest sub-hypergraph with the largest number of vertices, which is called the kernel sub-hypergraph. When conditions are set and multiple sub-hypergraphs that meet the conditions have the highest density, the sub-hypergraph with the highest number of vertices is called the conditional kernel sub-hypergraph. If \(H_{u}\) is the conditional kernel sub-hypergraph of \(H_{s}\), then \(H_{u}\) is partitioned into the maximum number \(t\) of non-connected sub-hypergraphs, represented as \(DP(H_{U}|H_{S})=\left\{H_{U_{1}},\ldots,H_{U_{t}}\right\}\). For the dense sub-hypergraph partition of hypergraph \(H\), it is defined as follows:  
\[DSP(H)=\left\langle DP(H_{v_{1}}|\varnothing),\ldots,DP(H_{v_{i}}|H_{\cup_{j-1 }^{i-1}y_{j}}),\ldots,DP(H_{v_{n}}|H_{\cup_{j-1}^{n-1}y_{j}})\right\rangle \tag{5}\]  
where \(\cup_{i=1}^{n-1}v_{i}=v\) and \(H_{v_{1}}\) is the kernel sub-hypergraph of \(H\). \(H_{v_{i}}(i>1)\) are conditional kernel sub-hypergraphs conditioned on the sub-hypergraphs \(H_{\cup_{j-1}^{i-1}y_{j}}\). Based on the above, the DSP partition algorithm includes two layers. First, the hypergraph \(H\) is continuously partitioned into a series of conditional kernel sub-hypergraphs, \(\left\langle H_{V_{1}},\ldots,H_{V_{n}}\right\rangle\). The partition of vertices set \(V\) is represented as \(\Psi(V)=\left\langle v_{1},\ldots,v_{n}\right\rangle\). Then, each sub-hypergraph \(H_{v_{i}}\) is partitioned into dense sub-hypergraphs. \(\Psi(V)\) defines the order of partitioning the vertices set \(V\). If there are \(\mid V\mid\) permutations of \(V\), there must be one permutation that satisfies the order of vertices in \(\Psi(V)\), denoted as \(\Theta(H)\). Based on \(\Theta(H)\), it is easy to find the dense sub-hypergraphs of the partition. Therefore, the algorithm for partitioning DSP can be described as follows:  
The time complexity of Algorithm 1 Is \(\text{O}\left(\tau dn_{e}(n_{v}+n_{e})^{2}\right)\), where \(\tau\) is the number of iterations in the algorithm and \(n_{v}\) and \(n_{e}\) are the number of vertices and hyperedges of the dense sub-hypergraph with maximum size, respectively.