学科课程教师培训班第13章幻灯片.pptVIP

万维网信息的结构World Wide Web （以第13章为基础） Web信息的基本结构特征 以网页为组成单位，每个网页对应一个网址 每个网页上可能有多个链接，每个链接指向另一个网页 由此，我们可以体会到 给定网页A和B，有可能通过一个个相继的链接，经过一些中间网页，从A到达B 如果可以如此从A到达B，也可以从B到达A，中间经过的网页很可能是不一样，路径的长度也就可能是不一样的 几篇网页之间的链接关系示意 注意，不仅信息所处的位置可以相距很远，其中的主题也可能“漂移”很远；不奇怪，人的思维也如此。 有向图：Web信息结构的模型 节点：网页（可能用网址标识） 有向边：表示从一个节点到另一个节点的直接链接关系；节点的出向边与入向边 有向路径：两节点之间边的方向一致的路径 节点A到B的距离：从A到B最短有向路径的长度 注意，从A到B的距离不一定等于从B到A的距离 强连通有向图：任何两节点之间都存在两个方向的有向路径（不一定经过相同节点） 强连通分量：尽可能大的节点子集，其中每个节点都有到其中任何另一节点的有向路径 一组网页之间构成的一个有向图示例＊具体与抽象 A B A与B之间的有向路径？ 寻找强连通分量 下图是个强连通有向图吗？ 强连通分量 节点子集，其中每个节点都有到任何其他节点的有向路径 不存在真包含这个集合的节点子集 问题：一个有向图中有没有可能存在两个节点有重叠的强连通分量？ 万维网的结构模型：有向图 根据用途，可在不同层次定义图的节点和边的含义 网页层次：网页 网站层次：网站（例如我们系的网站） 机构层次：机构网站总体（例如大学各院系） 还可以按行政层级分 县、地市、省 网页层次是基础 从有向图的角度看，Web宏观上是个什么样子（“形状”）？ 对于由巨量元素构成的事物，人们往往希望能得到对其整体性态的有意义的刻画 “领结”：Web信息结构的一种概貌 1999，Andrei Broder等发现万维网包含一个超大强连通分量SCC，加上其他部分，显示出一种形象的结构 链入，链出，卷须（管道），游离 这是怎么知道的？ 基本问题 给定一个有向图，如何得到其中的强连通分量？ 显然不一定就一个。强连通分量的划分性。 以最大的强连通分量为基础，如何描述其他部分与它的关系？ 链入，链出，卷须（管道），游离 为了回答第一个问题，我们问一个更具体些的问题：给定一个节点，如何确定包含它的强连通分量？ 基本方法：广度优先有哪些信誉好的足球投注网站 从一个具体例子入手 ｛1，3，4，8，9，13，14，15，18｝； ｛2｝，｛5｝，｛6｝，｛7｝，｛10｝，｛11｝，｛12｝，｛16｝，｛17｝ 有向图的“领结”表示 计算领结结构的方法（算法） 输入：有向图G 第一步：生成图G的“反向图”G’ 第二步：选择一个在最大强连通子图中的节点A（tricky?） 第三步：以A为出发节点，在图G中宽度优先有哪些信誉好的足球投注网站直到没有新的节点发现，得节点集合FS 第四步：以A为出发节点，在图G’中宽度优先有哪些信誉好的足球投注网站直到没有新的节点发现，得节点集合BS 结果 SCC＝FS和BS的交集，即共同元素 IN（链入）＝BS－SCC OUT（链出）＝FS－SCC 基于G和G’，FS和BS，进一步集合运算可得到卷须和游离 一次计算中国Web结构的实践 2006年1月，孟涛同学用16台服务器并行工作，北大网络实验室完成了一次中国Web的网页搜集，得到了8亿3千多万网页 基于这些网页，我们构造了一个巨大的有向图，8亿3千多万个节点，数据占用磁盘容量400GB+ 在这个有向图数据上，实现了前述算法，一个程序（在16台机器上）运行了一周，得到了有关结构形状的参数 结果：自相似、层次性 网页: http://.../....html, (完整地址) 网站: http://.../*, 对应例如大学的一个系 机构: http://*..../*, 对应例如一所大学所有院系网站的集合 本章要点 有向图是信息组织的一种有效形式 尤其是对于表达信息之间的“引用关系”（“认可”关系） 有向图的重要基本概念 有向路径 强连通分量 万维网信息结构 “领结” 领结结构的计算方法 广度优先有哪些信誉好的足球投注网站，基本集合运算 * 这个图只能描述万维网全貌，并不能描述网页之间的链接关系，辨别重要网页需要更近一步的分析。14章 * * * 这个图只能描述万维网全貌，并不能描述网页之间的链接关系，辨别重要网页需要更近一步的分析。14章 * *