The Research On Edge Classification Based On Neighborhood Similarity In Networks

Given a graph structured network G,edge classification is the problem of determining labels on unlabeled edges by using already labeled edges in G.The edge classification problem has numerous applications in graph mining and social network analysis,such as relationship discovery,categorization,and recommendation.In this paper,we study the problem of edge classification based on neighbor similarity in large graphs.Specific studies are as follow:First of all,through analyzing the existing methods,found that the existing edge classification algorithm in determining label of edge?u,v?,label of edge?u,v?is inferred by calculating the similarity between u and the vertex in neighbor set S?u?and the similarity between v and the vertex in the neighbor set S?v?.This method needs to judge the number of similar vertex pair is|S?u?|*|S?v?|,in practice,the effect is poor and the efficiency is low.Secondly,an online dynamic local index is proposed to reduce the times of traverse graph number and improve the efficiency.To solve the problem that the existing method needs to traverse the graph several times to get the result,during the first traversal the graph,record the label information of the edges that have been obtained,the highest in the subsequent judgment similarity,when judging the edge with the highest similarity,it is not necessary to traverse the data graph again and solve it directly by index.At the same time,we reduce the number of similarity vertices,reduce the number of traversal graphs,and improve the efficiency.Thirdly,in view of the problem of poor effect of the above methods,we propose to obtain the vertex w₁ with the highest similarity by using the similarity between the neighbor of u and v,at the same time,using the neighbor of v and u to calculate the similarity,the vertex w₂ with the highest similarity is obtained.Assuming that the similarity between w₁ and v is higher than that between w₂ and u,the label of edge?u,v?is represented by the label of edge?w₁,u?.The way to solve the problem of edge classification can avoid the situation that the existing method cannot give partial edge labeling,at the same time,an efficient algorithm BNSCA based on the above ideas is proposed to solve the edge labe,the number of vertex-pair similarities judged by the original method was reduced from|S?u?|*|S?v?|to|S?u?|+|S?v?|.Finally,in the experimental stage,based on three real data sets.Comparing the time of calculating the similar vertices and the accuracy of labeling without labeling,it verifies the efficiency and accuracy of the proposed method.