最新资讯

网络与图

2.1 基本概念

• 网络（Network）：通常指一个实际系统，使用“节点（node）”和“链接（link）”来描述。
• 图（Graph）：网络的数学表示，使用“顶点（vertex）”和“边（edge）”来描述。在大多数情况下，这两个术语可以互换使用。

2.2 图的起源

• 哥尼斯堡七桥问题：1736年，欧拉证明了无法一次性走遍七座桥且不重复。欧拉被视为“图论之父”。
• 关键结论：具有奇数个链接的节点必须是起点或终点，一条路径只能有一个起点和一个终点，而哥尼斯堡图有4个奇数链接的节点。

2.3 图的抽象与表示

图的定义：

图 ( G = (V, E) )，其中 ( V ) 是点集，( E ) 是边集。

顶点数 ( N = |V| )，边数 ( M = |E| )

图的类型：

按照性质分

• 无向图

• 有向图

• 简单图

  • 无多重边（No Multi-edge）
  • 无自环（No Self-edge）

• 完全图 ( K_N )：每对顶点之间都有一条边相连。

• …

2.4 图的计算机表示

• 邻接表（Adjacency list）
• 邻接矩阵（Adjacency matrix）
• 三元组

2.5 图的应用示例

文献共引与耦合:

大部分有向图可被转化为无向图来研究，因为 无向图研究更成熟

如：文献直接的引用关系是有向的，文献引用关系可以用来分析文献相关性，但是有向图较为复杂，可转化为文献共引与耦合的无向图来分析

文献的共引和耦合都能在一定程度上反映两篇文献在研究主题、内容或方向上的相关性。如果两篇文献之间存在强共引或强耦合关系，说明它们在学术研究中具有一定的关联性，可能在相同或相关的研究领域内对相关问题进行了探讨。

文献共引：

• 两文献被共同引用时，以两文献为点建一无向边链接。
• 两篇文章都有大量被引用时才可能是强共引。
• 强共引反映了两篇文献在学术研究中的共同价值和重要性。

文献耦合：

• 两文献共同引用大量相同文献时，以两文献为点建一无向边链接。
• 有两篇文章都引用大量文章才可能是强耦合。
• 强耦合表明它们在相同或相关的研究领域内具有一定的关联性和一致性。

2.6 图的基本性质

• 路径（Path）：从一个顶点到另一个顶点的边的序列。
• 回路（Circuit）：起点与终点重合的路径。
• 简单路径（Simple Path）：路径中的各个顶点互不相同。
• 圈（Cycle）：起点与终点重合且经过的顶点互不相同的路径。
• 连通性（Connected）：图中每一对顶点之间都存在路径。
• 不连通（Disconnected）：图包含多个连通片。
• 连通片（Connected component）：图中的一个孤立子图，该子图内部是连通的。
• 最大连通片（Maximal connected component）：图中最大的连通子图。

2.7 路径与连通性的邻接矩阵表示

• 节点 $i$ 和 $j$ 之间长度为 $r$ 的不同路径数量可以通过矩阵 $A^r$ 的元素 $(A^r{)}_{ij}$ 计算。

  这里，$A$ 是图的邻接矩阵。邻接矩阵 $A$ 的元素 $A^{ij}$ 表示节点 $i$ 和 $j$ 之间是否存在一条直接的边。如果存在，$A^{ij}=1$ ；否则，$A^{ij}=0$。矩阵 $A^r$ 的元素 $(A^r{)}_{ij}$ 表示从节点 $i$ 到节点 $j$ 长度为 $r$ 的路径数量。这是因为矩阵乘法的性质使得 $A^r$ 的每个元素$(A^r{)}_{ij}$等于所有可能的长度为 $r$ 的路径的和。

• 节点 $i$ 和 $j$ 之间距离不超过 $r$ 当且仅当 $ (I + A + A^2 + dots + A^r)_{ij} > 0$ 。

  这里，$I$ 是单位矩阵。矩阵 $I+A+A^2+\cdots +A^r$ 的元素 $(I+A+A^2+\cdots +A^r{)}_{ij}$ 表示从节点 $i$ 到节点 $j$ 长度不超过 $r$ 的路径数量。如果这个元素大于$0$，那么就存在至少一条从 $i$ 到 $j$ 长度不超过 $r$ 的路径，即 $i$ 和 $j$ 之间的距离不超过 $r$。

• 图是连通的当且仅当 $ (I + A + A^2 + dots + A^{N-1})_{ij} > 0 $。

  这里，N 是图中节点的数量。矩阵 $I+A+A^2+\cdots +A^{N-1}$ 的元素$(I+A+A^2+\cdots +A^r{)}_{ij}$ 表示从节点 $i$ 到节点 $j$ 长度不超过 $N-1$ 的路径数量。如果这个元素大于 $0$，那么就存在至少一条从 $i$ 到 $j$ 的路径，即图是连通的。因为在一个有 $N$ 个节点的图中，任意两个节点之间的最短路径长度最多为 $N-1$。

2.8 图的割集与连通性

• 割集（Cut Set）：从图中移除某些顶点或边以分离两个顶点。
  • 点割集：移除顶点的最少数目。
  • 边割集：移除边的最少数目。
• 极小割集（Minimum Cut Set）：最小的割集。

2.9 有向图的连通性

• 强连通（Strongly connected）：有向图中每对顶点之间都存在双向路径。
• 弱连通（Weakly connected）：将有向图视为无向图后是连通的。

2.10 树与生成树

• 树（Tree）：无圈且连通的图，具有以下性质：
  • 连通且有 ( N-1 ) 条边。
  • 不包含圈且有 ( N-1 ) 条边。
  • 任意两个顶点之间有且只有一条路径。
  • 任意一条边都是桥。
