第13章 万维网结构_875608944
- 格式：pptx
- 大小：1.27 MB
- 文档页数：23
下载文档原格式
合集下载
第13章 万维网结构_875608944
以a为出发节点在图g中宽度优先搜索直到没有新的节点发现得节点集合bs基于g和gfs和bs进一步集合运算可得到卷须和游离计算领结结构的算法16从一个具体例子入手fs134589101314151618bs1346789111213141518计算领结结构的算法17计算领结结构的算法fs134589101314151618bs1346789111213141518sccfsbs348913141518inbsscc671112outfsscc510162和17是卷须18计算领结结构的方法算法有向图的领结表示19一次计算中国web结构的实践2006年1月孟涛同学用16台服务器并行工作北大网络实验室完成了一次中国web的网页搜集得到了8亿3千多万网页基于这些网页构造了一个巨大的有向图8亿3千多万个节点数据占用磁盘容量400gb在这个有向图数据上实现了前述算法一个程序在16台机器上运行了一周得到了有关结构形状的参数20结果
15
计算领结结构的算法
输入：有向图G 第一步：生成图G的“反向图”G’ 第二步：选择一个在最大强连通子图中的节点A（tricky?）
第三步：以A为出发节点，在图G中宽度优先搜索直到没有
新的节点发现，得节点集合FS 第四步：以A为出发节点，在图G’中宽度优先搜索直到没有 新的节点发现，得节点集合BS 结果
在这个有向图数据上，实现了前述算法，一个程
序（在16 台机器上）运行了一周，得到了有关结 构形状的参数
20
网页: http://.../....html, (完整地址) 网站: http://.../*, 对应例如大学的一
个系
机构: http://*..../*, 对应例如一所大
学所有院系网站的集合
13 万维网结构 The Structure of the Web
15
计算领结结构的算法
输入：有向图G 第一步：生成图G的“反向图”G’ 第二步：选择一个在最大强连通子图中的节点A（tricky?）
第三步：以A为出发节点，在图G中宽度优先搜索直到没有
新的节点发现，得节点集合FS 第四步：以A为出发节点，在图G’中宽度优先搜索直到没有 新的节点发现，得节点集合BS 结果
在这个有向图数据上，实现了前述算法，一个程
序（在16 台机器上）运行了一周，得到了有关结 构形状的参数
20
网页: http://.../....html, (完整地址) 网站: http://.../*, 对应例如大学的一
个系
机构: http://*..../*, 对应例如一所大
学所有院系网站的集合
13 万维网结构 The Structure of the Web
《万维网概述》课件
大数据是指规模庞大、复 杂多样的数据集合，需要 新技术来处理、存储和分 析。
大数据的应用
大数据技术在金融、医疗、 营销等领域有着广泛的应 用，帮助人们从海量数据 中提取有价值的信息。
万维网在大数据 时代的应用
万维网在大数据时代的应 用包括数据挖掘、个性化 推荐和智能搜索等。
未来的趋势
1
万维网的未来
万维网将继续发展，越来越多的设
新兴技术对万维网的影响
2
备和物体将连接到互联网，形成更 智能、更便利的生活。
人工智能、大数据、物联网等新兴
技术将对万维网产生深远的影响和
变革。
3
人工智能技术在万维网中的
应用
人工智能技术将使万维网更加智能 和个性化，提供更精准的搜索结果 和推荐服务。
结语
万维网的发展从未止步，随着技术的进步和用户需求的变化，它将不断演化和创新。希望本课程 能够为您提供全面的了解和启发，谢谢！
搜索引擎
1
搜索引擎的定义
搜史
搜索引擎的发展经历了多个阶段，从最初的Yahoo到后来的Google，技术和算法 一直在不断创新。
3
搜索引擎的分类
搜索引擎可以根据运作方式分为蜘蛛型、目录型和社交媒体型等不同类型。
Web 2.0
Web 2.0的定义
网是指通过移 动设备（如手机、平板 电脑）访问互联网的方 式。
移动互联网的发展 历程
从2G到5G，移动互联网 的技术不断升级，数据 传输速度和可靠性有了 显著提升。
移动应用
移动应用是为移动设备 开发的软件，如社交媒 体应用、游戏等。
大数据时代下的万维网
大数据的定义
万维网的历史
万维网的起源可以追溯到20世纪60年代，但真正的爆发是在1990年代，由英国科学家蒂姆·伯纳斯 -李发明。从那以后，万维网经历了快速发展，成为了人类社会不可或缺的一部分。
大数据的应用
大数据技术在金融、医疗、 营销等领域有着广泛的应 用，帮助人们从海量数据 中提取有价值的信息。
万维网在大数据 时代的应用
万维网在大数据时代的应 用包括数据挖掘、个性化 推荐和智能搜索等。
未来的趋势
1
万维网的未来
万维网将继续发展，越来越多的设
新兴技术对万维网的影响
2
备和物体将连接到互联网，形成更 智能、更便利的生活。
人工智能、大数据、物联网等新兴
技术将对万维网产生深远的影响和
变革。
3
人工智能技术在万维网中的
应用
人工智能技术将使万维网更加智能 和个性化，提供更精准的搜索结果 和推荐服务。
结语
万维网的发展从未止步，随着技术的进步和用户需求的变化，它将不断演化和创新。希望本课程 能够为您提供全面的了解和启发，谢谢！
搜索引擎
1
搜索引擎的定义
搜史
搜索引擎的发展经历了多个阶段，从最初的Yahoo到后来的Google，技术和算法 一直在不断创新。
3
搜索引擎的分类
搜索引擎可以根据运作方式分为蜘蛛型、目录型和社交媒体型等不同类型。
Web 2.0
Web 2.0的定义
网是指通过移 动设备（如手机、平板 电脑）访问互联网的方 式。
移动互联网的发展 历程
从2G到5G，移动互联网 的技术不断升级，数据 传输速度和可靠性有了 显著提升。
移动应用
移动应用是为移动设备 开发的软件，如社交媒 体应用、游戏等。
大数据时代下的万维网
大数据的定义
万维网的历史
万维网的起源可以追溯到20世纪60年代，但真正的爆发是在1990年代，由英国科学家蒂姆·伯纳斯 -李发明。从那以后，万维网经历了快速发展，成为了人类社会不可或缺的一部分。
《万维网概述》课件
浏览器
使用高速缓存可减少 访问因特网服务器的时延
没有使用高速缓存的情况
校园网 R1
这条链路上 的时延很大
源点服务器
2 Mb/s
R2 因特网
所有万维网通信量 都经过这条链路
使用高速缓存的情况
(1) 浏览器访问因特网的服务器时，要先与校园网的 高速缓存建立 TCP 连接，并向高速缓存发出 HTTP 请求报文
浏览器
校园网 R1
源点服务器
2 Mb/s R2
因特网
校园网的高速缓存 （代理服务器）
使用高速缓存的情况
(5) 高速缓存收到此对象后，先复制在其本地存储器 中（为今后使用），然后再将该对象放在 HTTP 响 应报文中，通过已建立的 TCP 连接，返回给请求该 对象的浏览器。
浏览器
校园网 R1
2 Mb/s R2
●为 了 在 万 维 网 上 方 便 地 查 找 信 息 ， 用 户 可 使用各种的搜索工具（即搜索引擎）。
2 统一资源定位符 URL
1. URL的格式
●统一资源定位符 URL 是对可以从因特网上得到的资 源的位置和访问方法的一种简洁的表示。
●URL 给资源的位置提供一种抽象的识别方法，并用 这种方法给资源定位。
(3) 否则，高速缓存就代表发出请求的用户浏览器， 与因特网上的源点服务器建立 TCP 连接，并发送 HTTP 请求报文。
浏览器
校园网 R1
源点服务器
2 Mb/s R2
因特网
校园网的高速缓存 （代理服务器）
使用高速缓存的情况
(4) 源点服务器将所请求的对象放在 HTTP 响应报 文中返回给校园网的高速缓存。
万维网必须解决的问题
(1) 怎样标志分布在整个因特网上的万维网文 档？
JavaWeb编程技术(沈泽刚版)教材习题参考答案
第4章Java Web编程习题解析4.1 第1章习题解析1. 略。
2. 答：URL称为统一资源定位符，URL通常由4部分组成：协议名称、页面所在主机的DNS名、可选的端口号和资源的名称。
URI称为统一资源标识符，是以特定语法标识一个资源的字符串。
URI由模式和模式特有的部分组成，它们之间用冒号隔开，一般格式如下：schema:schema-specific-partURI是URL和URN的超集。
3. 答：①是URL，①和②都是URI，③是URN4. 答：动态Web文档技术包括服务器端动态文档技术和客户端动态文档技术，前者包括CGI技术、服务器扩展技术和HTML页面中嵌入脚本技术。
其中HTML页面中嵌入脚本技术包括ASP、PHP和JSP技术。
最流行的客户端动态文档技术是在HTML页面中嵌入JavaScript脚本代码。
使用JavaScript可以设计交互式页面。
与服务器端动态文档不同，JavaScript脚本是在客户端执行的。
5. 答：Servlet是用Servlet API开发的Java程序，它运行在Servlet容器中。
Servlet容器是运行Servlet的软件，主要用来扩展Web服务器的功能。
6. 答：开发Servlet的一般步骤包括：（1）编写Servlet源程序；（2）编译；（3）将Servlet部署到Servlet容器中；（4）访问执行Servlet。
7. 答：<tomcat-install>\lib\servlet-api.jar文件。
8. 答：部署描述文件名是web.xml，它是XML文件，应该存放在Web应用程序的\WEB-INF目录中。
9. 答：当服务器找不到用户请求的资源时将发生404错误。
10. 答：JSP页面是嵌入了Java脚本元素的HTML页面。
11. 答：Servlet主要用来实现业务逻辑和控制逻辑，JSP页面主要用来实现表示逻辑。
Java Web 编程习题解析第4章 4.2 第2章习题解析1. 答：Servlet 接口定义了下面5个方法：public void init(ServletConfig config)public void service(ServletRequest request, ServletResponse response) throws ServletException, IOExceptionpublic void destroy()public ServletConfig getServletConfig()public String getServletInfo()2. 答：Servlet 是在容器中运行的组件，有一个从创建到销毁的过程，其中包括加载和实例化、初始化、提供服务以及销毁几个阶段。
网页设计与制作各章习题及答案
网页设计与制作各章习题及答案第1章习题1. 填空题(1) WWW服务于_1990_年由设立在欧洲瑞士的粒子物理研究中心开发研制出来。
(2) WWW是_Word Wide Web_的缩写，其含义是_“全球网”_，很多人又形象地称其为_“万维网”_。
(3) 现在网页基本可以分为_静态_和_动态_两大类网页。
(4) 对于网站，我们通常又称作_站点_(5) HTML是Hypertext Markup Language 的缩写，意思为_超文本标记语言_。
(6) marquee代码的作用_实现标记中的内容在页面移动的效果_(7) HTML源代码包括_<Head></Head>头_和_<Body></Body>正文__两大部分(8) CuteFTP是一种基于__Ftp__的数据交换软件。
(9) CuteFTP有很多功能，如_断点续传_、_自动登陆_等，是上传、维护、更新网站必不可少的工具软件。
(10) Flash是网络上最为流行的_矢量__动画制作软件。
(11) 网页的主要组成元素有_文本__、__图片_、_多媒体_、_超链接_和_脚本_五种。
(12) 与网站设计相关的软件主要有_Dreamweaver_、_Photoshop_、_Flash_和_CuteFTP_。
(13) _<html>_和_</html>_是Web页的第一个和最后一个标记符，Web页的其他所有内容都位于这两个标记符之间。
2. 选择题(1) 下面哪些文件属于静态网页（ C ）A. abc.asp?????B. abc.doc?????C. abc.htm?????????D. abc.jsp(2) 下面哪些不是网页编辑软件（ B ）A. Dreamweaver?B. CuteFTP?????C. Word????????????D. Flash(3) 下面哪些文件不是网站的主页（ C? ）A. index.html??B. Default.jsp?C. index1.htm??????D. Default.php(4) DreamweaverMX是哪家公司的产品?? （ D ）A. Adobe???????B. Corel???????C. Microsoft???????D. Macromedia(5) 网页元素不包括：（ C）A. 文字????????B. 图片????????C. 界面????????????D. 视频(6) 下列哪种软件是用于网页排版的。
(完整word版)计算机网络(第六版)谢希仁著课后习题答案
第一章概述1-01 计算机网络向用户可以提供那些服务？答：连通性和共享1-02 简述分组交换的要点。
答：（1）报文分组，加首部（2）经路由器储存转发（3）在目的地合并1-03 试从多个方面比较电路交换、报文交换和分组交换的主要优缺点。
答：（1）电路交换：端对端通信质量因约定了通信资源获得可靠保障，对连续传送大量数据效率高。
（2）报文交换：无须预约传输带宽，动态逐段利用传输带宽对突发式数据通信效率高，通信迅速。
（3）分组交换：具有报文交换之高效、迅速的要点，且各分组小，路由灵活，网络生存性能好。
1-04 为什么说因特网是自印刷术以来人类通信方面最大的变革？答：融合其他通信网络，在信息化过程中起核心作用，提供最好的连通性和信息共享，第一次提供了各种媒体形式的实时交互能力。
1-05 因特网的发展大致分为哪几个阶段？请指出这几个阶段的主要特点。
答：从单个网络APPANET向互联网发展；TCP/IP协议的初步成型建成三级结构的Internet；分为主干网、地区网和校园网；形成多层次ISP结构的Internet；ISP首次出现。
1-06 简述因特网标准制定的几个阶段？答：（1）因特网草案(Internet Draft) ——在这个阶段还不是 RFC 文档。
（2）建议标准(Proposed Standard) ——从这个阶段开始就成为 RFC 文档。
（3）草案标准(Draft Standard)（4）因特网标准(Internet Standard)1-07小写和大写开头的英文名字internet 和Internet在意思上有何重要区别？答：（1） internet（互联网或互连网）：通用名词，它泛指由多个计算机网络互连而成的网络。
；协议无特指（2）Internet（因特网）：专用名词，特指采用 TCP/IP 协议的互联网络区别：后者实际上是前者的双向应用1-08 计算机网络都有哪些类别？各种类别的网络都有哪些特点？答：按范围：（1）广域网WAN：远程、高速、是Internet的核心网。
万维网原理
万维网原理万维网（World Wide Web）是一种基于超文本传输协议（HTTP）的信息系统，它是互联网的一个重要组成部分，也是人们日常生活中不可或缺的一部分。
万维网的出现极大地改变了人们获取信息的方式，让人们可以轻松地浏览、检索和分享各种信息资源。
那么，万维网是如何实现的呢？它的原理又是什么呢？首先，我们来谈谈万维网的基本组成部分。
万维网由一系列的网页（web page）组成，每个网页都可以包含文本、图片、视频、音频等多媒体内容。
这些网页通过超链接（hyperlink）相互连接，形成了一个庞大的信息网络。
万维网的核心技术是超文本标记语言（HTML），它定义了网页的结构和内容，使得网页能够在各种不同的设备上被正确地显示和解释。
其次，我们需要了解万维网是如何实现信息的传输和交换的。
在万维网中，客户端通过浏览器向服务器发送HTTP请求，服务器接收到请求后，会返回相应的网页内容。
这种基于客户端-服务器模式的交互方式，使得用户可以在任何时间、任何地点访问互联网上的各种信息资源。
除了HTTP协议，网页的传输还依赖于统一资源定位符（URL）和网页的传输协议（如HTTPS、FTP等），它们共同构成了万维网的基本架构。
此外，万维网的信息检索和搜索功能也是其重要的特点之一。
搜索引擎通过网络爬虫（web crawler）定期抓取互联网上的网页内容，并建立索引，用户可以通过关键词在搜索引擎上进行检索，从而快速找到所需的信息。
搜索引擎的出现大大提高了用户获取信息的效率，也促进了互联网信息的共享和传播。
最后，我们需要了解万维网的发展趋势。
随着移动互联网、物联网、大数据等技术的快速发展，万维网也在不断地演进和完善。
移动互联网使得人们可以随时随地使用手机、平板等移动设备访问互联网，物联网使得各种智能设备可以互联互通，大数据技术为万维网的信息处理和分析提供了更强大的支持。
未来，万维网将更加智能化、个性化，为人们的生活和工作带来更多的便利和乐趣。
7 万维网结构
– CNNIC – China Internet Network Information Center – 阎宏飞，李晓明，“关于中国Web的大小、形状和结构”，《计算机研究 与发展》，第39卷，第8期，2002年8月，第958-967页。 – 李晓明，“对中国曾有过静态网页数的一种估计”，《北京大学学报》 （自然科学版），第39卷，第3期，2003年5月，394-398。
– 超链接（hyperlink）
• A包含一个指向B的超链通常意味着A对B的一种“认可”
• 基本优势：可扩展性
几篇网页之间的链接关系
• 注意，不仅信息所处的位置可以相距很远，其中的主题也可 能“漂移”很远；不奇怪，人的思维也如此。
学术文章之间 引用关系构成 信息网络
“链接”不仅 用于表达网页 之间的关系
– SCC＝FS和BS的交集，即共同元素 – IN（链入）＝BS－SCC – OUT（链出）＝FS－SCC
• 在FS和BS基础上进一步操作可给出卷须和游离（细节略）
一个计算实例
• From Jan-Feb, 2006, PKU conducted a relatively thorough crawl of Chinese web, 830 million pages were collected • As a result, PKU constructed a huge directed graph of 830 million nodes, summing to 400GB+ data • A program ran one week on a 16 nodes cluster and generated the shape parameters
• People seriously report it from time to time – 1997, ~200 million, K. Bharat and A. Broder – 1998, ~800 million, S. Lawrence and C. Giles – 2000, ~2.1 billion, Shayna Keces – 2005, ~11.7 billion, A. Gulli and A. Signorini • People maintain websites to talk about it – 如何估计Web – 的规模？ – • In China, CNNIC annually reports it since 2002
– 超链接（hyperlink）
• A包含一个指向B的超链通常意味着A对B的一种“认可”
• 基本优势：可扩展性
几篇网页之间的链接关系
• 注意，不仅信息所处的位置可以相距很远，其中的主题也可 能“漂移”很远；不奇怪，人的思维也如此。
学术文章之间 引用关系构成 信息网络
“链接”不仅 用于表达网页 之间的关系
– SCC＝FS和BS的交集，即共同元素 – IN（链入）＝BS－SCC – OUT（链出）＝FS－SCC
• 在FS和BS基础上进一步操作可给出卷须和游离（细节略）
一个计算实例
• From Jan-Feb, 2006, PKU conducted a relatively thorough crawl of Chinese web, 830 million pages were collected • As a result, PKU constructed a huge directed graph of 830 million nodes, summing to 400GB+ data • A program ran one week on a 16 nodes cluster and generated the shape parameters
• People seriously report it from time to time – 1997, ~200 million, K. Bharat and A. Broder – 1998, ~800 million, S. Lawrence and C. Giles – 2000, ~2.1 billion, Shayna Keces – 2005, ~11.7 billion, A. Gulli and A. Signorini • People maintain websites to talk about it – 如何估计Web – 的规模？ – • In China, CNNIC annually reports it since 2002
《电子商务网站建设与维护》复习资料(试题及答案讲解)
第三章Dreamweaver CS6创建基本文本网页
第一节Dreamweaver CS6工作环境
第二节创建站点
第三节添加文本元素
第四节编辑文本格式
第五节设置头信息
第六节实战演练——创建基本文本网页
第四章创建超级链接
第一节超级链接的基本概念
第二节创建链接的方法
第三节实战演练
第五章使用图像和多媒体创建丰富多彩的网页
★考核知识点:域名和空间
附1.1.2（考核知识点解释）
.gov为政府机关域名不是商业域名，商业域名为com。
20、控制网页图片宽度和高度的html代码是（）
A.width B.length C.height D.area
★考核知识点:html代码
附2.1.1（考核知识点解释）
控制图片宽度和高度用width和height.
4、关于利用dreamweaver建立站点，描述正确的是（D）
A.必须建立站点B.不能建立站点C.站点没什么用D.根据用户需要
★考核知识点:Dreamweaver cs6
附3.2.1（考核知识点解释）
一个网站站点实际上就是一个文件夹，建立站点的目的是方便管理网站，一个网站可以不建立站点。
5、表格中表示行的html标记是（C）
A.图层可以隐藏B.图层可以锁定
C.图层的位置不可以更改D.图层中可以添加文字
★考核知识点:photoshop图层
附23.1.1（考核知识点解释）
Photoshop图层相当于透明的玻璃，可以隐藏，可以锁定，可以调整顺序，可以添加文字。
17、下列关于网站制作正确的是（D）
A.photoshop就可以制作网站B.网站不需要布局
21、下列属于可以创建的超级链接有（ABCD）
第一节Dreamweaver CS6工作环境
第二节创建站点
第三节添加文本元素
第四节编辑文本格式
第五节设置头信息
第六节实战演练——创建基本文本网页
第四章创建超级链接
第一节超级链接的基本概念
第二节创建链接的方法
第三节实战演练
第五章使用图像和多媒体创建丰富多彩的网页
★考核知识点:域名和空间
附1.1.2（考核知识点解释）
.gov为政府机关域名不是商业域名，商业域名为com。
20、控制网页图片宽度和高度的html代码是（）
A.width B.length C.height D.area
★考核知识点:html代码
附2.1.1（考核知识点解释）
控制图片宽度和高度用width和height.
4、关于利用dreamweaver建立站点，描述正确的是（D）
A.必须建立站点B.不能建立站点C.站点没什么用D.根据用户需要
★考核知识点:Dreamweaver cs6
附3.2.1（考核知识点解释）
一个网站站点实际上就是一个文件夹，建立站点的目的是方便管理网站，一个网站可以不建立站点。
5、表格中表示行的html标记是（C）
A.图层可以隐藏B.图层可以锁定
C.图层的位置不可以更改D.图层中可以添加文字
★考核知识点:photoshop图层
附23.1.1（考核知识点解释）
Photoshop图层相当于透明的玻璃，可以隐藏，可以锁定，可以调整顺序，可以添加文字。
17、下列关于网站制作正确的是（D）
A.photoshop就可以制作网站B.网站不需要布局
21、下列属于可以创建的超级链接有（ABCD）
《三、 网站的结构》作业设计方案-高中信息技术人教版选修3
《网站的结构》作业设计方案（第一课时）一、作业目标通过本次作业，学生将：1. 理解和掌握网站的结构，包括网页的布局、导航、链接等基本要素；2. 学会分析一个网站的结构，理解其设计理念和目的；3. 培养逻辑思维和问题解决能力，提高信息技术应用水平。
二、作业内容1. 任务一：网站结构分析请选择一个你熟悉的网站（如：学校官网、新闻网站等），分析其网站结构，包括首页、内页、导航、链接等要素。
将分析结果以文字形式（不少于XX字）描述出来，并绘制出该网站的简单结构图。
2. 任务二：网站目的与设计理念探究在分析完所选网站的结构后，思考该网站的目的和设计理念，查阅相关资料，以报告形式（不少于XX字）阐述你的理解。
3. 任务三：个人网站规划结合所学知识和对其他网站的观察分析，为自己或同学规划一个简单的个人网站，包括网站名称、目的、结构、内容等要素。
三、作业要求1. 作业需独立完成，不得抄袭；2. 分析报告和结构图需认真撰写，符合规范；3. 三个任务均需按时提交，提交形式可以是电子版文档或实物版报告；4. 鼓励创新思维，积极思考，提出自己的见解。
四、作业评价1. 评价标准：作业完成质量、分析报告的字数、结构图的绘制、资料的查阅和引用等方面；2. 评价方式：教师评价与学生互评相结合，最终综合评定成绩；3. 成绩评定：优秀（90-100分）、良好（80-89分）、中等（70-79分）、及格（60-69分）、不及格（60分以下）。
五、作业反馈1. 学生应在作业提交后的X天内，关注教师评语和反馈，及时修改和完善；2. 对于作业中存在的问题和不足，学生可向教师请教，寻求帮助和建议；3. 教师将定期收集和分析学生作业完成情况，不断优化和改进教学方案。
通过本次作业，学生将更深入地理解和掌握网站的结构和设计理念，提高自己的信息技术应用能力，为后续的网页设计和开发打下坚实的基础。
同时，教师也将根据学生的作业反馈，不断调整和优化教学方案，提高教学质量。
- 1、下载文档前请自行甄别文档内容的完整性，平台不提供额外的编辑、内容补充、找答案等附加服务。
- 2、"仅部分预览"的文档,不可在线预览部分如存在完整性等问题,可反馈申请退款(可完整预览的文档不适用该条件!)。
- 3、如文档侵犯您的权益，请联系客服反馈,我们会尽快为您处理(人工客服工作时间：9:00-18:30)。
个网页 由此，我们可以体会到
给定网页A 和B，有可能通过一个个相继的链接，经过 一些中间网页，从A到达B 如果可以如此从A到达B，也可以从B到达A，中间经过 的网页很可能是不一样，路径的长度也就可能是不一 样的
5
Web组织形式
几篇网页之间的链接关系示意
注意，不仅信息所处的位置可以相距很远，其中的主题也可
2
万维网 World Wide Web
3
万维网 World Wide Web
万维网原始构想和设计包含的两个基本特征 网页(web page)，资源以网页的形式创建和存储 浏览器(browser)，访问网页的方式
4
Web组织形式
以网页为组成单位，每个网页对应一个网址 每个网页上可能有多个链接，每个链接指向另一
能“漂移”很远；不奇怪，人的思维也如此
6
超文本的技术雏形
社会学的论文引用
三元闭包，小世界
现象，结构平衡， 同质性
7
超文本的技术雏形
Wiki中博弈论文章
的交叉引用
8
Vannevar Bush and the Memex
Vannevar Bush 曼哈顿计划的发起者 发起建立NSF Memex(Memory-Extender) 1945年，Vannevar Bush在《大西洋月刊》
15
计算领结结构的算法
输入：有向图G 第一步：生成图G的“反向图”G’ 第二步：选择一个在最大强连通子图中的节点A（tricky?）
第三步：以A为出发节点，在图G中宽度优先搜索直到没有
新的节点发现，得节点集合FS 第四步：以A为出发节点，在图G’中宽度优先搜索直到没有 新的节点发现，得节点集合BS 结果
18
计算领结结构的方法算法
有向图的“领结”表示
19
一次计算中国Web结构的实践
2006 年 1 月，孟涛同学用 16 台服务器并行工作，
北大网络实验室完成了一次中国Web 的网页搜集， 得到了8亿3千多万网页 基于这些网页，构造了一个巨大的有向图，8 亿3 千多万个节点，数据占用磁盘容量400GB+
强连通有向图：任何两节点之间都存在两个方向
的有向路径（不一定经过相同节点）
强连通分量：尽可能大的节点子集，其中每个节
点都有到其中任何另一节点的有向路径
10
一组网页之间 构成的一个有 向图示例
＊具体与抽象
A
B
11
将万维网看成有向图
寻找强连通分量
下图是强连通有向图吗？
• 强连通分量 – 节点子集，其 中每个节点都 有到任何其他 节点的有向路 径 – 不存在真包含 这个集合的连 通分量
14
万维网的“领结”结构
给定一个网络结构，如何得到强连通分量？ 显然不一定就一个。强连通分量的划分性 以最大的强连通分量为基础，如何描述其他部分
与它的关系？
链入，链出，卷须（管道），游离
为了回答第一个问题，我们问一个更具体些的问 题：给定一个节点，如何确定包含它的强连通分 量？
基本方法：广度优先搜索
上 发 表 了 一 篇 文 章 《As We May Think》，提出一种信息机器的构想 机器内部用微缩胶卷存储信息，也就是自 动翻拍，可以不断添加新的信息；桌面上 有阅读屏，用来放大阅读微缩胶卷；还有 许多个按钮，每一个按钮代表一个主题， 按一下，相应的微缩胶卷就会显示
读者可以建立指向某些微缩胶卷片段的链 接，并依照自己的喜好形成新的线性顺 序，甚至加上自己的补充或评论。这些可
13 万维网结构 The Structure of the Web
1
万维网(Wan Wei Wang) World Wide Web
定义 The World Wide Web, is a system of interlinked hypertext documents accessed via the Internet. With a web browser, one can view web pages that may contain text, images, videos, and other multimedia, and navigate between them via hyperlinks. (Wikipedia) The web was developed between March 1989 and December 1990 by Tim Berneers-Lee. 起源 1989年3月，李撰写了《关于信息化管理的建议》一文，文中提及 ENQUIRE 并且描述了一个更加精巧的管理模型 1991 年 8 月 6 日，他在 alt.hypertext 新闻组上贴了万维网项目简介 的文章。这一天也标志着因特网上万维网公共服务的首次亮相
12
从有向图的角度看，Web宏观上是 个什么样子（“形状”）？
对于由巨量元素构成的事物，人们往往希 望能得到对其整体性态的有意义的刻画
13
万维网的“领结”结构
1999，Andrei Broder等发现万维网包含一个超大强
连通分量SCC，加上其他部分，显示出一种形象的结 构
链入，链出，卷须（管道），游离
计算领结结构的算法
FS={1, 3,4,5,
8,9,10, 13,14,15,16, 18} BS={1, 3,4, 6,7,8,9, 11,12,13,14,15, 18} SCC=FS∩BS= {1, 3,4, 8,9, 13,14,15, 18} IN=BS-SCC={6,7,11,12} OUT=FS-SCC={5,10,16} 2和17是卷须
SCC＝FS和BS的交集，即共同元素 IN（链入）＝BS－SCC OUT（链出）＝FS－SCC
16
基于G和G’，FS和BS，进一步集合运算可得到卷须和游离
计算领结结构的算法
从一个具体例子入手
FS={1, 3,4,5,
8,9,10, 13,14,15,16, 18} BS={1, 3,4, 6,7,8,9, 11,12, 自相似、层次性
21
本章要点
Web组织形式 尤其是对于表达信息之间的“引用关系”（“认可”关 系） 将万维网看成有向图 有向路径 强连通分量 万维网的“领结”结构 “领结” 领结结构的计算方法
• 广度优先搜索，基本集合运算
22
Q/A
23
以成为共享，他人只要键入建立链接的作 者的索引代码，就可以追溯到这些关联
9
将万维网看成有向图
节点：网页（可能用网址标识） 有向边：表示从一个节点到另一个节点的直接链
接关系；节点的出向边与入向边 有向路径：两节点之间边的方向一致的路径
节点A到B的距离：从A到B最短有向路径的长度 注意，从A到B的距离不一定等于从B到A的距离
在这个有向图数据上，实现了前述算法，一个程
序（在16 台机器上）运行了一周，得到了有关结 构形状的参数
20
网页: http://.../....html, (完整地址) 网站: http://.../*, 对应例如大学的一
个系
机构: http://*..../*, 对应例如一所大
学所有院系网站的集合