• 中国计算机学会会刊
  • 中国科技核心期刊
  • 中文核心期刊

Computer Engineering & Science

Previous Articles     Next Articles

A weighted graph aggregation algorithm based
on  structural similarity and attribute similarity

BING Rui1,MA Hui-fang1,2,3,LIU Yu-hang1,YU Li1   

  1.  
    (1.College of Computer Science and Engineering,Northwest Normal University,Lanzhou 730070;
    2.Guangxi Key Laboratory of Trusted Software,Guilin University of Electronic Technology,Guilin 541004;
    3.Guangxi Key Laboratory of Multi-Source Information Mining & Security,Guangxi  Normal University,Guilin 541004,China)
     
  • Received:2018-08-28 Revised:2019-01-03 Online:2019-10-25 Published:2019-10-25

Abstract:

Graph aggregation is a technology for representing a large scale graph with a concise graph that can preserve the structural and attribute information of the original large graph. Existing algorithms consider either the attribute information of nodes or the weight information of edges, and the difference between the original graph and the aggregated graph can thus be huge. So we propose a graph aggregation method considering both the attribute information of nodes and the weight information of edges, which enables the aggregated graph not only to preserve the similarity of node attributes but also edge weight information. Firstly, we define the closed neighborhood structural similarity, and use a structure pruning strategy to calculate the structural similarity between nodes. Secondly, minimum hash (Minhash) technique is employed to calculate the attribute similarity between nodes, and the proportions of structure similarity and attribute similarity are adjusted, based on which the weighted graph is aggregated. Experiments prove the feasibility and effectiveness of our method.


 

Key words: graph aggregation, structural similarity, attribute similarity, weighted graph, minimum hash (Minhash)