# An Algorithm for Finding Optimal \(k\)-Core in Attribute Networks
## 2 Related Work  
\(k\)-core is the largest connected subgraph in a network, in which each node has a degree of no less than \(k\). It was originally used in the social sciences to characterize network cohesion [10]. Core decomposition can be completed by removing the vertices of the minimum degree one by one, which is called the peeling algorithm [11; 12]. High computational efficiency makes \(k\)-core the foundation of many algorithm models in dense subgraph mining and community search. Moreover, with the development of large-scalesocial networks, mining dense subgraphs based solely on structural compactness is no longer sufficient for meeting application requirements. Attribute graph searches [13; 14; 15; 16; 17; 18; 19; 20; 21] have gradually gained the attention of industry and academia. The ACQ query model [16] attempts to identify the community that contains the specified query vertices on the attribute graph. It shares the most attributes with the query attribute set. In contrast to the previous community search model, ACQ enhances the semantic interpretability of the target community, but the user must specify the appropriate core number as the query condition. This is too idealistic to assume that the user can be able to select the appropriate \(k\) value, which may result in the algorithm failing to find the optimal solution. As well, the query algorithm is only applicable to a single query vertex, and in the process of querying, the subset of attributes is enumerated one by one to calculate the community score, which is not suitable for social networks with rich attributes. The target subgraph of the KCCS model [17] needs to contain all query attributes, and the query path that connects each vertex in the subgraph to the attribute must be as short as possible. VAC [18] simplifies the startup parameters of the attribute community query. Users only need to provide query nodes and an integer \(k\) to limit the query range so that the quality of candidate communities can be evaluated according to various attributes of query nodes (such as geographical location and keyword attributes), which not only enriches the dimension of community attributes but also effectively avoids the risk of a rigorous query attribute set. Unfortunately, with regard to structural indicators, both KCCS and VAC models still require users to input an appropriate \(k\) value, which makes them also subject to the dilemma of selecting a \(k\) value. The ATC model [19] emphasizes that a good attribute scoring function should reward such communities, i.e., the more query attributes covered, the higher the score, and the fewer nodes unrelated to query attributes, the higher the score. Consequently, the ATC model assigns different weights to attributes and develops a community scoring function on the basis of attribute weighting. The model employs \(k\)-truss, which is tighter than \(k\)-core, as the structural indicator, but it still does not avoid the user's choice of \(k\) value, which limits the application of this model. [PERSON] et al. [20] have shown that the traditional greedy algorithm may stop prematurely during the process of improving the community score and adopt the first local optimal solution to be the optimal global solution. Therefore, they propose an elastic expansion method for the greedy algorithm, which allows the scoring function to continue trial and error within a limited number of times (including the number of trials and errors and the threshold of score reduction) after finding the first local optimal solution. While this has effectively improved the accuracy of the greedy algorithm, it does not guarantee that global optimization will be achieved. [PERSON] et al. [22] for the first time highlight the dangers associated with manually specifying the \(k\) value in the dense subgraph search problem and propose to find the optimal \(k\)-core globally to eliminate the uncertainty associated with manual selection and empirical analysis.