第 １ 期 电 子 学 报 Ｖｏｌ．４９ Ｎｏ．１
ｇｒａｐｈ ｉｎｔｏ ａ ｃｏｍｐａｃｔ ａｎｄ ｓｍａｌｌ-ｓｃａｌｅ ｇｒａｐｈ
ｗｈｉｌｅ ｒｅｔａｉｎｉｎｇ ｔｈｅ ｓｔｒｕｃｔｕｒｅ ａｎｄ ａｔｔｒｉｂｕｔｅ ｉｎｆｏｒｍａｔｉｏｎ ｏｆ ｔｈｅ ｏｒｉｇｉｎａｌ ｇｒａｐｈ．Ｗｉｔｈ ｔｈｅ ｉｎｃｒｅａｓｉｎｇ ｓｉｚｅ ｏｆ ｇｒａｐｈ，ｇｒａｐｈ ｄａｔａ ｂｅ-
ｃｏｍｅｓ ｄｉｆｆｉｃｕｌｔ ｔｏ ｑｕｅｒｙ ａｎｄ ｓｔｏｒｅ．Ｄｉｓｔａｎｃｅ-ｂａｓｅｄ ｑｕｅｒｉｅｓ，ｓｕｃｈ ａｓ ｓｈｏｒｔｅｓｔ ｐａｔｈ ｑｕｅｒｉｅｓ，ｄｅｐｅｎｄ ｈｅａｖｉｌｙ ｏｎ ｔｈｅ ｓｉｚｅ ｏｆ ｇｒａｐｈ．
Ｉｎ ｔｈｉｓ ｐａｐｅｒ，ａ ｄｉｓｔａｎｃｅ ｑｕｅｒｙ-ｏｒｉｅｎｔｅｄ ａｔｔｒｉｂｕｔｅ ｗｅｉｇｈｔｅｄ ｇｒａｐｈ ａｇｇｒｅｇａｔｉｏｎ ａｌｇｏｒｉｔｈｍ ｉｓ ｐｒｏｐｏｓｅｄ，ｗｈｉｃｈ ｎｏｔ ｏｎｌｙ ｇｕａｒａｎｔｅｅｓ
ｔｈｅ ｓｉｍｉｌａｒｉｔｙ ｏｆ ｓｔｒｕｃｔｕｒｅ ａｎｄ ａｔｔｒｉｂｕｔｅｓ ｂｅｔｗｅｅｎ ｎｏｄｅｓ，ｂｕｔ ａｌｓｏ ｐｒｅｓｅｒｖｅｓ ｔｈｅ ｄｉｓｔａｎｃｅ ｂｅｔｗｅｅｎ ｎｏｄｅｓ，ａｎｄ ｅｆｆｅｃｔｉｖｅｌｙ ｒｅｄｕｃｅｓ
ｔｈｅ ｓｉｚｅ ｏｆ ｔｈｅ ｇｒａｐｈ．Ｔｈｅ ｅｘｐｅｒｉｍｅｎｔｓ ｐｒｏｖｅ ｔｈａｔ ｔｈｉｓ ｍｅｔｈｏｄ ｉｓ ｅｆｆｅｃｔｉｖｅ ａｎｄ ｅｆｆｉｃｉｅｎｔ ｉｎ ｔｈｅ ｑｕｅｒｙ ｔａｓｋｓ．
Ｋｅｙ ｗｏｒｄｓ： ｇｒａｐｈ ａｇｇｒｅｇａｔｉｏｎ；ｇｒａｐｈ ｑｕｅｒｙ；ｄｉｓｔａｎｃｅ ｐｒｅｓｅｒｖｉｎｇ；ｓｔｒｕｃｔｕｒｅ ｓｉｍｉｌａｒｉｔｙ；ａｔｔｒｉｂｕｔｅ ｅｎｔｒｏｐｙ
准进行图压缩，而图聚类则是根据图中节点密度，对节
１ 引言
点进行聚类．
现实生活中，存在大量用图结构表示的数据，图中 图聚集方法可以分为两类，以压缩为目的的图聚
节点表示实体，边表示实体与实体之间的关系，如社交 集方法和面向查询的图聚集方法．
网络中用户之间的关系，交通网络中道路之间的关系，
面向距离查询的属性加权图聚集算法 来自淘豆网m.daumloan.com转载请标明出处.