• 生成树（Spanning Tree）：包含图的所有顶点的树。
• 最小生成树（Minimum Spanning Tree, MST）：边的权值之和最小的生成树。
  • 应用：在若干个地点之间建设连通网络，使建设代价最低。
  • 算法：利用图的特性，如割集性质（Cut property）和圈性质（Circle property）。

2.11 最小生成树算法

Kruskal算法：

该算法的本质是贪心，更适用于稀疏图。

基本思路：

• 把边按照权值进行排序
• 用贪心的思想优先选取权值较小的边，并依次连接
• 若出现环则跳过此边（用并查集来判断是否存在环）继续搜，直到已经使用的边的数量比总点数少一。

以洛谷P3367为例：

int n, m; 		// n 个节点，m 条边
int f[5010];	

struct line{
	int x, y, w;
}l[200010];//直接存边以便排序

bool cmp(line a, line b){ return a.w < b.w; } //用于sort函数的比较函数

int find(int x){
	if(x==f[x]) return f[x];	//基于状态压缩的并查集，用于检查是否成环
	else return f[x] = find(f[x]);
}


int kruskal(){		//核心代码
	
	int ans=0, cnt=0;
	for(int i=0 ; i<m ; ++i){
		int rtx = find(l[i].x);
		int rty = find(l[i].y);
		if(rtx == rty) continue;
		else{
			++cnt;
			ans += l[i].w;
			f[rtx] = rty;
		}
		if(cnt==n-1) return ans;
	}
	return 0;
}

局限性：

• 距离问题：MST可能无法满足两点之间最大距离或平均距离尽可能小的要求。
• 流量问题：MST可能导致某条边流量过大，造成拥塞。
• 鲁棒性问题：从MST中去除任意一条边后，图将变得不连通。

2.13 二分图与匹配

二分图（Bipartite Graph）：

图的顶点可以分为两个不相交的集合，每条边连接一个集合中的顶点到另一个集合中的顶点。

• 完全二分图（Complete Bipartite Graph）：两个集合中的每个顶点都与其他集合中的每个顶点相连。
• 从属网络（Affiliation Network）：表示实体之间的从属关系。
• 二模网络（Two-mode Network）：表示两种不同类型实体之间的关系。

匹配（Matching）：

图中任意两条边都没有公共端点。

• 最大匹配（Maximal Matching）：边数最多的匹配。
• 完全匹配（Perfect Matching）：既是X又是Y的完全匹配，顶点一一对

应用：

师生分配、婚姻匹配、工作招聘、任务分配等。、

2.14 社会网络中的弱连接

• 弱连接的桥梁作用：弱连接可以桥接社会距离。

  • 局部桥（Local Bridge）：如果节点A和B没有共同的邻居节点，则边A-B是局部桥。
  • 局部桥的跨度（Span）：去除边A-B后，节点A和B之间的距离。
  • 强三元闭合（Strong Triadic Closure）：如果一个人A有两个亲密朋友B和C，那么B和C也很有可能互相认识。
  • 弱连接与强连接：在社会网络中，弱连接在信息传播中起重要作用，因为它们数量众多。

2.15 平衡理论

• 平衡理论（Balance Theory）：描述了社会关系中的平衡状态。
  • 朋友的朋友是朋友；朋友的敌人是敌人；敌人的朋友是敌人；敌人的敌人是朋友。
• 平衡图：图中所有三角关系都是平衡的。
• 应用：分析社会网络中的关系动态。

---

网络基本拓扑性质

3.1 图论与网络科学

• 图论：关注图的结构特性，例如割点（Cut-vertex）或桥（Bridge），即去除哪个顶点或边会使图从连通变为不连通。
• 网络科学：研究网络的宏观特性，例如去除多少比例的节点或边会对网络连通性产生大的影响。图论多采用精确方法，而网络科学多采用统计方法。

3.2 复杂系统的特性

• More is Different：大量粒子组成的复杂系统的行为不能简单地通过少量粒子的性质进行外推。在每个复杂性层次上，都会出现全新的性质，需要进行基础性的研究来理解这些新行为，即整体不仅仅是部分的简单相加，而是有着本质的不同。
• 大数据与网络科学：随着传感器无处不在、存储技术的飞速发展以及云计算的普及，产生了海量的数据。网络科学在处理这些大数据时发挥着重要作用，例如分析社交网络、互联网等大规模网络的结构和特性。

3.3 网络的Bow-tie结构

弱连通巨片在网络中通常占据较大比例，而Bow-tie(蝴蝶结)结构是前者的常见结构形式

有向网络的蝴蝶结结构由4部分组成：

• 强连通核（SCC）
• 入部（IN）
• 出部（OUT）
• 卷须部（TENDRILS）

这四部分构成了一个类似蝴蝶结的图

3.4 网络的度相关特性

平均度：

• 定义为网络中所有节点的度的平均值，公式为：
  $⟨k⟩=\frac{1}{N}{\sum }_{i=1}^N{k}_i=\frac{1}{N}{\sum }_{i=1}^N{\sum }_{j=1}^N{a}_{ij}$
• 其中，(N)为节点总数，(k_i)为节点(i)的度，(a_{ij})为邻接矩阵的元素，表示节点(i)和节点(j)之间是否存在边。

有向网络的出度和入度：

• 出度（Out Degree）：
  $ k_{out} = sum_{j=1}^{N} a_{ij}$

• 入度（In Degree）：
  $ k_{in} = sum_{j=1}^{N} a_{ji}$

• 对单个节点而言，出度未必等于入度，但对整个网络，出度之和一定等于入度之和。

加权网络的强度：

