# An Algorithm for Finding Optimal \(k\)-Core in Attribute Networks
## 3 Proposed Approach
### Algorithms for Finding the Optimal \(k\)-Core
#### 3.2.2 Advanced Algorithm  
We find that the performance bottleneck of the BaseLine algorithm lies in constructing \(C_{k}\) for each \(k_{min}\leq k\leq k_{max}\) and checking whether it contains the query vertex set \(Q\). Mostof the time, \(Q\) may only exist in part of \(C_{k}\), especially when the graph contains multiple connected subgraphs, resulting in more invalid computations. In addition, when \(Q\) changes, the previous calculation result cannot be reused, and the feasible \(C_{k}\) set needs to be filtered again, which is very unfavorable for online queries. Therefore, we deeply analysis the characteristics of the \(C_{k}\) set and design a two-stage query algorithm:  
* Stage 1: Utilize the nested nature of \(C_{k}\) to construct a hierarchical attribute \(k\)-core forest and sort the tree nodes. * Stage 2: Locate the query vertex set \(Q\) to the relevant tree nodes, construct an initial feasible solution, and then gradually spread to the marginal tree nodes to find the optimal attribute \(C_{k}\). 1. Constructing the attribute \(k\)-core forest  
According to Definition 1, for \(k_{min}\leq k_{1}<k_{2}\leq k_{max}\), their corresponding \(k\)-cores are \(C_{k_{1}}\) and \(C_{k_{2}}\), respectively. If \(C_{k_{1}}\) and \(C_{k_{2}}\) belong to the same connected graph, then \(C_{k_{2}}\subseteq C_{k_{1}}\), which is the nesting property of \(k\)-cores [26; 27]. Trees can be used to organize and represent the relationships between different \(C_{k}\). Combining the primary keys of these attribute scoring functions, we define the attribute \(C_{k}\) tree node as follows. **Definition 4 (attribute \(k\)-core tree node)**. : _For any \(C_{k}\) in attribute graph \(G\), there is a unique tree node \(N^{t}_{i}\), where \(t\) is the unique identifier of the tree and \(i\) is the index number of the node in the tree. \(N^{t}_{i}\) contains parent, children, vertexSet, and invertedIndex, which are, respectively used to identify its parent tree node, children tree nodes, connected \(k\)-shell vertex set, and the keyword inverted indexes in vertexSet._  
**Definition 5 (parent tree node)**. : _Given the attribute graph \(G\), for \(k_{min}\leq k_{1}<k_{2}\leq k_{max}\), their \(k\)-cores are \(C_{k_{1}}\) and \(C_{k_{2}}\), respectively, and their tree nodes are represented by \(N^{t}_{k_{1}}\) and \(N^{t}_{k_{2}}\). If \(N^{t}_{k_{1}}\) and \(N^{t}_{k_{2}}\) belong to the same tree, \(C_{k_{2}}\subseteq C_{k_{1}}\), and there is no \(k_{1}<k^{*}<k_{2}\), then \(N^{t}_{k_{1}}\) is the parent tree node of \(N^{t}_{k_{2}}\)._  
**Definition 6 (attribute \(k\)-core forest)**. : _Given the attribute graph \(G\), create attribute \(k\)-core tree nodes for each \(k_{min}\leq k\leq k_{max}\). If the tree node has a parent tree node, then connect them. All trees form the attribute \(k\)-core forest._  
It is important to note that \(k\) may not be continuous, so a tree node's core number does not necessarily equal its father tree node's core number minus 1. As shown in Figure 2, subtrees with roots \(N^{0}_{1}\) and \(N^{0}_{2}\) can be restored to 2-core and 4-core, respectively. However, due to the lack of vertices with \(core(v)=3\), \(N^{0}_{2}\) becomes the legitimate child node of \(N^{0}_{1}\), but their core numbers are not continuous. Furthermore, according to Definition 1, the subgraph composed of {9,..., 14} is actually a 5-core. So, although \(N^{0}_{2}\) and \(N^{0}_{5}\) are both child nodes of \(N^{0}_{1}\), they are located at different \(C_{k}\). Therefore, in the algorithm design for building attribute forest, we should only create tree nodes for the actual \(k\) that exists, rather than all integer in \(0\leq k\leq k_{max}\). In order to quickly locate the tree node where the query vertex is located during the query phase, we store the tree node in a set of Bins. We organize Bins according to the following rules:  
* If \(core(v)\) of the connected k-shell set in \(N^{t}_{i}\) equals \(k\), then add \(N^{t}_{i}\) to \(bin_{k}\).