# An Algorithm for Finding Optimal \(k\)-Core in Attribute Networks
## 3 Proposed Approach  
### Problem Formulation  
The problem studied in this article is defined on an undirected attribute graph \(G=(V,E,A)\), where \(V,E,A\) represent the vertex set, edge set and attribute set, respectively. \(n=|V|\) and \(m=|E|\) are the number of vertices and edges, generally \(m>n\). For \(\forall v\in V\), \(v\) is an entity. Pair \((u,v)\in E\) is an edge, implying that there is a certain relationship between entities \(u\) and \(v\) (such as co-authorship, friends, etc.). For each \(v\), there is a set \(A(v)\) representing the text attributes of entity \(v\). Different entities may share common attributes, which means that they may have a certain semantic similarity in these attributes. Table 2 shows the main notations appearing throughout the remain text. To clarify the problem to be solved and the algorithm presented in this article, it is necessary to introduce the relevant concepts first. **Definition 1 (\(k\)-core). **_Given a graph \(G\) and a positive integer \(k\), the subgraph \(H\) is called a \(k\)-core of \(G\), denoted as \(\mathsf{C}_{k}\), if and only if \(H\) is a maximum connected subgraph and \(\forall v\in H\), degree\((v)\ \geq\ k\)._  
It is worth emphasizing that the \(k\)-core obtained by the classical Peeling algorithm may contain multiple connected subgraphs, some of which can be viewed as multiple kinds of \(k\)-cores. For example, in Figure 1, the subgraph composed of \(\{4,\ldots,26\}\) can be viewed as a \(4\)-core in the past, which contains two connected subgraphs. But in this article, according to Definition 1, we consider the subgraph composed of vertex set \(\{9,\ldots,14\}\) as a separate \(5\)-core, which is more appropriate in real-world application scenarios and more conducive to the subsequent creation of forests. \begin{table}
\begin{tabular}{c c c c c} \hline \hline
**Model** & **Topic** & **Participation Condition 1** & **Structural** & **Attribute** & **Target** \\  & & **Condition 1** & **Cohesiveness** & **Function** & **Community** \\ \hline
[16] & ACS & \(q\), \(S\), \(k\) & \(k\)-core & YES & local \\
[17] & ACS & \(S\), \(k\) & \(k\)-core & YES & local \\
[18] & ACS & \(Q\), \(k\) & \(k\)-truss & YES & local \\
[19] & ACS & \(Q\), \(S\), \(k\), \(d\) & (\(k\), \(d\))-truss & YES & local \\
[20] & ACS & \(Q\), \(S\) & ECOQUG & YES & local \\
[22] & CD & - & \(k\)-core & NO & global \\ Ours & ACS & \(Q\), \(S\) & \(k\)-core & NO & global \\ \hline \hline \end{tabular}  
* 1 Participation conditions may be a vertex \(q\), a query vertex set \(Q\), a query keyword set \(S\), or some positive integers \(k\) and \(d\).  
\end{table} 
Table 1: A comparison of representative models on community detection (CD) and attribute community search (ACS). \begin{table}
\begin{tabular}{c c} \hline \hline
**Notation** & **Meaning** \\ \hline \(G=(V,E,A)\) & \(G\) is an undirected attribute graph, including the vertex set \(V\), the edge set \(E\), and the attribute set \(A\). \\ \(A(v)\) & the attribute set of vertex \(v\). \\ \(V(H)\) & \(H\) is the subgraph of \(G\), \(V(H)\) is the vertex set of \(H\). \\ \(n(H)\) & the number of vertices in \(H\). \\ \(core(v)\) & the core number of vertex \(v\). \\ \(Core(H)\) & the core number set of graph \(H\). \\ \(\mathsf{C}_{k}\) & a connected graph composed of vertices with \(core(v)=k\) \\ \(V_{w}\) & a vertex set with \(w\in A(v)\) \\ \(N_{i}^{t}\) & a tree node in attribute \(k\)-core forest \\ \(bin_{k}\) & a list of tree nodes that can be restored to \(C_{k}\) \\ \hline \hline \end{tabular}
\end{table} 
Table 2: Notations and meanings. **Definition 2 (core number). **_For \(\forall v\in G\), the core number of a vertex \(v\) is \(core(v)=max\{k|v\in C_{k}\}\), which is the maximum value of \(k\) among all \(C_{k}\) containing vertex \(v\)._  
Generally, \(k_{max}\) and \(k_{min}\) are used to represent the maximum and minimum core number of the graph \(G\), while \(C_{k_{max}}\) represents the most tightly structured subgraph in graph \(G\).