• 有向加权网络：
  • 出强度（Out Strength）：
    $
    s_{out} = sum_{j=1}^{N} w_{ij}$
  • 入强度（In Strength）：
    $
    s_{in} = sum_{j=1}^{N} w_{ji}
    $
• 无向加权网络：
  $s_i={\sum }_{j=1}^N{w}_{ij}$
  其中，$w_{ij}$ 表示节点 $i$ 和节点 $j$ 之间的权重。

3.5 网络的稀疏性与稠密性

稠密网络：

每个节点都与其他所有节点相连，即$k=N-1$，边的数量$M\sim O(N^2)$。

稀疏网络：

实际网络通常是稀疏的，即平均$⟨k⟩\ll N-1$，边的数量$M\ll O(N^2)$。例如：

• Facebook：$N=7.21\times 10^8$，$M=687\times 10^9$，$⟨k⟩=190$，密度$\rho =0.3\times 10^{-7}$
• WWW（ND Sample）：$N=325,729$，$M=1.4\times 10^6$，$M_{max}=10^{12}$，$⟨k⟩=4.51$

网络密度：

• 稠密网络模型：密度$\rho$趋于非零常数（当$N\to \infty$）。
• 稀疏网络模型：密度$\rho$趋于零（当$N\to \infty$）。
• 密度公式：
  $\rho =\frac{2M}{N(N-1)}$

3.6 网络的路径特性

平均路径长度：

• 定义为网络中所有节点对之间最短路径长度的平均值，公式为：
  $L=\frac{1}{N(N-1)}{\sum }_{i\ge j}{d}_{ij}$
• 其中，(d_{ij})表示节点(i)和节点(j)之间的最短路径长度。
• 另一种定义方法是网络中两点之间距离的“调和平均”：
  $L=\frac{1}{G_E}=\frac{1}{\frac{1}{N(N-1)}{\sum }_{i\ge j}\frac{1}{d_{ij}}}$
  对于不连通网络，$L$为无穷大。

网络直径：

网络中任意两个节点之间的最长最短路径长度，即：$D=\max (d_{ij})$

有效直径：

距离不超过$D$的连通节点对的比例$g(D)=0.9$。

单源最短路径算法：

Dijkstra

1. 初始化

   • 距离数组：设置起点的距离为0，其他节点的距离为无穷大（∞）。

   • 优先队列：将起点及其距离（0）加入优先队列。

2. 主循环

   • 取出最小距离节点：从优先队列中取出距离最小的节点（当前节点）。

   • 遍历邻居：遍历当前节点的所有邻居节点。

   • 更新距离：对于每个邻居节点，计算从当前节点到该邻居的新距离。如果新距离小于已知距离，则更新距离，并将该邻居节点及其新距离加入优先队列。

3. 终止条件

   • 当优先队列为空时，算法结束。此时，距离数组中存储的即为从起点到各节点的最短距离。

typedef long long ll;
struct edge{
	ll w;
	int v;
};

class Compare{
	public:
		bool operator() (edge a, edge b) const {
			return a.w > b.w;
		}
};

int n, m, s; 				// 顶点数n，边数m，源点s
ll dist[100005]; 			//存储源点到每个点的距离
vector<edge> graph; 	//存储边权和顶点编号


void dijkstra(){
	for(int i=1 ; i<=n ; ++i) dist[i]=LLONG_MAX; 		   //将每个点的值变为无穷大
	dist[s] = 0;										//初始化源点
	
	priority_queue<edge, vector<edge>, Compare> pq;	    //建一个最小堆
    edge temp = {0,s};
	pq.push(temp);				//存入源点的信息
	
	while(!pq.empty()){									//形似BFS
		ll dis = pq.top().w;
		int u = pq.top().v;						//对于每一个节点，访问其邻居节点并更新距离
		pq.pop();
		
		if(dis > dist[u]) continue;
		for(int i=0 ; i<(int)graph[u].size() ; ++i){
			auto edge = graph[u][i];
			int v = edge.v;
			ll w = edge.w;
			if(dist[u] + w < dist[v]){
				dist[v] = dist[u]  + w;
                temp = {dist[v],v};
				pq.push(temp);
			}
		}
	}
}

3.7 网络的聚类特性

• 聚类系数：
  • 节点(i)的聚类系数：
    $C_i=\frac{2E_i}{k_i(k_i-1)}$
    其中，$E_i$为节点$i$的$k_i$个邻居节点之间实际存在的边数。
  • 网络的聚类系数：
    $C=\frac{1}{N}{\sum }_{i=1}^N{C}_i$
• 聚类系数的另一种定义：
  • 节点(i)的聚类系数：
    $C_i=\frac{\text{包含节点}i\text{的三角形的数目}}{\text{以节点}i\text{为中心的连通三元组的数目}}$
  • 网络的聚类系数：
    $C=\frac{1}{N}{\sum }_{i=1}^N{C}_i$
• 聚类系数与度的关系：
  • 度为(k)的节点的聚类系数的平均值(C(k))通常与(k)的幂律关系有关，即：
    $C(k)\sim k^{-\beta }$
  • 低度节点（小(k)）通常具有较高的聚类系数，它们的邻居倾向于相互连接，形成紧密的社区；高度节点（大(k)，即枢纽节点）通常具有较小的聚类系数，它们连接不同的独立社区。

3.8 网络的度分布

度分布：

网络中随机选取的一个节点的度为(k)的概率(P(k))。

常见度分布类型：

正态分布：

$f(x)=\frac{1}{\sqrt{2\pi {\sigma }^2}}{e}^{-\frac{(x-\mu {)}^2}{2{\sigma }^2}}$

泊松分布：

$P(k)=\frac{{\lambda }^k{e}^{-\lambda }}{k!}$

无标度分布：

• 特点：大部分节点的度很小，少数节点的度很大。

