信息检索与数据挖掘 2019/5/13 17 Web特性→Web图特性 该有向图可能不是一个强连通(strongly connected)图，也 就说，从一个网页出发，沿着超链接前进，有可能永远不 会到达另外某个网页。我们将指向某个网页的链接称为入 链接(in-link),而从某个网页指出去的链接称为出链接 ( out-lik)。一个网页的入链接数目被称为这个网页的入度 (in-degree),在一系列研究中得到的网页的平均入度大概 从8到15左右不等。同样，我们可以定义某个网页的出链 接数目为其出度(out-degree) 。 B 6个网页（分别以A到F标识)，网页 B的入度为3、出度为1。该图不是强连 通图，因为B不可能到A C
信息检索与数据挖掘 2019/5/13 17 Web特性 Web图特性 • 该有向图可能不是一个强连通（strongly connected）图，也 就说，从一个网页出发，沿着超链接前进，有可能永远不 会到达另外某个网页。我们将指向某个网页的链接称为入 链接（in-link），而从某个网页指出去的链接称为出链接（ out-link）。一个网页的入链接数目被称为这个网页的入度 （in-degree），在一系列研究中得到的网页的平均入度大概 从8 到15 左右不等。同样，我们可以定义某个网页的出链 接数目为其出度（out-degree）。 6 个网页（分别以A 到F 标识），网页 B 的入度为3、出度为1。该图不是强连 通图，因为B 不可能到A
信息检索与数据挖掘 2019/5/13 18 Web特性→Web图特性 Web的形状 ·Strongly Connected Tendrils 44 Million Component (SCC) nCNIES Core ·Upstream(N) N SCC OUT ·Core can't reach IN ---- 4 Million nodes 56 Million noxdes 4 Million nodles ·Downstream(OUT) ·OUT can't reach core ·Disconnected ·Tendrils&Tubes Tubes Disconnected components
信息检索与数据挖掘 2019/5/13 18 Web特性 Web图特性 Web的形状 • Strongly Connected Component (SCC) • Core • Upstream (IN) • Core can’t reach IN • Downstream (OUT) • OUT can’t reach core • Disconnected • Tendrils & Tubes
信息检索与数据挖掘 2019/5/13 19 Web特性→Web图特性 小世界网络 It is a‘small world Millions of people.Yet,separated by “six degrees”of acquaintance relationships Popularized by Milgram's famous 1223 44】5561 experiment •Mathematically Diameter of graph is small (log N as compared to overall size Property seems interesting given sparse'nature of graph but...This property is 'natural'in pure'random It's a small world graphs Huge graph with small distance
信息检索与数据挖掘 2019/5/13 19 Web特性 Web图特性 小世界网络 •It is a ‘small world’ • Millions of people. Yet, separated by “six degrees” of acquaintance relationships • Popularized by Milgram’s famous experiment •Mathematically • Diameter of graph is small (log N) as compared to overall size • Property seems interesting given ‘sparse’ nature of graph but … This property is ‘natural’ in ‘pure’ random graphs Huge graph with small distance It’s a small world
信息检索与数据挖掘 2019/5/13 20 Web特性→Web图特性 无标度网络 站点大小Site Sizes(以页面数量计算)服从power law分布 ·跨越不同的规模 ·g在1.6-1.9之间 ·节点的度connections per node服从power law分布 Study at Notre Dame University reported g=2.45 for outdegree distribution 10 AOL users to sites .g=2.1 for indegree distribution 10 scale free Head 10 Xueindod Long tail Long Tail 10 10 103 10 number of users Products
信息检索与数据挖掘 2019/5/13 20 Web特性 Web图特性 无标度网络 • 站点大小Site Sizes（以页面数量计算）服从 power law 分布 • 跨越不同的规模 • g 在1.6-1.9之间 • 节点的度connections per node 服从power law 分布 • Study at Notre Dame University reported • g = 2.45 for outdegree distribution • g = 2.1 for indegree distribution scale free Long tail
信息检索与数据挖掘 2019/5/13 21 连接服务器 Web图在计算机中如何表示？ 。支持Web图上的快速查询 ·哪些URL指向给定的URL? B ·给定的URL指向哪些URL? 在内存中存储了映射表 ·URL到出链，URL到入链 •应用 。采集控制 .Web图分析 ·连通性Connectivity,采集优化 。链接分析Link analysis
信息检索与数据挖掘 2019/5/13 21 连接服务器 • 支持Web图上的快速查询 • 哪些URL指向给定的URL？ • 给定的URL指向哪些URL？ 在内存中存储了映射表 • URL到出链, URL到入链 • 应用 • 采集控制 • Web图分析 • 连通性Connectivity, 采集优化 • 链接分析Link analysis Web图在计算机中如何表示？