1. 简介

1.1 世界中的图

在真实世界中，每个人都不是独立的个体，人们通过交流和电话进行信息的沟通，这都都是图的一部分。我们想要知道他们都代表什么意思，就需要将这些关系进行编码，也就是图的表示。

例如：

• 在生物提供，各种分子的结构、细胞之间的协同工作方式，都是图的一种。
• 科学文章之间的引用
• 搜索引擎之间的关系
  

1.2. 研究图的目的

图建模的目标就是将自然界中的关系通过数学语言进行描述，有了具体的描述，我们就可以通过图中节点的运动方式去了解这些系统的运行机制。

1.3. 通常需要解决的问题

1. 结点的分类：预测给定结点的种类/颜色。
   一个具体的例子：维基百科中的有一部分的文章是伪造的，通过文章之间的相互引用和关联，可以推断哪些文章是有问题的。
2. 关系预测：预测两个节点之间是否有联系
3. 社区检测：如何在只有少数点的情况下，预测整个网络的作用/种类
4. 网络相似性：度量两个节点或者是两个网络之间的相似性。

1.4. 建模步骤

主要包括以下几个步骤：

1. 如何描述网络以及衡量网络
2. 设计网络的原则以及模型方法
3. 具体的算法以及如何使用模型去解决问题

1.5. 从图中学什么？

2. 网络的概念

网络和图的区别：

网络与图的联系：

2.1 无向图与有向图

节点的度 - degree

在无向图中：与目标节点A相连节点的数量称为度。
在有向图中：根据Edge方向的不同分为入度和出度。其中，在图中具有这样的一条性质：
in-degree的和与out-degree之和相等。原因是：在有向图中有入必有出。

节点的平均度 - average degree

average degree = 边的数量 除以 节点数。

multiple graphs

在上文中，我们规定了两个node之间的edge只有一条，但是，如果有多条的情况下，我们成为multi graphs

完全图 - complete graph（集 - clique）

2.2 常见网络与图之间关系总结

2.3 二分图

在下图中，二分图的意思是左边的图仅和右边的图有关联，边缘只出现在左右图的连接中，而不出现在同侧。

这种图的一个具体的例子为：文章作者和文章之间的联系或者是演员和电影之间的关系。

同样的，有二分图就意味着有三边图：如：演员、电影、电影类型之间的关系。

举个具体的例子：

• 根据U、V图推已知Project U和Project V。

  • 推Project U
    1、2、3均连接A
    2、5连接B
    4、5连C
    5、6、7连D

  • 推Project V
    A、B通过节点2连接
    B、C、D通过节点5连接

• 已知Project U和Project V 推U、V图。
  项目U和项目V之间的关系可以用下图中中间的图进行表示。
  note：在构建图的过程中，需要完全连接的点才能对应右图中新的节点。
  • 1、2、3三点互联，因此对应右图节点A；
  • 1、2、5中1和5并未相连，故而与节点B相连的只有2、5两个节点。）

2.4 图的矩阵表示

利用矩阵计算图的度

2.4 图的邻接表示

通过各个点之间边的关系来表达图。

这样的表示方法适合较为稀疏的图。

2.5 邻接列表

综合矩阵表示和邻接表示的方法，产生了邻接列表。

3. 其他的图网络

3.1 权重网络

3.2 循环图网络

3.3 多图

此时，矩阵中表示的则是不同节点之间的连接次数

4. 图的连通性

桥（bridge）：若两个节点之间仅由一条边连接，则该边称为桥。A、F。F、H不能称作桥，若去掉F、H的边，F仍然可以通过G到达H。

4.1 连通图与非连通图的矩阵表示

4.2 有向图的强连接和弱连接

强连接：节点之间可以相互连接
弱连接：节点之间的关系往往都是有去无回的，F、G