• 80/20法则：管好少数节点，可以带动（或忽略）多数节点。

• 长尾分布：多数“小”节点的累积作用也不可忽视。

• 幂律分布：
  $P(k)=C{k}^{-\gamma }$
  取对数后：
  $lnP(k)=lnC-\gamma lnk$

• 幂律分布的性质：

  • 当$\gamma >3$时，具有有限均值和有限方差。
  • 当$2<\gamma \le 3$时，具有有限均值，但没有有限方差。大部分具有幂律度分布的实际网络的幂指数都处于这一区间。
  • 当$\gamma >1$时，为概率分布；当$\gamma >2$时，具有有限均值；当$\gamma >3$时，具有有限二阶矩。

• 举例：

  • WWW：$⟨k⟩=7$，方差为无穷大。

  • Internet：$⟨k⟩=3.5$，方差为无穷大。

  由于这些网络的方差很大，平均值可能没有实际意义，因为波动太大。

• 最大度的估计：

  • 假设网络中有$N$个节点，最大度为$K_{max}$，则有：
    $P(k>K_{max})\le \frac{1}{N}$
  • 根据幂律分布的累积分布函数：
    ${\int }_{K_{max}}^{\infty }C{k}^{-\gamma }dk=\frac{1}{N}$
  • 解得：
    $K_{max}\approx N^{\frac{1}{\gamma -1}}$

---

计算机网络基础

4.1 计算机网络概述

应用：

• 商业应用：
  1. 公司内部资源共享
  2. 通信媒介（如Email、视频会议）
  3. 电子商务（B2B、B2C等）。
• 个人与家庭用户：
  1. 访问远程信息（如WWW、在线图书馆）
  2. 个人通信（如IM、聊天室、P2P通信等）
  3. 娱乐（如视频点播、游戏）
  4. 电子商务（如B2C、C2C等）。
• 移动用户：
  1. 移动办公（如PDA、手机）
  2. 军事网络、城市管理（如无线停车计时器）
  3. 位置服务（如导航、地图）
  4. 增强现实（如超市比价、实景游戏等）。

产生和发展：

• 第一代（195X）：面向终端的计算机网络。
• 第二代（1968）：以分组交换网为中心的计算机网络（如ARPNET）。
• 第三代（197X-198X）：体系结构标准化的计算机网络（如OSI/RM）。
• 第四代（199X）：以网络互连为核心的计算机网络（如Internet）。

定义：

将地理位置不同、具有独立功能的多个计算机系统通过通信设备和线路连接起来，以功能完善的网络软件实现网络中计算机之间的数据通信和资源共享的系统。

功能：

资源共享、均衡负载及分布处理、信息快速传递和集中处理、综合信息服务、提高系统的性能价格比、维护方便、扩展灵活。

4.2 计算机网络组成

网络硬件：

资源子网：

资源子网主要依赖于计算机硬件（如服务器、客户机、终端设备等）来提供和管理资源。这些硬件设备通过网络连接在一起，形成一个资源共享的环境。

• 服务器：网络的核心，负责网络资源管理和用户服务。

• 工作站：网络上的个人计算机，通过网卡和通信电缆连接到服务器。

• 网络终端设备：如打印机、扫描仪等，这些设备通过网络连接到服务器或客户机，实现资源共享。

通信子网：

通信子网主要依赖于网络连接设备和传输介质来实现数据的传输和通信控制。这些设备和介质共同构成了网络的通信基础设施，确保数据能够在网络中高效、可靠地传输。

• 网络连接设备：

  • 网络接口卡（网卡）：计算机与通信介质的接口，有唯一MAC地址。

  • 交换机：交换机用于连接多个网络设备，并根据数据帧中的MAC地址来转发数据。

  • 路由器：路由器用于连接不同的网络，如局域网与广域网、不同的局域网等。

  • 集线器：用于连接多个网络设备，它将接收到的数据信号广播到所有连接的设备上。

  • …

• 通信介质（有线）：

  • 双绞线：点到点通信距离一般不超过100m，连接器为RJ-45。
  • 同轴电缆：屏蔽性较好，带宽较高，常用于有线电视网和城域网。
  • 光缆：带宽高、衰减低、抗干扰性强、细小轻、安全性高，分为单模、多模光纤。
  • 磁介质：银行异地灾备常采用，通过物流运输磁盘，成本低，传输带宽高。

网络软件：

网络操作系统：

• 网络操作系统是运行在网络硬件基础之上的，为网络用户提供共享资源管 理服务、基本通信服务、网络系统安全服务及其他网络服务的软件系统。
• 网络操作系统是运行在网络硬件基础之上的，为网络用户提供共享资源管 理服务、基本通信服务、网络系统安全服务及其他网络服务的软件系统。

网络协议软件：

• 网络协议是在计算机网络中两个或两个以上计算机之间进行信息交换的规 则，它包括一套完整的语句和语法规则。
• 比较流行的协议有IPX/SPX、TCP/IP（Internet的协议）等

4.3 计算机网络分类与架构

拓扑结构

网络的拓扑结构是指网络中通信线路和站点（计算机或设 备）的相互连接的方法和几何形式。

1. 星型拓扑结构：

以一个节点为中心的处理系统，各种类型的入网计算机均与该中心有物理链路直接相连。

• 优点:

  • 可靠性高
  • 方便服务
  • 故障诊断容易

• 缺点:

  • 安装费用高
  • 扩展困难
  • 对中央节点依赖性强。

2. 总线形拓扑结构：

将所有的入网计算机均通过相应的硬件接口直接接入到 一条通信线路上。为防止信号反射，一般在总线两端有终结匹配器。

• 优点：

  • 布线容易
  • 电缆用量小
  • 可靠性高
  • 易于扩充和安装

