# An Algorithm for Finding Optimal \(k\)-Core in Attribute Networks
## 3 Proposed Approach
### Problem Formulation
\(k\)-core can only characterize the compactness between vertices structurally, but for attribute graphs, each vertex has a different number of keywords to describe its characteristics. In order to achieve personalized queries and further explain the reasons for community formation, various attribute community search models have designed multiple attribute scoring functions [16; 18; 19; 20; 21] based on actual application scenarios to evaluate the quality of attribute communities. Different models define attribute scoring functions differently, but they are usually derived from some primary keys. Assuming that \(H\) is the subgraph to be evaluated and \(S\) is the query attribute set, this article studies the following primary keys commonly used in attribute scoring functions:  
* \(V(H)\): the vertex set of subgraph \(H\);
* \(\mathsf{n}(H)\): the number of vertices in \(H\), i.e., \(\mathsf{n}(H)=|V(H)|\);
* \(A(v)\): the attribute set of vertex \(v\);
* \(V_{w}\): the set of vertices in subgraph \(H\) containing the attribute \(w\);  
Based on the above primary keys, some attribute scoring functions are defined as follows. \[f(H,S)=\left|\cap_{v\in V(H)}(A(v)\cap S)\right| \tag{1}\]  
Equation (1) determines the number of attributes shared by all vertices in subgraph \(H\) with the query attribute set \(S\). \[f(H,S)=\sum_{w\in S}\frac{|V_{w}\cap V(H)|^{2}}{n(H)} \tag{2}\]  
First proposed by [19], Equation (2) determines the criteria that should be followed for the rating function of attribute communities. It is particularly pointed out that attributes have different contributions to community ratings, and the more vertices they are shared, the stronger the explanatory power of attributes on community semantics. Therefore,  
Figure 1: Sample network and its corresponding \(k\)-cores. Equation (2) not only depends on the number of vertices containing the attribute \(w\) but also considers the weight of the attribute \(w\) in the subgraph \(H\). \[f(H,S)=\sqrt[s]{\prod_{w\in S}\frac{\left|V_{w}\cap V(H)\right|^{2}}{n(H)}} \tag{3}\]  
Equation (3) is a modification of Equation (2), which rewards larger communities under the same conditions. That is, if each vertex of a large community covers most of the query attributes, it should receive a higher attribute score than its subgraph. \[f(H,S)=\left\{ \begin{array}{l}1,S\subseteq\left\{w|w\in\cup\limits_{v\in H}A (v)\right\}\\ 0,others\end{array} \right. \tag{4}\]  
As shown in Equation (4), some modes only require the target subgraph to cover all query attributes and then propose more requirements from different aspects, such as keyword distance [17], community diameter [21; 23; 24], similarity [18; 25], which enriches application scenarios. Therefore, the goal of this article is to find the best \(k\)-core on the attribute graph that maximizes Equations (1)-(3). The formal problem definition is as follows:  
**Definition 3** (attribute optimal \(k\)-core): _Given an undirected attribute graph \(G\), a query vertex set \(Q\), a query attribute set \(S\), and an attribute score function \(f(H,S)\), for any \(k_{min}\leq k\leq k_{max}\), if \(C_{k}\) contains all query vertices in \(Q\) and makes \(f(H,S)\) optimal, then the subgraph \(C_{k}\) is the attribute optimal \(k\)-core of \(G\)._