图分析 – 佚名

概述

图分析的应用领域
- 编译器的优化
- 操作系统的任务调度
- 数据库应用
- 自然语言处理
- 计算几何
- 社交网络分析
分布式的图
- 多核CPU，多指令多数据（Multiple Instruction Multiple Data，MIMD）
  - OpenMP
- GPU，单指令多线程（Single Instruction Multiple Thread，SIMT）
  - CUDA
  - Thrust
  - OpenCL
- 分布式系统
  - MPI
编写图分析的算法
- （抽象程度低）使用原生语言（比如C、CUDA），以及底层库
  - 程序规模大，难以理解、修改，而且容易出错
- （抽象程度中）使用框架
  - 调用通用API
  - 基于不同的执行模型
- （抽象程度高）使用领域专用语言（Domain Specific Language，DSL）
  - 提供语义检查
  - 提供高层次的抽象
DSL的例子
- Web应用 –> HTML、CSS、JavaScript
- 数据库应用 –> SQL
- 硬件设计语言 –> VHDL、Verilog
- 科学计算 –> Matlab

网页对应于点，链接对应于边
- Pagerank算法是一种图的算法
道路网络
- 图的直径很大
- 图的顶点度数很小
- 导航的寻路算法是一种图的算法
随机图
- 图的点是固定的
- 图的边是随机的，可以增加和删除
- 类似于神经网络的dropout
社交网络
- 图的直径很小，小世界现象（Small-World Phenomenon）
- 图的顶点度数可能很大（比如一个人拥有大量关注者），满足幂律分布（Power-Law Distribution）