• 缺点：

  • 故障诊断和隔离困难
  • 通信介质或中间接口点故障会导致网络瘫痪
  • 终端必须是智能的。

3. 环型拓扑结构：

将各台联网的计算机用通信线路连接成一个闭合的环。信息按照固定方向流动，每个计算机有自己的顺序编号接力传递信息。

• 优点：

  • 电缆长度短
  • 适用于光纤
  • 无差错传输

• 缺点：

  • 可靠性差
  • 故障诊断困难
  • 调整网络比较困难。

4. 树型拓扑结构：

是总线型的扩展，在总线网上加上分支形成。其传输介质有多条分支，但无闭合回路；也可以看成是星型结构的叠加。具有层次结构。也是因特网的拓扑结构。

• 优点：

  • 结构简单
  • 成本低
  • 每个链路支持双向传
  • 点扩充方便灵活、寻找链路路径方便

• 缺点：

  • 任何一个故障都会影响整个系统
  • 对根的依赖性太大。

计算机网络分类

• 按规模及覆盖范围：
  • 个人区域网（PAN）
  • 局域网（LAN）
  • 城域网（MAN）
  • 广域网（WAN）
  • 因特网
• 从通信技术角度：
  • 广播型网络
  • 点到点型网络。
• 从交换方式角度：
  • 电路交换网
  • 报文交换网
  • 分组交换网
• 按服务对象：
  • 公用网
  • 专用网。

网络的分类细节

传输技术

• 广播网络：只有一个信道，所有机器共享，传递的是分组或包，分组中有地址域，可广播或多播。
• 点到点网络：由多个连接构成，每个连接对应一对机器，传送分组需经过路径，有时称单播。

一般来说小的网络采用广播，大的网络采用点到点。

距离尺度/覆盖范围

• 个人区域网络：仅供一个人使用的网络，如无线连接计算机与外设或个人医用设备等。
• 局域网：公司、校园等专用网络，覆盖范围小，传输距离和时间短，常采用统一传输技术，多种拓扑结构，协议和结构简单。
• 城域网：覆盖城市，如有限电视网，随着Internet发展可用于接入Internet。
• 广域网：跨越大区域，包含大量主机，主机通过通信子网连接，子网中包含传输线和交换单元，间接通信采用存储-转发或分组交换原则，也有卫星系统组成的WAN使用广播通信。

交换方式

• 电路交换：最早出现的交换方式，应用于电话通信网
  • 优点：独占性、实时性、可靠性
  • 缺点：连接建立慢、资源利用率低、兼容性差。
• 报文交换：以报文为数据交换单位，采用存储转发传输方式
  • 优点：无连接建立时延、可切换路径、兼容性好、提供多目标服务、允许建立数据传输优先级、提高通信线路利用率
  • 缺点：转发时延长、缓冲需求大、实时性差、错误开销大、容错率低。
• 分组交换：仍采用存储转发传输方式，将长报文分割为若干分组发送
  • 优点：分组间转发和存储并行、提高速度、简化存储管理、提高容错性、减少重发数据量
  • 缺点：存在转发时延、增加冗余信息、需额外处理失序、丢失和重复分组。

计算机网络的体系结构

• 分层结构：计算机网络采用分层结构，每一层在其下一层提供的功能基础上，实现为上一层提供的功能，底层功能弱，高层功能强。
• 分层的优点：各层之间独立、灵活性好、结构可分割、易于实现和维护、能促进标准化工作。

类比于邮件系统的分成结构：

• 用层次结构构建复杂系统——服务
• 垂直调用和逐层封装——接口
• 两端每一层之间都有相应的约定

ISO参考模型（OSI七层模型）

背景：不同厂商产品体系结构不同，给网络互连造成困难，ISO于1977年成立专门机构研究，1981年颁布OSI/RM。

层级：共7层，从下往上分别是物理层、数据链路层、网络层、传输层、会话层、表示层和应用层。

数据传输方向：接受数据时自下而上，发送数据时自上而下。

各层功能及协议:

• 物理层：提供网络的物理连接。
• 数据链路层：以帧为单位传输数据，进行数据封装和数据链路的建立，功能包括数据链路的分裂、定界、同步，流量控制，差错检验和恢复，相关设备有Hub、Modem。
• 网络层：提供路由功能，建立拆除网络连接，路径选择和中继，多路复用，传输及流量控制。
• 传输层：解决数据在网络之间的传输问题，提高传输质量，实现可靠的端到端传输，功能包括映像传输地址到网络地址，多路复用与分割，传输连接管理，分段（块）与组装。
• 会话层：提供会话服务，令牌管理和活动管理。
• 表示层：管理不同数据表示。
• 应用层：应用程序通信协议（如FTP、SMTP、POP3）。

TCP/IP体系结构：

• 层级：采用4层体系结构，从上到下依次是应用层、传输层、网际层和网络接口层。
• 与OSI模型对应关系：
  • 应用层：对应OSI的表示层和应用层，协议有Telnet、FTP、SMTP、DNS、HTTP等。
  • 传输层：对应OSI的传输层，协议有TCP、UDP等。
  • 网际层：对应OSI的网络层，协议有IP、ARP、RARP、ICMP等。
  • 网络接口层：对应OSI的数据链路层和物理层，包含各种通信网络接口（如以太网、令牌环、帧中继、ATM等）。
• 协议重点：TCP/IP协议集中最重要的是传输控制协议（Transmission Control Protocol，TCP）和网际协议（Internet Protocol，IP）
• TCP负责发现传输问题并要求重传，IP为数据报在Internet上的发送、传输和接收制定规则。
• TCP/IP体系结构的目的是实现网络间的互连，现已成为网络互连的 工业标准。目前流行的网络操作系统都已包含了上述协议，成了标 准配置。

