## 4 Methods
### Local Extend Algorithm  
The intuitive algorithm is essentially the enumeration of graphs starting from \(q\), resulting in massive invalid subgraphs. According to the nesting nature of k-core, we believe that if there is a better solution, it must be included by the initial feasible community. Therefore, we first detect the maximum feasible community \(H\) as the initial subgraph, which can significantly reduce the search space. We calculate \(TScore(q,v)\) for each node \(v\) in \(H\), then sort them in descending order according to the score. Starting from \(q\), we gradually expand the nodes under the guidance of the best score until a feasible community is formed. Then, we choose the feasible community with the highest score, that is, the optimal solution. We use \(Et\) to represent the extended point set, \(C\) represents the candidate point set, \(H_{B}\) represents the current optimal solution, and \(H_{Et+v}\) represents the feasible solution derived from \(Et+v\). During each expansion, we select the best node according to the following node selection strategy:  
* Strategy 1: Select the neighbor node \(v\) of \(Et\) from \(C\) with the highest \(TScore(q,v)\);
* Strategy 2: If there are multiple nodes satisfying strategy (1), we choose the node with the largest degree. Strategy 1 ensures that the score of the subgraph is monotonically decreasing. Strategy 2 is to select nodes with cohesive structures and organize them into feasible solutions as soon as possible. At the same time, we follow the following extension rules and stop rules. * Extend Rule 1: If \(TScore(q,H_{Et+v})<TScore(q,H_{B})\) and \(|H_{B}|>|H_{Et+v}|\), then add node \(v\) to \(Et\) and continue to expand. * Extend Rule 2: If \(TScore(q,H_{Et+v})>TScore(q,H_{B})\), then add node \(v\) to \(Et\), update \(H_{B}=H_{Et+v}\) and continue to expand. * Extend Rule 3: If \(TScore(q,H_{Et+v})=TScore(q,H_{B})\) and \(|H_{B}|<|H_{Et+v}|\), then add node \(v\) to \(Et\), update \(H_{B}=H_{Et+v}\) and continue to expand. Extend Rule 1 describes the early stage of the algorithm, not finding enough nodes to form a feasible community. Extend Rule 2 shows that the addition of node \(v\) allows us to obtain a new feasible solution with a higher score, and so we update the current optimal community. Extend Rule 3 occurs after Extend Rule 2. Adding a new best node \(v\) does not reduce the score of \(H_{B}\), indicating that the algorithm has found a larger feasible community and should update the current optimal solution. * Stop Rule 1: If \(TScore(q,H_{Et+v})<TScore(q,H_{B})\) and \(H_{B}\subseteq H_{Et+v}\), then stop extension. * Stop Rule 2: If \(C=\varnothing\), then stop extension. Stop Rule 1 may be triggered after the feasible solution is formed. Specifically, if \(H_{B}\) cannot maintain its score when expanding \(v\), we can conclude that there will not exist a more extensive feasible community whose score is no less than \(H_{B}\). Thus, the expansion should be stopped and return \(H_{B}\) as the optimal solution. Stop Rule 2 is easy to understand. There are no extensible nodes, so \(H_{B}\) is naturally the optimal community. The Local Extend algorithm is outlined in Algorithm 1, which integrates all expansion and stop strategies. In the worst case, the initial feasible solution is the optimal solution, and thus the algorithm will expand from \(q\) to each node, but generally not. ```
Input: A graph \(G=(V,E)\), a query node \(q\), a non-negative integer \(k\). Output: A \(k-core\)\(H_{B}\) with the maximum \(TScore(q,H_{B})\). 1: Find the maximum feasible community \(H\) as initial subgraph. 2: For each node \(v\) in \(H\), compute \(TScore(q,v)\), then arrange them in descending order according to the score. 3:\(Et\gets q\); \(C\gets V_{H}-q\); \(H_{B}\gets H\);
4: Extend ( \(Et,C,H_{B}\) )
5: return \(H_{B}\). Procedure Extend(\(Et,C,H_{B}\))
6: if \(C=\varnothing\), then
7: Update \(H_{B}\); over;
8:else
9: Select the best node \(v\) from \(C\) according to the vertex selection strategy.