# 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
10:else:
11: compute the lowest common ancestor for \(N_{i\_min}^{t}\) and \(N_{i\_max}^{t}\) as \(LCAncestor\);
12:end if
```  
**Algorithm 2** LCA algorithm  
According to the hierarchical tree construction process shown in Algorithm 1, the tree nodes are numbered in a preorder traversal manner, which endows the tree nodes with the following query properties. **Property 1**. : _For tree nodes \(N_{i}^{t_{1}}\) and \(N_{j}^{t_{2}}\), if \(t_{1}\
eq t_{2}\), then they do not belong to the same tree, that is, the vertices in their vertexSet are not connected._  
**Property 2**. : _For tree nodes \(N_{i_{1}}^{t}\) and \(N_{i_{2}}^{t}\), if \(i_{1}<i_{2}\), then \(N_{i_{1}}^{t}\) is created before \(N_{i_{2}}^{t}\)._  
**Property 3**. : _For tree nodes \(N_{i_{1}}^{t}\), \(N_{i_{1}}^{t}\), \(N_{i_{2}}^{t}\), if \(i_{1}<i<i_{2}\), then the LCA of \(N_{i_{1}}^{t}\) and \(N_{i_{2}}^{t}\) is also the LCA of all of them._  
Firstly, the Algorithm 2 locates relevant tree nodes (see lines 3, 4) based on the core number of the query vertices, and records the minimum and maximum tree node index (\(i\_min\) and \(i\_max\), respectively). According to Property 1, if the located tree nodes do not belong to the same tree, the query ends prematurely. According to the Properties 2 and 3, the LCA of \(N_{i\_min}^{t}\) and \(N_{i\_max}^{t}\) is also the LCA of all tree nodes in \(Nodelist\). Therefore, it is only necessary to perform a classic LCA search algorithm for \(N_{i\_min}^{t}\) and \(N_{i\_max}^{t}\) once. If you want it to be faster, you can consider a fast LCA algorithm. The subtree with the LCA node as the root node can be restored to the tightest subgraph containing all query vertices. Algorithm 3 takes it as the initial feasible solution and enters the expanding query stage to search for the optimal solution. As shown in Figure 2, when \(Q=\{4\,,9\,,16\,,25\}\), Algorithm 2 locates relevant tree nodes as \(Nodelist=\big{\{}N_{2}^{0},N_{3}^{0},N_{4}^{0},N_{5}^{0}\big{\}}\), \(i\_min=2\), \(i\_max=5\). Simply locating the LCA of \(N_{2}^{0}\) and \(N_{5}^{0}\) as \(N_{1}^{0}\), which is also the ancestor of \(N_{3}^{0}\) and \(N_{4}^{0}\). The subtree rooted on \(N_{1}^{0}\) can be restored to a connected 2-core, which is the initial feasible solution containing all query vertices. In Algorithm 3, the primary keys and optimal solution \(C_{best}\) are first initialized with the subtree rooted in \(LCAncestor\), as shown in lines 2-4. If \(LCAncestor\) is not the root of the tree, then we take its parent tree node as \(current\_root\) and enter the expansion phase. Note that the subtree rooted on \(LCAncestor\) has completed the calculation of the primary keys and can be recorded as \(finished\_subtree\) (line 5). Subsequently, only other child subtrees of \(current\_root\) will be traversed. The traversal process continuously updates the primary keys, and only calculates the score of the new graph when tracing back to \(current\_root\), as shown in lines 9-13. After that, we update \(finished\_subtree\) again and continue to expand upward until the root of the tree to obtain the optimal solution \(C_{best}\). Assuming \(Q=\{4,\ 16,\ 25\}\), according to Algorithm 2, the \(LCAncestor\) is located as \(N_{2}^{0}\), that is, the initial feasible solution is \(C_{4}\). According to Algorithm 3, since \(N_{2}^{0}\) is not the root of the tree, it needs to be extended upward to the \(N_{1}^{0}\) node to calculate subgraph \(C_{2}\). Note that \(N_{1}^{0}\) has two child nodes, but \(N_{2}^{0}\) has already completed the calculation. It only needs to visit \(N_{5}^{0}\), update \(V(H)\) and \(V_{w}\), and complete the calculation of the 2-core score when going back to \(N_{1}^{0}\). In the same way, continue to expand to \(N_{0}^{0}\) and calculate the score of \(C_{1}\). At this time, \(C_{best}\) is obtained. Although the time of the Advanced algorithm can be divided into two parts: forest creation and extended query, once the hierarchical forest is created, it only needs dynamic maintenance [28].