TCP/IP在传输层定义了两个端到端的传输协议：

• 传输控制协议（ Transmission Control Protocol ， TCP）：一个可靠的， 面向连接的协议，允许从一台机器上发出的字节流正确无误的递交到互联网上的另一台机器上。
• 用户数据报协议（User Datagram Protocol， UDP）：一个不可靠的，无连接的协议，主要用于那些“不想要TCP的序列化或流控制功能，而希望自己提供这些功能”的程序。往往用于一些“快速递交比精确递交更重要”的应用，如语音、视频传输等。

OSI模型及TCP/IP模型的评价：

• OSI模型：曾被看好，但实际未统治领域，错误和教训包括糟糕的时机（TCP/IP已广泛应用）、技术（数据链路和网络层复杂，会话和表示层简单）、实现（最初实现庞大笨拙）、政策（试图将不完善标准强加给研究人员和程序员）。
• TCP/IP模型：协议被广泛使用，但模型并不重要，缺点是没有很好区分服务、接口和协议的概念，不通用（如无法描述蓝牙通信网络），没有区分数据链路层和物理层。

4.4 数字通信基础

• 数据传输速率：描述数据传输系统的主要技术指标之一，数值上等于每秒传输二进制位数，单位为bps。
• 带宽与数据传输速率：现代网络技术中，带宽常用来表示信道的数据传输速率，但带宽不等于数据传输速率。
• 误码率：衡量数据在规定时间内传输精确性的指标。
• 时延：从终端A发送第一位数据到终端B接收最后一位数据的时间间隔，包括发送时延（数据块长度/信道带宽）、传播时延（d/s）和处理时延。

4.5 局域网基础

概述

• 特点：共享传输信道、范围有限（一般在几公里内）、传输速度高（目前常用100Mbps）、工作可靠、误码率低。
• 拓扑结构：常用星型、环型和总线型，交换技术发展使星型拓扑结构广泛应用。
• 体系结构：使用IEEE 802标准，最常用的是IEEE 802.3（以太网）和IEEE 802.11（无线局域网），体系结构由物理层、介质层和逻辑链路控制子层组成。
• 载波侦听多路访问/冲突检测协议（CSMA/CA）：介质访问控制技术，是局域网重要基本技术，包括确定节点发送信息的特定时刻和对公用传输介质进行访问、利用和控制。

常用局域网简介

• 以太网：采用IEEE 802.3标准组建，是有线局域网，技术成熟、应用广泛。
• 无线局域网：采用IEEE 802.11标准组建，是无线局域网，目前还不能完全脱离有线网络，是有线网络的扩展和补充，包括对等无线网络和结构化无线网络。

CSMA/CA主要内容

CSMA/CA（Carrier Sense Multiple Access with Collision Avoidance）即带有冲突避免的载波侦听多路访问，是一种用于无线局域网（WLAN）的介质访问控制（MAC）协议。

协议流程：

1. 侦听信道（Carrier Sense）：在发送数据之前，设备首先会侦听信道，检测是否有其他设 备正在发送数据。如果信道被占用，设备将等待一段时间再次尝试。
2. 随机等待时间：如果信道忙碌，设备会等待一段随机生成的时间。这个随机等待时间的 目的是避免多个设备同时尝试发送数据，从而减少碰撞的可能性。每个设备会选择不同的等 待时间，以增加公平性。
3. 清空信道：一旦设备完成了随机等待时间，它会再次侦听信道。如果信道仍然忙碌，设 备将继续等待和随机等待。如果信道变为空闲，设备将发送数据。
4. 数据发送：一旦设备确定信道空闲，它将发送数据。其他设备在接收到数据之前会继续 侦听信道，以确保不会发生碰撞。
5. 确认和重传：接收设备会发送确认信号来确认接收到的数据。如果发送设备没有收到确 认，它将认为数据丢失，并尝试重新发送。

作用： 用于局域网、无线局域网及其它网络中。它通过侦听信道、随机等待时间和数据发送等步骤， 确保多个设备之间的公平竞争和数据传输的可靠性。

3.6 网络标准化

• 必要性：多种网络生产、供应商有自己的思路和方法，需标准化以便不同计算机通信，还能扩大产品市场，带来规模经济等好处。
• 标准类型：
  • 事实标准（De facto）：已发生但未正式计划的标准，如IBM PC是小型、家庭计算机的事实标准。
  • 法定标准（De jure）：权威标准化组织采纳的正式、合法标准。
• 相关组织：
  • 国际电信联盟（ITU）：1865年诞生，对电报等进行标准化，包含无线通信部门ITU-R、电信标准化部门ITU-T、开发部门ITU-D，ITU-T有众多成员部门。
  • 国际标准组织（ISO）：1946年成立，自愿、非条约性质，成员有89个成员国的国家标准组织，制定大量学科标准，与ITU-T联合避免出现不兼容国际标准，成员包括ANSI等。
  • 电气和电子工程师协会（IEEE）：是电子电气等领域最大的专业技术学会，802委员会制定多种LAN标准，如802.3以太网、802.11无线LAN、802.15蓝牙等。
• Internet标准领域：全球性Internet有与ITU-T和ISO不同的标准化机制，早期有Internet活动委员会（IAB），其标准通过RFC技术报告发布交流，1989年IAB重组为研究任务组（IRTF）和工程任务组（IETF）。
• 万维网标准化组织：
  • 万维网联盟（W3C）：1994年创建，是Web技术领域最具权威和影响力的国际中立性技术标准机构，已发布200多项Web技术标准及实施指南，由Web发明者Tim Berners-Lee及首席执行官Jeffrey Jaffe领导，由四个全球总部联合运营。
