Research On Leader Node Concealment Methods For Network Centrality Analysis

Network analysis is the process of analyzing network structures through the use of methods such as graph theory.Network analysis technique plays an important role in measuring the importance of nodes,improving network information dissemination,and link prediction.This technique is widely used in many areas such as sociology,economic,geography,etc.However,the existing researches focus on designing or optimizing network analysis algorithms,and the problem of malicious network analysis,namely the abuse of network analysis technique by attackers,is not paid enough attention to,which may cause network privacy and security risks.Starting from the network analysis technique of closeness centrality,this dissertation starts from two different ways of reducing the value of the leader node or increasing the ranking of the leader node,and proposes new methods for hiding the leader node from malicious network analysis.The main innovation points and contributions in this dissertation are listed as follows:First,in order to reduce the closeness value of the leader node,this problem is transformed into the problem of removing limited edges to minimize the closeness value of the leader node,and this optimization problem is proven to be NP-hard.An approximate algorithm based on greedy algorithm is proposed to obtain an approximate optimal solution of the optimization problem,and a dynamic update closeness value algorithm based on the pruning idea is proposed.Combining the greedy algorithm and the dynamic update algorithm,the time cost of recalculating the value can be reduced,and the approximate optimal solution performs better than the theoretical lower bound.Experimental results show that the average acceleration rate of dynamic update algorithm is above 10,and it can significantly reduce the time required for recalculation in complex networks,showing that this algorithm is effective.In the real-life and random generated network datasets,comparing the greedy algorithm with the optimal solution,the minimum approximation rate is 0.85,which is much higher than the theoretical lower bound(1-1/e=0.63),and the approximate results is better than the solution of baseline algorithms,showing that the greedy algorithm is effective.Second,hiding the leader node under the measure of closeness ranking is also investigated.Similar to the previous work,the problem of hiding the leader node is first transformed into the optimization problem,and this optimization problem is proven to be NP-hard.Due to that the optimization problem is not submodular,the greedy algorithm cannot reach the theoretical lower bound,and the greedy simulated annealing algorithm is proposed to improve the accuracy of the approximate solution.Based on shortest path lower bound algorithm,a fast calculation algorithm for closeness ranking is proposed to reduce the number of traversing the network required to calculate the ranking of the leader node.In experimental results,except for the ER network,the acceleration rate of the closeness ranking fast calculation algorithm in other datasets is above 9,proving that the fast calculation algorithm is effective.In the experiment,the effectiveness of the greedy simulated annealing algorithm is also proved by comparison with the optimal solution and the baseline algorithm solution.