参考节点嵌入最短距离估算在图聚类中的应用

Application of shortest distance estimation based on reference node embedding in graph clustering

为解决社会关系网络图中节点没有坐标值、不能采用传统的欧几里得距离和曼哈坦距离进行聚类的问题,提出采用最短路径算法,来衡量点与点之间的相异度。针对最短路径算法具有时间复杂度大的缺点,引入基于参考节点嵌入的最短距离估算思想来估算两点之间的近似距离。在此基础上,针对DBLP数据集构成的社会关系网络图进行聚类,使用基于划分的k-medoids算法,分别采用以上两种距离算法,比较其优劣。实验证明改进后的算法和最短路径算法中的Dijkstra算法相比,距离误差率小,时间复杂度大大降低,在提高效率的同时,取得了同样好的聚类效果。

To deal with the problem that Euclidean distance or Manhattan distance cannot be used in graph clustering algorithm,because the vertices in a social network have no coordinates,shortest path algorithm is proposed,which is used to measure the dissimilarity between the vertices.Firstly,aiming at the problem of shortest path algorithm having big time complexity shortcoming,the idea of shortest distance estimation based on reference node embedding is introduced to estimate the approximate distance between two vertices.On that basis,K-medoids of partition-based graph clustering algorithm is applied to partition the social network extracted from the DBLP data into different subgraph,the above two distance algorithms are used to compare their advantages and disadvantages.In view of improved algorithm compared with shortest path algorithm such as Dijkstra,experimental results demonstrate that distance error rate is small,the time complexity is reduced greatly,the same good effect of clustering is archived at the time of improving efficiency.