• ACM（美国计算机协会）：
  • 1947年创立，是世界上最大的科学及教育型计算机学会，专注计算机科学与技术创新发展。
  • 每年ACM图灵奖影响力大，2000年度图灵奖授予姚期智。
  • 分设35个特殊兴趣组，关注不同领域技术发展。
  • ACM数字图书馆提供学术会议和期刊的学术论文。
  • ACM国际学术会议影响力大，如SIGCOMM、MOBICOM体现网络和无线网络领域全球最高水平。
  • ACM国际大学生程序设计竞赛展示大学生创新能力、团队精神等。
• 计算机网络三大顶级会议：
  • SIGCOMM：ACM数据通信专业组会议。
  • MobiCom：ACM移动计算和网络国际会议。
  • INFOCOM：IEEE计算机通信国际会议。
  • 这三大会议长期被中国计算机学会（CCF）推荐为A类国际学术会议。

---

因特网基础

5.1 因特网概念

Internet基础

• 定义：Internet是目前世界上覆盖面最广、最成功的国际计算机网络。它将世界各地的局域网（LAN）、城域网（MAN）和广域网（WAN）按照层次关系连接在一起，形成一个逻辑网络。
• 中文名称：1997年，我国正式确定中文名称为“因特网”。

Internet的起源和发展

• Internet概况

  • 1969年，第一个远程分组交换网ARPANET正式问世。
  • 1984年，ARPANET分解成两个网络：民用科研网ARPANET和军用计算机网络MILNET。
  • NSFNET接管了ARPANET，并将其改名为Internet。
  • 1996年，美国发起下一代高速互联网及其关键技术的研究，代表性项目为Internet2计划，目标是筹建一个最高传输速度达100Gbps的新网络。

• Internet在中国

  • 1987～1993年：Internet在中国的起步阶段。

  • 1994年至今：Internet在中国进入飞速发展时期。

  • 目前，国内已建成十大主干网络，并与Internet连通，包括：

    中国科学技术网（CSTNET）

    中国教育和科研网（CERNET）

    中国公用计算机互联网（ChinaNet）

    中国联通互联网（UNINET）

    中国网通公用互联网（CNCNET）

    中国移动互联网（CMNET）

    宽带中国（China169）

    中国长城互联网（CGWNET）

    中国卫星集团互联网（CSNET）

    中国国际经济贸易互联网（CIETNET）

5.2 因特网地址

IP地址

定义：IP协议中给因特网上的每台计算机和其他设备规定的一个唯一地址，称为“IP地址”。

格式

• IPv4：32位，分为4个字节，每个字节对应一个0~255的十进制整数，形如“×××.×××.×××.×××”。采用这种编址方法，Internet可以容纳约40亿台计算机同时上网。
• IPv6：使用128位IP编址方案，共有$2^{128}$个IP地址，采用冒号十六进制表示，例如FDEC:BA09:7695:3815:ADBD:BB67:2922:37B3。

类型

• A类地址：
  • ip范围：001.x.y.z — 126.x.y.z
  • 网络地址占8位，主机地址占24位
  • 可分配$2^7-2=126$个网络地址
  • 可支持$(2^{24}-2)$台主机
• B类地址：
  • ip范围：128.x.y.z — 192.x.y.z
  • 网络地址占16位，主机地址占16位
  • 可分配$2^{14}-2$个网络地址
  • 可支持$(2^{16}-2)$台主机
• C类地址：
  • ip范围：192.x.y.z — 223.x.y.z
  • 网络地址占24位，主机地址占8位
  • 可分配$2^{21}-2$个网络地址
  • 可支持$(2^8-2)$台主机。
• D类地址：组播地址，用于多播通信。
• E类地址：保留作为研究使用。

保留地址：由于地址资源紧张，A、B、C类IP地址中预留部分保留地址段，这些地址不能在Internet上使用，但可以在局域网内重复使用。采用NAT技术接入Internet。保留地址段如下：

• A类：10.0.0.0～10.255.255.255（1个网络）
• B类：172.16.0.0～172.31.255.255（16个网络）
• C类：192.168.0.0～192.168.255.255（256个网络）

网络逻辑地址与物理地址：

在局域网中，数据帧是通过MAC地址进行传输的。当一个设备要发送数据帧给另一个设备时，它会在数据帧的头部添加目标设备的MAC地址。交换机根据MAC地址表来转发数据帧。MAC地址是固化在网卡硬件中的，一般情况下不能更改。它与设备的硬件紧密相关，不像IP地址那样可以根据网络环境进行灵活配置。IP地址的作用范围是整个互联网，它可以使不同网络中的设备能够相互通信。例如，一个用户可以通过IP地址访问位于世界各地的网站服务器。而MAC地址的作用范围仅限于局域网内部。当数据包从一个局域网发送到另一个局域网时，虽然数据帧的MAC地址在局域网内部起作用，但IP地址才是决定它跨网络传输的关键因素。

子网掩码

定义：子网掩码是一个32位的二进制数，用于区分IP地址中的网络部分和主机部分。

格式：子网掩码由一连串的“1”和一连串的“0”组成。其中“1”对应于网络地址和子网地址，而“0”对应于主机地址。例如，子网掩码255.255.248.0对应的二进制为11111111 11111111 11111000 00000000。

默认子网掩码：

• A类地址：255.0.0.0
• B类地址：255.255.0.0
• C类地址：255.255.255.0

作用：

• 区分计算机是在本地网络还是在远程网络上。如果两台计算机的IP地址和子网掩码“与”运算结果相同，则表示两台计算机处于同一网络内。
• 快速确定IP地址的哪部分代表网络号，哪部分代表主机号，以及判断两个IP地址是否属于同一网络。

