Node Importance Ranking Algorithm Based On Directed Simple 3-motif In Graph Network:Direct-motif Rank

PageRank algorithm is an algorithm to calculate the importance of nodes in graph network data.The importance of each node is calculated by the importance of in-chain nodes and the number of in-chain nodes.It can be widely used in practical problems such as search engine recommendation,social network crowd importance ranking and literature author ranking.However,in practical problems,due to the topology of the graph network structure,the importance contribution of the same node to different nodes is different.At this time,using the original PageRank algorithm to calculate the importance of nodes in the network is not accurate enough.Moreover,the PageRank algorithm based on undirected structure can change the weight of edges in the calculation process,but it introduces too much noise and masks the network structure characteristics of the original graph,which will affect the accuracy of the algorithm ranking.In order to solve the above problems,this thesis proposes a PageRank algorithm based on a directed simple 3-motif in a graph network: Direct-motif rank.Firstly,the edge frequency matrix of the closed directed simple 3-motif in the network is calculated,in order to improve the robustness of the model,a small amount of noise is added to obtain the adjacency matrix based on the specific local directed simple motif,which is normalized with the original graph network adjacency matrix respectively,and then linearly combined to obtain a new adjacency matrix.The new adjacency matrix is used to run the PageRank algorithm.In the whole process,the directed local feature orientation of graph network is used to change the weight of edges in the calculation process.Compared with PageRank algorithm with undirected structure,the influence of noise is less,and the final adjacency matrix is constructed by normalizing and then linear combination,which retains the structural features of the original graph network,so as to achieve the purpose of making the sorting results more accurate.This thesis will use the reference data set DBLP and the actual social network data set Epinions for modeling,and use the discount cumulative gain(DCG)as the index.Through different linear combination coefficients,different local structures and different topk ranking results,it is empirically judged that the Direct-motif rank algorithm is more accurate for the node ranking effect of the graph network than the undirected structure PageRank algorithm.In addition,because the DCG indicator requires the nodes of the graph network data to have a benchmark evaluation score,and some data sets in the actual problem may not meet this condition.Therefore,starting from the practical significance of Normalized Discount Cumulative Gain(NDCG)(the degree to which the results of the sorting algorithm reach the ideal sorting),this thesis explores new evaluation indicators by comparing the sorting results with each other: mutual normalized discount cumulative gain(MNDCG),and uses the results of MNDCG to prove the ranking effect of the Direct-motif rank algorithm better than the PageRank algorithm with undirected motif.