Motivation
两种常见的关于图的分类：
Networks (also known as Natural Graphs)
其实就是我们实际生活中会遇到的真实的图，比如社会人际关系、基因组、我们的想法
本质上这些是给定了一个domain，上面的所有信息可以建立一个networks，我们好利用networks/graphs更好的理解这个domain
information graphs
这一类更关心的是各个个体之间的联系，从而可以来做分类，预测等任务。
研究graph的目的/意义：
- model就是之前说的natural graph，而predict就是之前说的information graph。
- 举一个笔者个人认为很重要的现实意义：目前新型冠状病毒，因为春运的原因，人员走动非常的广，没有办法人工去追踪，那么这时候利用大数据建立一个social networks，可以较好的将所有潜在的感染者找出来，从而切断传染源。
Networks and Application
这一节主要讲解一些常见的networks和这些networks的应用
我们分析networks，主要分析哪些方面呢？也就是研究者们主要研究哪些方面呢？
| Networks | Application |
|---|---|
| Social Networks | Social Circle Detection |
| Infrastructure Networks | Aug 15，2003 blackout |
| Knowledge Networks | Link Prediction |
| Online Media | Polarization on Twitter、Misinformation、Predicting Virality、Product Adoption |
| Biomedicine | Side effects |
what are the images that are nearby in this embedding space？接下来的五节课我们都会学习怎么来映射到高维空间中。
上面的结果是只是用了image feature，没有使用graph。而下面的是使用了graph的。明显看到下面的结果会更好。
Course Outline
- 蓝色部分：Algorithm for analyzing networks
- 黄色部分：Statistical machine learning on networks
- 绿色部分：public applications and lectures focused on the use cases those applications
Structure of Graphs
怎么描述一个网络？首先理解图的基本单元有哪些：
Network和Graphs是在课程中是不同的概念。但是大家也不要太在意这些区别：
How do you define a networks?
其实是network的一种数学表示
- networks可以视为一种通用的语言，用来描述不同domain下个体之间的联系。
- 根据什么样的属性来考虑个体之间的联系，就称为xxxnetwork（xxx表示的就是你基于的联系属性）。
Choice of Network Representation
- undirected graphs（无向图）：比如像微博上，我关注了你，你并没有关注我或者你也关注了我。即互相之间的关系是无所谓主从关系
- directed graphs（有向图）： 电话-一定有一人拨打电话和另一断接听电话，是明确知道方向，我打给了你和你打给我是不一样的箭头方向
节点的度：（1）在undirected graph中这个度表明的就是这个节点连接的其他节点数量
我们也可以理解为微博中，你的粉丝数量+关注数量-互粉数量
（2）在directed graph中这个度反映的就更加精准：分为in-degree和out-degree
in-degree可以理解为粉丝数量，out-degree可以理解为关注数量（你关注别人）。注意到这里ppt上
的C是没有双向箭头的。
完全图
二分图
这种图结构很有用：
当你的nodes是不同的类型的时候，按照类型分类(disjoint sets)。如作者作为U类，论文作为V类。
同时二分图也可以衍生出新的图
怎么表示/存储一个图？
Adjacency Matrix
通俗的理解就是将每个节点之间是否存在连接（1 or 0)通过矩阵形式表示出来
我们可以试一下将0表示为白色，1表示为黑色点将邻近矩阵画出来：可以发现邻近矩阵是稀疏的
note
现实中大部分networks都是稀疏的（稀疏–非常好的性质）
这样我们把graph表示成矩阵-稀疏矩阵，所占内存将减少很多
Edge List
Adjacency List
Edge Attributes
下面是示例：
连通性
Network Representations
不同的network具有不同的graph：
