| Networks are ubiquitous in real life,for instance,road networks,ecological networks,protein interaction networks,social relationship networks,etc.With the birth of complexity science,people can abstract the representation of graphs about complex networks from all aspects of the real world.In the basic research of complex networks,an important branch is the study of node importance: on the importance of entities which is abstracted as nodes in complex networks in the network.And it often plays a crucial role in the prevention and control of epidemic,the spreading of economic crisis,emergency adding of power network and building for the transportation infrastructure……The weighted network always carries more information than the unauthorized network,which is more suitable for representing the network structure in the real world.There are two main factors that have plagued the research on the importance of weighted network nodes in recent years.There is a dilemma in balancing the time complexity and accuracy in calculating the node importance in both of the unweighted and weighted network.Second,for the existing algorithms,whether there is an optimization way to improve their accuracy by a low computing time.Thirdly,in weighted networks,the contribution of weights to the importance of nodes has not yet been clearly defined.These problems need to be addressed reasonably.Aiming at the node importance problem of weighted network,this thesis proposes a simple normalization method for calculating and a node importance mining algorithm which based on local topology information and an optimization method which based on half local topology or global topology information,respectively called,Weighted Expectation(WE)algorithm and List Plus(LP)algorithm.For the proposal of the WE algorithm,this thesis is inspired by the calculating of Expectation and Softmax: Relying on its characteristics,this thesis firstly establishes a new weight normalization formula according to the correlation between the strength of the connection between nodes and the weight of the edge;Furthermore,this thesis explores a new weighted network node importance calculation method based on network local topology information;Finally,on the basis of the ideas mentioned above,this thesis evaluates the node importance in the network by a certain way of calculating the node importance score.Through the experimental verification and comparative analysis with multiple node importance algorithms,WE has higher sorting accuracy and lower time complexity.For LP algorithm,the essence is that on the basis of existing research limiting the size of associated nodes,the selection mode of associated nodes is further considered:On the basis of existing sorting,based on the frustrated random walk method and the Ffunction of iteratively transferring node importance,the accuracy of node importance sorting is optimized by using multi-level neighbor information.The List Plus algorithm has good portability which can input any sorting result with a node importance score,then further improve the sorting accuracy according to the Random Walk and the contribution of the control weight to the node importance by F-function.The List Plus algorithm itself has extremely low time complexity and the experiments have proved that the algorithm can optimize the sorting accuracy. |
