# 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
* For tree nodes in the same \(bin_{k}\), sort them by tree number \(t\) first. Then, for nodes belonging to the same tree, sort them by the minimum rank of vertices in the vertexSet. So when locating the query vertex, we only need to search for the \(bin_{k}\) based on \(core(v)\), and further locate its corresponding tree node with help of binary search algorithm. Note that if the located tree nodes belong to different trees, the query ends immediately because our target subgraph is at least a connected graph. Algorithm 1 shows the pseudo-code for constructing a hierarchical forest. On the basis of core decomposition, hierarchical trees are constructed for each connected subgraph, finally resulting in a hierarchical forest. Lines 5, 6 create the root node of each tree, and line 7 recursively constructs its child nodes. Note that in Procedure _Build_child_node_, the tree nodes are numbered in the preorder traversal order. It also maintains _parent_k_ and _child_k_ during each recursive, which can avoid establishing blank tree nodes and reduces the storage cost of forests. In addition, the algorithm initially leaves bins empty and then creates a new \(bin_{k}\) when discovering an unclassified core number \(k\). In other cases, only update the corresponding \(bin_{k}\). For a parent tree node, after all its child nodes are created, its attribute inverted index can be constructed as shown in line 10 of Procedure _Build_child_node_, since now all nodes in its \(vertexSet\) belong to the same connected k-shell. ```
Input: A graph \(G=(V,E,A)\) Output: the hierarchical forest \(Bins\)
1:\(t\gets 0\), \(Bins\leftarrow\varnothing\)
2:compute \(core(v)\) of each vertex in \(G\) by core decomposition;
3: construct connected \(Subgraphs\) from \(G\);
4:for graph in \(Subgraphs\):
5:\(k_{min}\gets min(core(v))\) in \(Core(graph)\), \(node\_index\gets 0\);
6: create root tree node \(N_{node\_index}^{t}\) and update \(bin_{k_{min}}\);
7:\(Build\_child\_node(N_{node\_index}^{t},k_{min})\);
8: update tree indicator \(t\);
9: return \(Bins\). Procedure \(Build\_child\_node(parent\_node,parent\_k)\):
1: select vertices with \(core(v)>parent\_k\) as candidate children vertex set;
2: if candidate children vertex set is not empty:
3: obtain connected subgraphs composed of candidate vertex sets as _children_graphs_;
4: for each graph in \(children\_graphs\):
5:\(node\_index\gets node\_index+1\);
6: select \(min(core(v))\) in this graph as \(child\_k\);
7: create \(child\_nodeN_{node\_index}^{t}\) and update \(bin_{child\_k}\);
8: update \(parent\_node\);
9:\(Build\_child\_node(child\_node,child\_k)\);
10: create attribute reverse index for \(parent\_node\);
11: end \(Build\_child\_node\)
```  
**Algorithm 1** Building forest  
As shown in Figure 2, the hierarchical forest corresponding to the network in Figure 1 is composed of two trees, including a total of eight tree nodes. Starting from the root of the tree, as the depth increases, the core number of tree nodes gradually increases (not necessarily continuously), indicating an increasingly compact structure. Figure 2: Hierarchical forest and the sorted tree nodes. Node localization and extended query  
We apply the attribute hierarchical forest to the Advanced query algorithm, which consists of two parts: identifying the Lowest Common Ancestor node (LCA), and expanding the query, as shown in Algorithms 2 and 3. ```
Input: the hierarchical forest \(Bins\), the query vertex set \(Q\) Output: the lowest common ancestor \(LCAncestor\)
1:\(Nodelist\leftarrow\varnothing\), \(i\_min\gets None\), \(i\_max\gets None\)
2:for\(v\) in \(Q\):
3: locate \(bin_{k}\) according \(core(v)\);
4: perform a binary search the tree node \(N_{i}^{t}\), where \(v\in N_{i}^{t}\):vertexSet;
5: add \(N_{i}^{t}\) to \(Nodelist\);
6: update \(i\_min\) and \(i\_max\);
7:end for
8:if the tree indicator \(t\) of \(N_{i}^{t}\) in \(Nodelist\) are different:
9: return \(None\) # the query nodes do not belong to the same tree and have no common ancestor.