COMP5313 Week 01 图与网络基础讲课总结
COMP5313 Week 01 讲课总结：图与网络基础
本讲主要是课程引入和图论基础。期中安排等行政信息不整理，只保留后续考试会反复用到的概念。
1. 本讲主题
老师用 large-scale networks 作为全课主线：把现实系统抽象成图，再研究结构、搜索、传播、排名和机器学习。
典型网络包括：
- 社交网络：人是节点，关系是边。
- Web graph：网页是节点，超链接是有向边。
- 信息网络：论文引用、网页链接等。
- 交通 / 通信 / 交易网络：地点、设备或实体是节点，连接或交互是边。
重点不是画图，而是用图结构回答问题，比如谁重要、社区在哪里、信息如何传播、搜索能否高效进行。
2. 图的基本定义
图记作：
[ G=(V,E) ]
- \(V\)：节点集合。
- \(E\)：边集合。
- \(n=|V|\)：节点数。
- \(m=|E|\)：边数。
老师强调后面很多复杂模型，本质都要回到这些基础定义。
3. 无向图与有向图
无向图：
- 边没有方向。
- 适合表示对称关系。
- 例子：Facebook 朋友关系、合作关系。
有向图：
- 边有方向。
- 适合表示非对称关系。
- 例子：Twitter 关注、Web 超链接、论文引用。
做题时要先判断图类型，因为路径、连通性、PageRank/HITS 的计算都依赖方向。
4. 路径与距离
Path 是节点序列，相邻节点之间有边。
- 路径长度 = 边数。
- 有向图中必须沿边方向走。
- 最短路径长度就是两个节点之间的 distance。
Diameter 是图中所有可达节点对最短距离的最大值。
直觉：diameter 衡量网络最远两点需要走多远。
5. 连通性与连通分量
无向图中，如果任意两个节点之间都有路径，则图是 connected。
Connected component：
- 最大连通子图。
- 每个节点只属于一个 connected component。
- 两个 component 之间只要加一条边，就会合并成一个更大的 component。
Giant component：
- 大规模网络中常见一个远大于其他分量的连通分量。
- 后面 Web graph、社交网络、P2P 网络都会反复用到这个直觉。
6. BFS 广度优先搜索
BFS 从起点开始逐层扩展：
- 第 0 层是起点。
- 第 1 层是起点的邻居。
- 第 2 层是还没访问过的邻居的邻居。
- 以此类推。
BFS 的用途：
- 计算从一个源点到所有其他节点的最短距离。
- 判断连通分量。
- 后面计算 edge betweenness 时要用 BFS tree。
- 后面判断 signed graph 是否二部 / 是否 balanced 也会用 BFS 思路。
BFS 树中的边只会连接同层或相邻层，不会跨过多层。
7. 考点重点
- 会写图的形式 \(G=(V,E)\)，理解 \(n,m\) 的含义。
- 会区分 directed graph 和 undirected graph。
- 会解释 path、distance、diameter。
- 会找 connected component 和 giant component。
- 会用 BFS 按层扩展，并知道 BFS 能求最短路径距离。
- 知道这些基础概念会贯穿 PageRank、community detection、GNN、P2P lookup 等后续内容。