# A Key Node Mining Method Based on K-Shell and Neighborhood Information
## 3 Proposed Methods
### KCH Methods
#### 3.2.3 KCH  
Consider a simple undirected, unweighted graph \(G(V,E)\), where \(V\) represents the set of nodes, and \(E\) is the set of edges. In many networks, nodes with a low degree can also be influential; for example, bridge nodes with SH are typical low-degree, high-influence nodes. Additionally, a higher local clustering coefficient indicates that a node's neighbors tend to cluster together, which can enhance the node's influence. Therefore, this paper uses the KS method to collect the global topological structure information of the network while also obtaining local structural information through SH and the clustering coefficient. By combining both global and local structural information, we aim to measure and rank the importance of nodes more effectively. The KS method, which has been detailed in Section 3.1, will not be reiterated here in Section 3.2. The first-order clustering coefficient of node i is defined as the sum of the local clustering coefficients of its first-order neighbors. Let \(N_{i}\) represent the set of neighboring nodes of node i. The specific definition is as follows:  
\[C_{i}^{1}=\sum_{j\in N_{i}}C_{j} \tag{11}\]  
Since node i is also a neighbor to its first-order neighbors, it affects the calculation of the first-order clustering coefficient. Furthermore, the smaller the network constraint coefficient of a node, the higher the likelihood of it being a structural hole, indicating stronger influence capability. In this method, we use the reciprocal of the network constraint coefficient to measure the SH evaluation, as shown in the following formula, where a larger SH value signifies stronger influence capabilities. \[sh_{i}=\frac{1}{SH_{i}} \tag{12}\]  
The calculation method of KCH involves two primary steps. First, we use the K-shell algorithm to obtain the KS values, \(ks_{i}\), for each node in the network G. Then, we calculate the structural holes (\(sh_{i}\)) and the first-order clustering coefficient (\(C_{i}^{1}\)) for each node using the aforementioned formulas. Second, we calculate the KCH value for each node. The KCH centrality of a node is defined by the following formula:  
\[KCH(i)=ks_{i}+y_{i} \tag{13}\]  
\[y=f\Big{(}sh+C^{1}\Big{)} \tag{14}\]  
\[f(x)=\frac{x-min}{max-min} \tag{15}\]Here, \(f()\) represents the maximum-minimum normalization formula, y is the normalized data result, x is the original data, and \(min\) and \(max\) denote the minimum and maximum values of the original data, respectively. A higher KCH value indicates greater importance of the node. We use the example network to illustrate the execution process of the KCH method. The network has 15 nodes and 27 edges, and its K-shell layered diagram is shown in Figure 1. We initiate the demonstration of the KCH by selecting node 3 as an example to showcase its execution process. First, we calculate the \(ks_{i}\) (values of K-Shell) of node 3, which is 4. Next, we identify the neighboring nodes of node 3, which are its closest neighbors: 1, 2, 4, 5, 10, and 15. Next, we calculate the local clustering coefficient and network constraint coefficient for each neighboring node. Subsequently, we compute the \(C_{i}^{1}\) and \(sh_{i}\) of node 3, and calculate the sum of the two, which is 5.7660. Then, normalize it. The local clustering coefficient and network constraint coefficient of the first-order neighbors of node 3 are shown in Table 1.  
Finally, we obtain the KCH value of this node by adding its \(ks_{i}\) and the \(y_{i}\). \[KCH(i)=ks_{i}+y_{i}=ks_{i}+f\Big{(}sh_{3}+C_{3}^{1}\Big{)}=4+f(5.7660)=4.6083 \tag{16}\]  
The time complexity of the KCH method is primarily concentrated in two parts. The first part involves the calculation of KS values, structural holes, and the first-order clustering coefficient. The second part is the calculation of KCH itself. The K-shell algorithm requires traversing each node and edge in the graph, resulting in a time complexity of \(O(|V|+|E|)\), where \(|V|\) is the number of nodes in the network and \(|E|\) is the number of edges.