刚哥的公开课笔记：图机器学习（一）之图结构介绍

为什么需要网络？网络是一般的描述语言，描述复杂的系统和互动实体。

两种类型的图/网络

网络（也称为自然图）：

社会是七十亿个人的集合通信系统连接电子设备基因/蛋白质之间的相互作用调节生命我们的隐藏的思想，是由大脑中有数十亿个神经元的连接

信息图：

信息/知识被组织和链接场景图：场景中的对象如何关联相似网络：获取数据，连接相似点

两种不存在明显的界限。

许多不同类型的网络

社交网络经济网络通信网络信息网络互联网神经网络

这些系统是如何组织起来的？有什么设计特征呢？

网络：知识发现

许多系统背后都有错综复杂的接线图，网络，定义了组件之间的相互作用。

我们将永远无法建模和预测这些系统，除非我们了解他们背后的网络。

许多的数据都是以网络形式的存在的：

事件图知识图疾病传播分子结构场景图细胞近似度网络

我们如何利用这些关系结构获得更好的预测？

图机器学习

复杂的领域（知识，文本，图片等）具有丰富的关系结构，可以表示为关系图。

通过明确建模关系，我们可以取得更好的预测效果。

但是我们为什么要关心网络呢？

网络是用于描述复杂数据的通用语言来自科学，自然和技术的网络比人们预期的更为相似领域之间共享词汇定义计算机科学，社会科学，物理学，经济学，统计学，生物学数据可用性和计算挑战网络/移动，生物，健康和医疗影响！社交网络，药物设计，人工智能推理

分析网络的各种方法预测给定节点的类型/颜色节点分类预测两个节点是否链接链接预测识别密集链接的节点簇社区检测测量两个节点/网络的相似性网络相似度

Facebook的社交网路图

社交圈图检测

找到社交圈以及他们为什么存在。

2003年8月15日停电前后

这揭示了此类的两个重要主题：

我们必须了解网络结构如何影响系统的健壮性开发定量工具以评估在网络结构和动态之间相互作用及其对网络故障的影响我们将了解到现实中故障随之而来，可以量化的可复制的规律，甚至使用网络工具进行预测网络：知识

应用：知识图谱

应用：链接预测

图嵌入

目标：将节点映射到d维嵌入，这样具有相似网络的节点社区紧密地嵌入在一起

基于图的推荐

网络：在线媒体

政治博客之间的联系

Tweet的两极分化

应用：谣言信息

利用网络检测wikipedia文档的真假。

真实的网络和虚假的网路对比

利用网络可以检查出86%的虚假信息，高出人类能判断的66%。

cs.stanford/people/jure/pubs/hoax-www16.pdf

应用：预测病毒

应用：产品的采用度

60%-90%的领英用户是由已有用户介绍加入的。

网络：生物制药

蛋白质交互网络

新陈代谢网络

应用：副作用

许多患者服用多种药物来治疗复杂或并存的疾病：

70-79岁的人中有46％服用5种以上的药物许多患者服用20多种药物来治疗心脏病，抑郁，失眠等

任务：假设有一对药物可以预测不良副作用

应用：生物制药图

构建一个异构图预测链接

预测任务

副作用预测的结果：

附录：一些网络工具

SNAP.pySNAP C++networkx网络结构

网络是对象的集合，其中一些成对的对象通过链接连接。

图的组成

对象：节点，边交互：连接，端点系统：网络，图网络通常是指真实的系统 Web，社交网络，代谢网络语言：网络，节点，链接图是网络的数学表示网络图，社交图，知识图语言：图，顶点，边

网络通用语言

如果您将工作的人联系起来彼此之间，您将探索职业网络如果您连接科学论文互相引用，您将研究引文网络如果您用标题中的相同单词连接所有论文，您将探索什么？这也是一个网络

如何构建一个网络

如何建立图表：

什么是节点？什么是边？

选择适当的网络表示形式，给定的领域/问题决定了我们成功使用网络的能力

在某些情况下，存在唯一的，明确的表示在其他情况下，没有独特表现形式分配链接的方式将决定你可以研究的问题

有向和无向图

无向图

有向图

交易节点的度数

节点度数定义为与节点i相邻的边的数量。

在有向网络中，我们定义入度in-degree和出度out-degree。节点的（总）度是入度和出度的总和。

完全图

N个节点上的无向图中的最大边数是

一个无向图，其边数目为E=Emax被称为完整图，平均度数为N-1

下图是各种网络的不同特征：

二分图

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

例子：

作者和论文（由作者撰写） 演员和电影（他们出现在） 观众和电影（他们评价） 配方和成分（包含）

“折叠式”网络：

作者协作网络 电影分级网络

折叠和投射的二分网络

图的表示方法：邻接矩阵

邻接矩阵是稀疏的

图的表示方法：边列表

邻接列表：

如果网络是大或者稀疏的，则更容易表示使我们能够快速检索所有给定节点的邻居

网络是稀疏图

大部分的真实网络都是稀疏的，结果是大部分的邻接矩阵充满了大量的0。

边的属性

可能的选择：

权重（例如通讯频率）排名（最好的朋友，第二好的朋友…）类型（朋友，亲戚，同事）标志：朋友与敌人，信任与不信任属性取决于图中的其余结构：例如公共朋友的数量

无权重图和有权重图

自环图和多图

无向图的连接性

无向图的连接

路径可以连接任何两个顶点断开连接的图由两个或者更多的组件组成连接

桥接边：如果我们删除边缘，图形将断开连接。例如AF

铰接节点：如果我们删除该节点，则图将断开连接。例如F

具有多个组件的网络的邻接矩阵可以以对角线的形式编写，以便将非零元素限制为正方形，而所有其他元素均为零：

有向图的连接

紧密连接的有向图

具有从每个节点到每个其他节点的路径，反之亦然（例如，A-B路径和B-A路径）弱连通有向图，如果忽略边缘方向，则成为连接图。

上图已连接非紧密连接（例如，无法通过遵循边缘方向从F到G）。

强连接的组件（SCC）可以被识别，但并非每个节点都属于非平凡的强连接组件。

组件内 in-component：可以到达SCC的节点，

外部组件 out-component：可以从SCC到达的节点。

推荐阅读P. Erdos, A. Renyi. On Random Graphs I. Publ. Math. Debrecen, 1959. P. Erdos, A. Renyi. On the evolution of random graphs. Magyar Tud. Akad. Mat. Kutato Int. Koezl., 1960. B. Bollobas. Random Graphs. Cambridge University Press. M.E.J. Newman, S. H. Strogatz and D.J. Watts. Random graphs with arbitrary degree distributions and their applications. Phys. Rev. E 64, 026118, 2001. R. Milo, N. Kashtan, S. Itzkovitz, M.E.J. Newman, U. Alon. On the uniform generation of random graphs with prescribed degree sequences. Arxiv, 2004. D. Ellis. The expansion of random regular graphs. Lecture notes from Algebraic methods in combinatorics, Cambridge University, 2011. S. Arora, S. Rao and U. Vazirani. Expander Flows, Geometric Embeddings and Graph Partitioning. In proc. STOC '04, 2004.