【摘要】 本发明涉及一种互联网超链接网络图数据的简化方法，该方法首先对所述超链接网络的图数据G0’，得到第一级简化子图G1’。再根据图的度序列确定第二级简化子图G2’的起点S2’，从S2’开始对G1’作宽度优先遍历，从G1’中选择点加入到G2’中，在G2’中选择点连接生成边，得到第二级简化子图G2’。再以从G1得到G2’的方法从G2’得到G3’，并以此类推得到最优简化子图G’。本发明方法得到的简化子图能够去除母图中的非关键点，有效地保留母图的拓扑结构，从而使子图相对于母图具备较好的代表性，且简化效率高。由于根据度序列确定起点及宽度优先遍历的计算量较小，因而本方法的执行速度快，而且可以对图进行分层次简化。 【专利类型】发明授权 【申请人】常州工学院 【申请人类型】学校 【申请人地址】213011 江苏省常州市天宁区通江南路299号 【申请人地区】中国 【申请人城市】常州市 【申请人区县】天宁区 【申请号】CN201210177910.8 【申请日】2012-05-31 【申请年份】2012 【公开公告号】CN102750263B 【公开公告日】2014-10-22 【公开公告年份】2014 【授权公告号】CN102750263B 【授权公告日】2014-10-22 【授权公告年份】2014.0 【IPC分类号】G06F17/20; G06F40/00 【发明人】毛国勇; 张永春; 张燕红; 高敏; 廉春原 【主权项内容】1.一种互联网超链接网络图数据的简化方法，包含以下步骤：步骤一、对所述超链接网络的图数据G0’进行去除自回路和平行边的预处理，得到第一级简化子图G1’=(V1’，E1’)，V1’为一级点的集合， E1’为一级边的集合，所述点为所述互联网的超链接网络中的网页，所述边为所述互联网的超链接网络中网页间的链接关系; 并设第n级简化子图Gn’为下一级简化子图Gn+1’的母图GOn’；n为初值等于1的整数；步骤二、选择所述母图GOn’中具有最优度的点作为下一级简化子图G n+1’的起点S n+1’，其中度为一网页与其他网页的链接总数，所述最优度的点为超链接总数最多的网页；步骤三、从所述起点S n+1’开始对所述母图进行宽度优先遍历，获得所述下一级简化子图G n+1’=(V n+1’，E n+1’)，其中V n+1’为下一级点的集合，E n+1’为下一级边的集合；所述的获得所述下一级简化子图G n+1’=(Vn+1’，En+1’)的方法包括以下步骤：A：把所述起点Sn+1’及其直接邻接点加入到该级已遍历点的集合VT n+1’中，并把所述起点S n+1’加入到所述下一级点的集合V n+1’中；B：若已加入集合VTn+1’中的各直接邻接点的邻接点不在所述集合VTn+1’中，则将该直接邻接点作为所述集合V n+1’的新的加入点，并连接所述已加入点与所述新的加入点生成边，并将所述边加入到所述下一级边的集合E n+1’中，并将所述新的加入点及其直接邻接点加入到所述集合VTn+1’中；C：对于所述新的加入点，重复所述步骤B，直至遍历结束，以构成所述下一级简化子图G n+1’=(V n+1’，E n+1’)；步骤四、设所述下一级简化子图G n+1’为再下一级简化子图的母图GO(n+1)’，重复所述步骤二、三直至得到最优简化子图G’, 即获得最优超链接网络。 【当前权利人】上海前隆信息服务有限公司 【专利权人类型】公立 【统一社会信用代码】12320400467283964D 【引证次数】2.0 【他引次数】2.0 【家族引证次数】2.0 【家族被引证次数】2

未经允许不得转载：http://www.zhongzhencnc.com/1789873828.html