图表示的选择

网络的组成部分

因此，网络由两种类型的对象组成。首先，我们将对象或实体本身称为节点，和顶点，
然后我们在它们之间有相互作用或边，叫做链接，或者，是边缘。
然后是整个系统，然后我们将域称为-网络，还是图。

选择合适的代表

¡ 如果您将相互合作的个人联系起来，您将探索一个专业网络
¡ 如果你连接那些有无性关系的人，你将探索性网络
¡ 如果将相互引用的科学论文连接起来，您将研究引文网络
¡ 如果将标题中相同单词的所有论文连接起来，您将探索什么？ 它是一个网络，但

你如何定义图

¡ 如何构建图表：
§ 什么是节点？
§ 什么是边？
¡ 对给定域/问题的适当网络表示的选择决定了我们成功使用网络的能力：
§ 在某些情况下有一个独特的、明确的表示
§ 在其他情况下，表示绝不是唯一的
§ 您分配链接的方式将决定您可以研究的问题的性质

有向图vs无向图

无向图
¡ 链接：无向（对称，互惠）
例子：
§ 合作
§ Facebook 上的友谊

有向图
¡ 链接：定向（弧线）
例子：
§ 电话
§ 在推特上关注

节点的度

无向图

节点度，ki：与节点i相邻的边数


嗯，在网络上。有这个数字2的原因是，
因为当我们计算节点的度数时，每个边缘都被计数两次。

有向图

在有向网络中，我们定义了入度和出度。
入度是指向节点的边数。
出度是节点指向外的边数。
节点的（总）度数是入度和出度之和。

Source ：kin = 0 的节点
Sink ：kout = 0 的节点

二部图

二部图是一种图，其节点可以分为两个不相交的集合 U 和 V，
使得每个链接都将 U 中的一个节点连接到 V 中的一个节点；
U 和 V 是独立的集合

二部图通常是两种不同类型的节点的图，
其中节点仅与其他类型的节点进行交互
但彼此之间不可以。

因此，例如，二部图是可以拆分节点的图
分为两个分区，并且-边缘仅从左侧开始，
嗯，到正确的分区，而不是在同一分区内。
自然出现的二部图的例子是，
例如，嗯，科学作者链接到他们撰写的论文，
演员与他们上映的电影有关，
与他们评分或观看的电影相关联的用户，
嗯，依此类推。例如
购买产品的客户也是我们有一组客户的二部图，一套产品，
然后我们将顾客与产品链接起来，嗯，她购买了产品。

例子：
§ 作者对论文（他们创作的）
§ 演员到电影（他们出现在）
§ 用户到电影（他们评分）
§ 配方到成分（它们包含）
¡ “折叠”网络：
§ 作者合作网络
§ 电影合作评级网络

既然我们已经定义了双向网络，
我们还可以定义折叠或投影网络的概念，我们可以在其中创建，
例如，作者协作网络，或电影分级网络。
想法如下：如果我有二部图，

折叠或投影二部图

然后我可以将此二分图投影到左侧或右侧。
以及何时以及何时我进行投影，基本上，
我只在投影图中从一侧使用节点，
我连接节点的方式是说
我将在一对节点之间创建一个连接，如果他们至少有一个共同的邻居。
因此，如果这些是作者并且这些是科学论文，
然后基本上，它说，
我将在其中创建一个共同合作或共同作者图表
如果他们共同撰写至少一篇共同的论文，则可以将一对作者联系起来。
例如1、2和3人合著了这篇论文，因此它们彼此相连。
例如，3和4没有共同撰写论文，
因此它们之间没有链接。
但是例如5和2共同撰写了一篇论文，
所以他们之间有联系，因为他们是共同创作的，
嗯，这里的这篇论文。以类似的方式，
您还可以创建一个投影这个双向网络-在右侧，
然后您将获得这样的图形。

正如我所说的，二部图或多部图，
如果您有多种类型的边缘，
非常受欢迎，尤其是
如果您有两种不同类型的节点，
例如使用者和产品，用户和电影，作者和论文，等等等等。

表示图：邻接矩阵

请注意，对于有向图（右），矩阵不是对称的

邻接矩阵是稀疏的

网络是稀疏图

图表示：边列表

§ (2, 3)
§ (2, 4)
§ (3, 2)
§ (3, 4)
§ (4, 5)
§ (5, 2)
§ (5, 1)

图表示：邻接表

邻接表：
§ 更容易使用，如果网络是
§ 大的
§ 稀疏
§ 允许我们快速检索给定节点的所有邻居
§ 1:
§ 2: 3, 4
§ 3: 2, 4
§ 4: 5
§ 5: 1, 2

节点和边的属性

可能的选项：
§ 权重（例如，交流频率）
§ 排名（最好的朋友，次要的朋友……）
§ 类型（朋友、亲戚、同事）
§ 符号：朋友与敌人，信任与不信任
§ 属性取决于图其余部分的结构：共同朋友的数量

有向图的连通性

强连通有向图
§ 有从每个节点到每个其他节点的路径
反之亦然（例如，A-B 路径和 B-A 路径）
¡ 弱连通有向图
§ 是连通的，如果我们忽略边的方向

上边的图是连通的但不是强连通的（例如，没有办法通过沿着边缘方向从 F 到 G）。

SSC

可以识别强连接组件 (SCC)，但并非每个节点都是非平凡强连接组件的一部分。
因此，例如，在这种情况下，节点，呃，A，B，C和C组成一个紧密连接的组件，因为它们处于循环中。
因此，我们可以从任何我们可以访问的节点访问任何其他节点。
嗯，这里的示例显示了，有两个强连接的有向图，再次，打开两个周期，最多三个节点。

In-component：可以到达SCC的节点，
Out-component: 可以从 SCC 到达的节点

总结

使用图进行机器学习
§ 应用和用例
¡ 不同类型的任务：
§ 节点级别
§ 边缘级别
§ 图形级别
¡ 图形表示的选择：
§ 有向、无向、二分、加权、邻接矩阵