互联网中的网页及其超链接可建模为一个庞大的有向图，称为Web Graph。Web Graph的分析研究可应用于网页排名、检测网络垃圾信息、发现社区和镜像站点等。然而，这项研究受阻于需要把巨大的图存储到外存上，从而影响有效地随机访问结点。因此，把Web Graph压缩存储到内存的研究具有十分重要的意义。Web Graph具有本地性和相似性，且服从幂律分布。BV算法采用Zeta-k编码，是最有效的Web Graph压缩方案之一。基于BV算法，本文提出了两种改进的Web Graph压缩算法：近似最优引用序列的压缩算法和合并最优引用序列的压缩算法。二者均采用引用压缩，其关键是选取最优引用序列。不同的是，前者不再局限于滑动窗口内部，可以实现沿着结点的引用链回溯搜索近似全局的最优引用序列；后者则是通过合并固定数目的结点生成块结点，用来作为块内结点的最优引用序列。本文选用五组测试数据分别对三种压缩算法进行测试。主要的测试内容包括两个基本点：存储每条链接所用的比特位和随机访问每个结点所用的时间。最后，通过比较和分析三种算法的实验结果，表明改进后的方法提高了压缩效果，而且缩短了结点引用链的长度，提高了随机访问结点的效率。