@

1.图的概念

1. 图的组成部分
   
2. 图的意义
   作为一种解决问题的通用语言，将问题抽象成图，用同一种机器学习的算法可以求解多个问题。
   但为问题选择合适的表示是很难的问题——选择合适的点、边和问题域

2.design choice

1. 有向图和无向图directed/undirected graphs
   
2. 节点度node degrees
   
   1. 无向图的每个节点都被计算两次，平均节点度*2
   2. 自循环的无向图，增加一个节点会增加两个节点度
   3. 有向图分为入度in-degree和出度out-degree
   4. 如节点B，在无向图中节点度为2，在有向图中节点度为3
3. 二部图bipartite graph
   
   1. 通常有两种不同类型的节点，其中，A类型的节点只与B类型的节点进行交互且图的边仅从左侧开始
   2. 折叠网络即是里面一种节点类型所建的单独的网络
   3. 基于此，还可以类推出多部图multipartite

如上图，是作者U和文章V的图，当作者1,2,3一起写了文章A，那作者图里1,2,3即存在连边。所以，当我们有了二分图，可以将其投影到左侧或右侧。

3.图的表示representing graphs

1. 使用邻接矩阵adjacency matrix
   
   采用0-1两种选择，当两个节点间有边时，权重为1，否则权重为0.
   
   无向图和有向图邻接矩阵在路径上的区别。
   
   大多数的网络是稀疏的sparse，如：电网power-girds、互联网连接internet connection等
2. 使用边列表egde list——在深度学习中很受欢迎
   
   将两个节点之间的连接表示为二维矩阵two-dimensional matrix，常用于深度学习框架中，问题在于很难进行图的操作和分析，就算只是计算图中点的度数都会很难
3. 使用邻接表adjacency list——便于进行图分析和处理graph analysis and mainpulation
   
   1. 适用于大型和稀疏矩阵
   2. 能够快读检索给定节点的所有邻边

4.图的附加属性property/attributes

1. 节点的重量——可以用邻接矩阵表示
   
   节点的重量可以表示两个节点连接的强度
2. 自环和多图
   具有自环的节点：如节点4的度为3
   多图：一对节点间可以有多条边
   
3. 图的连通性connectivity of undirected graphs
   1. 无向图的连通性
      
      
      当图没有连通时，邻接矩阵可以被分成几个对角块，所以在聚类系数里面只要弄清有几个对角块就可以知道有几类。
   2. 有向图的连通性
      
      分为强连接和弱连接，强连接中的每对节点都相连，而弱连接则不是。
      

原文地址：http://www.cnblogs.com/churcee/p/16930703.html