子网划分：单位可以根据需要将分配到的IP地址划分为若干个子网，通过子网掩码来实现。例如，一个B类网络需要划分为10个子网，则需要将主机地址空间的前4位作为子网地址空间，此时子网掩码为255.255.240.0。

网关地址

定义：网关是用于连接两个或多个网段的网络设备，通常使用路由器（Router）作为网关。

作用：在TCP/IP网络体系中，网关根据目的IP地址的网络号与子网号，选择最佳的出口对IP分组进行转发，实现跨网段的数据通信。

计算：

• 将IP地址与子网掩码进行与运算，得到网络地址
• 将网络地址中对应到主机号的部分的零变为一，得到广播地址
• 网关地址常常位于网络地址和广播地址之间
• 小型网络中，网关地址一般是网络地址的第一个可用地址（主机号部分第一个非零地址）

域名系统（DNS）

• 定义：DNS是一个命名系统，用于管理名字与IP地址的对应关系。它采用分层次的命名规则，各层之间用圆点“.”隔开。

• 格式：…….三级域名.二级域名.顶级域名

  • 例如：www.wust.edu.cn表示中国（cn）教育机构（edu）武汉科技大学（wust）提供www服务的主机。

• 顶级域名

  • 国家顶级域名：如CN（中国）、JP（日本）、FR（法国）等。
  • 国际顶级域名：如int（国际性组织）。
  • 通用顶级域名：如com（公司企业）、edu（教育机构）、gov（政府部门）、net（网络服务机构）等。

5.3 因特网接入

Internet接入技术

• 定义：Internet接入技术是指用户计算机和用户网络接入Internet所采用的技术和接入方式的结构。Internet服务提供商（ISP）是接入Internet的桥梁。
• 接入方式
  • 电话拨号接入：通过调制解调器连接到ISP的接入服务器。
  • ISDN接入：通过ISDN线路连接到ISP。
  • xDSL接入：ADSL是目前最常用的。用户还需为ADSL Modem或ADSL路由器选择通信连接方式，如静态IP、PPPoA、PPPoE等。
  • 有线电视接入：通过有线电视网络接入Internet。
  • 无线接入方式：如GPRS、CDMA、WLAN、WCDMA、CDMA2000、TD-SCDMA（3G）、LTE（4G）等。
  • 共享接入：
    • 网卡共享方式：通过共享网卡实现多台计算机接入Internet。
    • 路由方式：通过路由器实现多台计算机接入Internet。

5.4 因特网服务

Internet的基本服务

WWW浏览

• 定义：WWW（World Wide Web）是一种信息服务器的集合标准，是Internet的一种具体应用。它采用客户机/服务器工作模式，通过超文本传输协议（HTTP）实现客户端和服务器之间的通信。
• 组成：
  • 浏览器：客户端软件，用于向Web服务器发出请求并显示接收到的网页。
  • Web服务器：服务器端软件，用于“监听”到来的HTTP请求，找到所请求的网页数据，并将其发送到客户端。
  • 超文本传输协议（HTTP）：用于Web服务器和Web浏览器之间交换数据的网络协议。
• 统一资源定位（URL）：用于指定用户所要求的万维网文档。URL由4部分组成：资源类型、存放资源的主机域名、端口号和资源文件名。例如，http://www.wust.edu.cn:80/index.htm。

电子邮件

• 定义：电子邮件（E-mail）是一种应用计算机网络进行信息传递的现代化通信手段，是Internet提供的一项基本服务。
• 邮件地址格式：邮箱名@邮箱所在的主机域名，例如119064649@qq.com。
• 工作原理：
  • 邮件服务器：分为接收邮件服务器和发送邮件服务器。接收邮件服务器为用户开辟专用存储空间。
  • 邮件客户端：用于撰写、发送和接收邮件。
  • 协议：
    • SMTP（简单邮件传输协议）：用于发送电子邮件。
    • POP3（邮局协议版本3）：用于接收电子邮件。
    • IMAP（Internet邮件访问协议）：用于从邮件服务器上获取邮件信息和下载邮件。

信息搜索

• 信息检索：将杂乱无章的信息有序化形成信息集合，并根据需要从信息集合中找出特定信息的过程。
• 搜索引擎：搜索预先整理好的网页索引数据库。常见的搜索引擎包括：
  • 百度：全球最大的中文搜索引擎。
  • Google：全球最大的搜索引擎。
  • 雅虎：涵盖全球120多亿网页的搜索引擎。
  • 搜狗：搜狐公司推出的第三代互动式中文搜索引擎。
  • SOSO：QQ推出的独立搜索网站。
  • 有道：网易自主研发的搜索引擎。
• PageRank算法：谷歌的网页排序算法，核心思想是根据网页之间的链接关系来评价网页的重要性。如果一个网页被很多其他网页链接到，说明该网页比较重要，其PageRank值会相对较高。如果一个PageRank值很高的网页链接到其他网页，被链接到的网页的PageRank值会相应提高。

文献检索：

从已经组织好的大量文献集合中查找并获取特定信息的相关文献的过程。常见的文献数据库包括：

• 万方数据库
• 中国知识资源总库（CNKI）
• 维普中国科技期刊全文数据库
• 中国生物医学文献数据库
• PQDD学位论文全文数据库
• IEEE/IEE（IEL）数据库
• Elsevier全文期刊
• John Wiley全文期刊

---

网站建设、网络信息表示及显示机制

6.1 网站设计原则

• 确定内容
• 确定内容的表现形式和用户
• 确定一个创造性、有效的设计方案

6.2 HTML 的各标记符作用

标记符	作用描述
	定义HTML文档的根元素，包含整个HTML文档的内容。
	定义文档的头部，包含元数据（如标题、字符集、样式链接等），不会显示在浏览器窗口中。