最近《复杂网络建模》这门课要考试了，正好也在跟Stanford的《CS224W：MachineLearningWithGraphs》这门课，这里就一边整理笔记一边复习了。1.网络的定义网络(network)是一些通过链接(links)连接起来的对象集合，它包含以下成分：对象：节点(nodes)/顶点(vertices)，用\(N\)表示；交互：链接(links)/边(edges)，用\(E\)表示；对象和交互组成的系统我们就称为网络(或图，graph)，用\(G(N,E)\)表示。一般而言，我们用术语网络来称呼一个真实的系统，如Web、社交网络、代谢网络等，此时伴随着术语节点和链接进行使用；而
收录一些比较冷门的DP优化方法。1.树上依赖性背包树上依赖性背包形如在树上选出若干个物品做背包问题，满足这些物品连通。由于01背包，多重背包和完全背包均可以在\(\mathcal{O}(V)\)的时间内加入一个物品，\(\mathcal{O}(V^2)\)的时间内合并两个背包，所以不妨设背包类型为多重背包。先考虑一个弱化版问题。给定一棵有根树，若一个节点被选，则它的父亲必须被选。显然存在一个\(\mathcal{O}(nV^2)\)的树形DP做法，它能求出以每个节点为根时其子树的答案。接下来引出科技：树上依赖性背包。我们发现对每个节点都求答案似乎有些累赘，因为我们只关心以\(1\)为根时的答案
初等数论学习笔记I：同余相关。初等数论学习笔记II：分解质因数。1.数论函数本篇笔记所有内容均与数论函数相关。因此充分了解各种数论函数的名称，定义，符号和性质是必要的。1.1相关定义数论函数：定义域为正整数的函数称为数论函数。因其在所有正整数处均有定义，故可视作数列。OI中常见的数论函数的陪域（即可能的取值范围）为整数。加性函数：若对于任意\(a,b\in\mathbb{N}_+\)且\(a\perpb\)均有\(f(ab)=f(a)+f(b)\)，则称\(f\)为加性函数。注意区分代数中的加性函数。积性函数：若对于任意\(a,b\in\mathbb{N}_+\)且\(a\perpb\)均有\
1导引我们在博客《知识图谱实体对齐1：基于平移(translation)嵌入的方法》和博客《知识图谱实体对齐2：基于GNN嵌入的方法》中介绍的都是有监督的知识图谱对齐方法，它们都需要需要已经对齐好的实体做为种子（锚点），但是在实际场景下可能并没有那么多种子给我们使用。为了解决这个问题，有许多无监督/自监督的知识图谱对齐方法被提出。2一些常见无监督和自监督方法2.1基于GAN的方法首先我们来看一个基于GAN的方法[1]，虽然该方法是用于解决NLP中无监督跨语言词向量对齐操作的，但是我觉得在知识图谱领域也很有借鉴意义。在最原始的有监督跨语言词向量的对齐任务中，给定已经对齐好的字典（锚点）\(\le
收录一些比较冷门的DP优化方法。1.树上依赖性背包树上依赖性背包形如在树上选出若干个物品做背包问题，满足这些物品连通。由于01背包，多重背包和完全背包均可以在\(\mathcal{O}(V)\)的时间内加入一个物品，\(\mathcal{O}(V^2)\)的时间内合并两个背包，所以不妨设背包类型为多重背包。先考虑一个弱化版问题。给定一棵有根树，若一个节点被选，则它的父亲必须被选。显然存在一个\(\mathcal{O}(nV^2)\)的树形DP做法，它能求出以每个节点为根时其子树的答案。接下来引出科技：树上依赖性背包。我们发现对每个节点都求答案似乎有些累赘，因为我们只关心以\(1\)为根时的答案
初等数论学习笔记I：同余相关。初等数论学习笔记II：分解质因数。1.数论函数本篇笔记所有内容均与数论函数相关。因此充分了解各种数论函数的名称，定义，符号和性质是必要的。1.1相关定义数论函数：定义域为正整数的函数称为数论函数。因其在所有正整数处均有定义，故可视作数列。OI中常见的数论函数的陪域（即可能的取值范围）为整数。加性函数：若对于任意\(a,b\in\mathbb{N}_+\)且\(a\perpb\)均有\(f(ab)=f(a)+f(b)\)，则称\(f\)为加性函数。注意区分代数中的加性函数。积性函数：若对于任意\(a,b\in\mathbb{N}_+\)且\(a\perpb\)均有\
1导引我们在博客《知识图谱实体对齐1：基于平移(translation)嵌入的方法》和博客《知识图谱实体对齐2：基于GNN嵌入的方法》中介绍的都是有监督的知识图谱对齐方法，它们都需要需要已经对齐好的实体做为种子（锚点），但是在实际场景下可能并没有那么多种子给我们使用。为了解决这个问题，有许多无监督/自监督的知识图谱对齐方法被提出。2一些常见无监督和自监督方法2.1基于GAN的方法首先我们来看一个基于GAN的方法[1]，虽然该方法是用于解决NLP中无监督跨语言词向量对齐操作的，但是我觉得在知识图谱领域也很有借鉴意义。在最原始的有监督跨语言词向量的对齐任务中，给定已经对齐好的字典（锚点）\(\le
知识图谱实体对齐2：基于GNN嵌入的方法1导引我们在上一篇博客《知识图谱实体对齐1：基于平移(translation)嵌入的方法》中介绍了如何对基于平移嵌入+对齐损失来完成知识图谱中的实体对齐。这些方法都是通过两个平移嵌入模型来将知识图谱\(\mathcal{G}_1\)和\(\mathcal{G}_2\)的重叠实体分别进行嵌入，并加上一个对齐损失来完成对齐。不过，除了基于平移的嵌入模型之外，是否还有其它方式呢？答案是肯定的。目前已经提出了许多基于GNN的实体对齐方法[1]，这些方法不仅采用GNN捕捉更多的实体结构化信息，还通过诸如参数共享、参数交换等方式在embedding模块中就使实体的e
知识图谱实体对齐2：基于GNN嵌入的方法1导引我们在上一篇博客《知识图谱实体对齐1：基于平移(translation)嵌入的方法》中介绍了如何对基于平移嵌入+对齐损失来完成知识图谱中的实体对齐。这些方法都是通过两个平移嵌入模型来将知识图谱\(\mathcal{G}_1\)和\(\mathcal{G}_2\)的重叠实体分别进行嵌入，并加上一个对齐损失来完成对齐。不过，除了基于平移的嵌入模型之外，是否还有其它方式呢？答案是肯定的。目前已经提出了许多基于GNN的实体对齐方法[1]，这些方法不仅采用GNN捕捉更多的实体结构化信息，还通过诸如参数共享、参数交换等方式在embedding模块中就使实体的e
题目： 现在有一个长度为n的序列待构造，给出m对关系\(i,j,x\)，表示\(a_i|a_j=x\)，请在满足这m对关系的情况下构造出的最小字典序的序列。分析： 每当我们看到最小字典序的时候，基本都是贪心的思想。本题可以知道，我们要让序列前面的数尽可能的小。对于他给出的关系，需要按位来考虑，但是有一些麻烦的就是你确定一个数的一位的时候，他会影响到与他有关系的数，感觉就是一个二分图的思想。我们可以用\(f0[i][j]\)表示第\(i\)个数在第\(j\)位必定填0，\(f1[i][j]\)同理必定填1。顺序遍历序列，枚举位，能填0就填0。实现： 对于给出的关系若x在第\(k\)位上为0
