COMP5313 考试 Cheatsheet(六大模块速查)
COMP5313 考试 Cheatsheet — 六大模块速查
覆盖 Week 1-6,按六大知识模块组织,供考场快速回顾。 教材:Networks, Crowds, and Markets (Easley & Kleinberg) + Mining of Massive Datasets Ch5 + Barabási Network Science
一、图与网络基础(Graph Basics)
1.1 基础定义
- 图(Graph):\(G = (V, E)\),节点集 \(V\)、边集 \(E\)
- 邻居(Neighbors):若 \((u,v) \in E\),则 \(u, v\) 互为邻居
- 度(Degree):节点连接的边数;有向图分出度 \(d^{out}\)、入度 \(d^{in}\)
- 无向图:边对称;有向图:边有方向(Web、Twitter 关注)
- 应用:社交(Facebook)、通信(Arpanet)、信息(Web)、生物(PPI)
1.2 路径与环
- 路径(Path):节点序列,相邻节点间有边
- 简单路径(Simple Path):不重复节点
- 环(Cycle):首尾相同的路径,长度 ≥ 3
- 路径长度:边数
- 距离 \(d(u,v)\):最短路径长度
- 直径(Diameter):\(\max_{u,v} d(u,v)\)
1.3 连通性
- 连通(Connected):无向图中任意两节点有路径
- 连通分量(Connected Component, CC):极大连通子图
- 巨分量(Giant Component):占节点相当比例的大分量;通常只有一个——两个巨分量只需 1 条边即合并
- 有向图:
- 强连通(Strongly Connected):任意两点互有有向路径
- 强连通分量(SCC):极大强连通子图