Thus in such case, for node u, the effect of its neighborhood is lager and the label is susceptible to change. In our method, all the nodes in network G are in ascending order on their α-degree neighborhood impacts, and we choose this order as the updating order of labels, which makes the updating order of labels relatively constant. In addition, the smaller the impact KSP is, the earlier the node updates. We strive to avert label updating oscillation to facilitate convergence. Definition 4 (ratio of stable node). — In the label updating process, after one iteration, the percentage of nodes possessing exactly identical labels as before is called the ratio of stable node. We
can calculate the stable node ratio p as p=Nc|V|, (4) where Nc is
the number of nodes whose labels have no change in this round of iteration. The stable node ratio p can be employed to measure the degree of convergence of our algorithm in the duration of label propagation. 3. Proposed Algorithm Just like the original label propagation algorithm LPA, our algorithm based on α-degree neighborhood impact also iteratively updates labels according to a node traversal order and will eventually group nodes with the same label into the same community. The difference is that we introduce the impact values for each node and use it to determine the rankings of nodes and to update the node labels. 3.1.
Label Updates The method of updating label in algorithm α-NILP is based on the average impact of neighborhood nodes. When the label of node u needs to be updated, we use the following formula to determine its new label: lunew=maxl∑i∈N(u)(VIi(α)·δ(li,l)), (5) where N(u) is a set of 1-degree neighbors of node u and δ(i, j) is the Kronecker function. If i = j, then δ(i, j) = 1; otherwise δ(i, j) = 0. Therefore, the label of the 1-degree neighbor that exerts the greatest influence becomes the new label of node u. If there exist multiple choices of greatest neighborhood influence labels of node u, we randomly select a label as the new label of node u. 3.2. Algorithm Description Given α ≥ 1, we can describe our algorithm α-NILP in the following steps. Step 1 . — For any node u in a complex network G = (V, E), calculate VIu(α) the average α-degree neighborhood impact of node u. Step 2 . — According GSK-3 to the α-degree neighborhood impact VIu(α), arrange the nodes in the network in an ascending order on the impact values to determine the updating order of node labels. Step 3 . — For any node u ∈ V, assign it a unique label, and set the stable ratio p = 0. Step 4 . — According to the determined updating order above, use formula (5) for updating labels of all the nodes. Step 5 . — Calculate stable ratio p1 of the current round of label update. Step 6 .