A Research And Application Of The Detection Of Key Nodes In Networks

Key nodes detection is always at the forefront of the research of complex network science and has been widely used in various technical fields such as viral marketing,recommendation systems,and biomedicine.Based on different views on the importance of nodes,many algorithms and models have flooded into the world recently,but a large number of data lacking real labels make it difficult to verify the effectiveness of these algorithms,and the related theories based on real experiments still lack sufficient accuracy.In addition,not just the key nodes,but all nodes are aggregated by their linking actions,which are called their behavioral patterns.The research on the behavioral pattern of nodes can reveal the evolution mechanism of the network from the micro level.However,the current algorithms not only need to manually set many critical parameters,but also usually have very high computational complexity.This thesis will focus on how to detect key nodes in social exchange networks.The core of it is to create a new measure of importance.Because after measuring the importance of the node,it is only necessary to rank the nodes according to their importances and then take the top nodes as the key nodes.More specifically,this thesis is based on the Nash bargaining solution,a solution concept of cooperative game,to determine the specific division of profit on every edge.Then Backward Induction,a critical technique which also comes from game theory,will be used to extrapolate the credible alternatives used by each node to negotiate,which revises the alternatives defined by the previous Nash negotiating solution,and thus greatly improving its predictive accuracy.Furthermore,this thesis extends the algorithm to be applicable to the more complex scenarios where people are able to achieve multiple transactions per round.Finally,the algorithm takes the maximal profit gained by a node as its importance measure,and selects key nodes accordingly.For the analysis and prediction of nodes’ behavioral patterns,because the massive data carried in the era of big data has caused the diversification and temporality of entity relationships,this thesis uses the tensor to describe multi-dimensional and multi-linear coupling in such complex network systems,and proposes SASTA algorithm to decompose the original tensor to extract node features,which can automatically determine the size of factor matrices and nuclear tensor after decomposition,and has a smaller time complexity compared with traditional algorithms.Then based on the node features obtained by SASTA,the nodes are clustered by the synchronization-based clustering algorithm to analyze their behavioral patterns.This algorithm does not need to manually set the number of clusters.After that,the exponential smoothing technique is used to fit the tensor that will appear in the future.The SASTA and synchronization-based clustering algorithm will be used again to predict the nodes’ future behavioral patterns.In short,SASTA,synchronization-based clustering algorithm,and exponential smoothing technique constitute a complete algorithmic framework for analyzing and predicting nodes’ behavioral patterns.Finally,the thesis compares the algorithms with several real and artificial datasets and verifies that the proposed algorithm and algorithmic framework have higher accuracy and lower computational complexity.