融合结构与属性相似性的加权图聚集算法

计算机工程与科学

融合结构与属性相似性的加权图聚集算法

邴睿1，马慧芳1,2,3，刘宇航1，余丽1

（1.西北师范大学计算机科学与工程学院，甘肃兰州 730070;

2.桂林电子科技大学广西可信软件重点实验室,广西桂林 541004;

3.广西师范大学广西多源信息挖掘与安全重点实验室，广西桂林 541004）

收稿日期:2018-08-28 修回日期:2019-01-03 出版日期:2019-10-25 发布日期:2019-10-25
基金资助:
国家自然科学基金(61762078，61363058)；广西可信软件重点实验室研究课题(kx201910);广西多源信息挖掘与安全重点实验室开放基金(MIMS18-08)

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.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

摘要：

图聚集技术是将一个大规模图用简洁的小规模图来表示，同时保留原始图的结构和属性信息的技术。现有算法未同时考虑节点的属性信息与边的权重信息，导致图聚集后与原始图存在较大差异。因此,提出一种同时考虑节点属性信息与边权重信息的图聚集算法，使得聚集图既保留了节点属性相似度又保留了边权重信息。该算法首先定义了闭邻域结构相似度，通过一种剪枝策略来计算节点之间的结构相似度；其次使用最小哈希(MinHash)技术计算节点之间的属性相似度，并调节结构相似与属性相似所占的比例；最后，根据2方面相似度的大小对加权图进行聚集。实验表明了该算法可行且有效。

关键词: 图聚集, 结构相似度, 属性相似度, 加权图, 最小哈希

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)

邴睿1，马慧芳1,2,3，刘宇航1，余丽1. 融合结构与属性相似性的加权图聚集算法[J]. 计算机工程与科学.

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

A weighted graph aggregation algorithm based

on structural similarity and attribute similarity

[J]. Computer Engineering & Science.

[1]	马满福, 姜璐娟, 李勇, 张强, 范颜军, 邓晓飞. 基于AFP的有向加权注意力流网络链路预测[J]. 计算机工程与科学, 2022, 44(10): 1762-1770.
[2]	徐景秀, 张青. 改进小波软阈值函数在图像去噪中的研究应用[J]. 计算机工程与科学, 2022, 44(01): 92-101.
[3]	肖继海, 崔晓红, 陈俊杰. 节点属性和拓扑信息相结合的脑网络聚类模型[J]. 计算机工程与科学, 2020, 42(11): 2088-2095.
[4]	王威1，刘婧1，李骥1，刘洋1，潘伟2. 基于变差函数全局纹理增强的结构相似度图像质量评价[J]. J4, 2016, 38(04): 726-732.
[5]	刘婧,王威，李骥，杨蔚蔚. 基于对偶树复小波变换的模糊图像质量评价[J]. J4, 2015, 37(08): 1573-1578.
[6]	刘玉军，汪明辉，蔡猛，陈坤. 降低Ad hoc网络信息泄露的路由算法[J]. J4, 2015, 37(06): 1087-1092.
[7]	卢凯，熊振海，李崇飞，李根. 基于全局结构相似度度量方法的显著性检测[J]. J4, 2013, 35(6): 113-117.
[8]	李崇飞1,高颖慧2,卢凯1,曲智国2. 基于结构相似度的视觉显著性检测方法[J]. J4, 2013, 35(10): 181-185.
[9]	韩毅1，贾焰1，刘春阳2，周斌1，韩伟红1. 一种基于相似性聚类的社会网络合作模式发现方法[J]. J4, 2012, 34(6): 146-152.
[10]	戚尚菊,纪秀花. 基于边缘的结构相似度模糊图像质量评价[J]. J4, 2011, 33(2): 133-136.