Research On Comparison Of Node Similarity Based On Local Neighborhood

High-dimensional complex data in the real world can often be represented as graph structured data,such as social networks,transportation networks,protein interaction networks,etc.,where nodes represent entities and edges represent relationships between entities.Nodes with similar functions in the network usually have high similarity in structure,attributes and so on.Node similarity determination is very important in complex network analysis.Structural similarity measures the similarity of topological features between nodes,which is widely used in network function module identification,key node identification,link prediction and so on.Most of the existing algorithms use the low-order topological characteristics of nodes,such as node degree,neighbor node degree distribution,proximity centrality,aggregation coefficient,etc.,to calculate the structural similarity between nodes,while the high-order structural characteristics,such as subgraphs,paths,loops,communities,etc.,are often ignored,which makes the existing algorithms have certain limitations when dealing with complex networks.In this paper,higher-order neighborhood information is used to study the structural similarity between nodes.The main work is as follows:(1)In order to utilize the higher-order structure information of nodes and their neighborhoods effectively,a structure similarity measurement algorithm MNDD(Node Structure similarity measurement based on Multiple Neighborhood Degree Distribution)is proposed.MNDD uses the degree distribution information of multi-order neighborhood of nodes to represent the higher-order structure information of nodes.The structural similarity between nodes is obtained by JS divergence between their higher-order structure information distributions.Compared with the algorithms with low-order structural information,the proposed algorithm takes the relationship between nodes and their neighborhoods into account to measure the structrual similarity effectively.Experiments on real network data sets show that MNDD algorithm performs well in real network analysis and node classification tasks.(2)Aiming at the sparse representation of node neighborhood structure in MNDD algorithm,a structure similarity measurement algorithm ANNLI(A Node Structure similarity determination algorithm for Aggregation Node Neighborhood Label Information)is proposed.In this algorithm,WL algorithm is used to aggregate and update the neighborhood information of nodes,and local labels of nodes are obtained.By using Skip-gram model,the node neighborhood label information is embedded into the lowdimensional space.Finally,the embedded similarity between nodes is used to calculate the structural similarity between nodes.The proposed algorithm makes full use of the higherorder structure information of nodes,alleviates the sparsity of neighborhood structure,and effectively measures the structural similarity between nodes.The embedding obtained from ANNLI algorithm is applied into classification tasks on UCI classification data sets such as breast-cancer.Compared with the embedding obtained from classical algorithms such as Node2 vec,ANNLI algorithm has higher classification accuracy and more accurate calculation of node structure similarity.(3)In order to make full use of the high-order structure information of the network,a structure similarity measurement algorithm GANNLI(A Node structure similarity determination algorithm for Aggregation Label Information of k-tuple Group in Node Neighborhood)is proposed.In this algorithm,the non-isomorphic subgraphs formed by ktuple were used as group labels,and the neighborhood group label information of k-tuple was aggregated by WL algorithm,and the group labels were updated.The label information of different k-tuple formed by nodes is counted to obtain node representation.The structural similarity between nodes is calculated by cosine similarity.Compared with the algorithm that only considers the low order information such as node degree and proximity centrality,this algorithm uses the high order k-tuple structure information to measure the structural similarity between nodes more effectively.Experimental results on real network data sets show that using structural similarity of k-tuple information can improve the accuracy of node classification task.