近年来,随着万维网(World Wide Web,WWW)的发展,社交网络的应用变得十分流行。社交网络通常是由现实中的个体之间通过朋友、血缘等社交关系建立的社交结构。将社交网络中的个体看作顶点,个体之间的联系看作边,可以将社交网络抽象成一个有向图,称为社交网络图。挖掘社交网络中的信息和研究社交网络的发展模型取决于对社交网络图的深层研究,而社交网络的规模巨大,导致对应的社交网络图的顶点和边也非常多,这是研究社交网络图的一大障碍。因此,对社交网络图进行压缩即成为社交网络图研究的首要任务。但是社交网络图和传统网络图的性质有很大的不同,根据节点的URL字典序存储后,相邻节点的邻接序列的相似度很小,不利于社交网络的压缩。本文通过研究社交网络的性质,分析出社交网络中的相似性。这种相似性表现在节点和它邻接序列表中的节点之间,这是因为节点和邻接序列表中的节点具有朋友、血缘等关系,现实中两个人的关系越亲密,其对应的社交圈的重合度也比较大。本文根据这种相似性,提出了一种新的压缩方案,称为SNComp(Social Networks Compression)。SNComp结合了BFS(Breadth First Search)算法和Rabin指纹算法。使用BFS算法能够实现对节点的层次化扫描,将父节点和它的孩子节点存储在相对临近的位置。但是使用这种方法对节点排序,节点的孩子节点之间是按照扫描的先后顺序依次排列,没有考虑孩子节点之间的相对顺序。SNComp进一步使用Rabin指纹算法,计算父节点和它的孩子节点之间的相似度值,然后通过这个值对孩子节点排序,从而可以保证子节点之间能够按照和父节点的相似度大小顺序排序。因此,SNComp能够保证存储在相邻位置的节点能够表现出很大程度的相似性。根据节点间的相似性,SNComp使用引用压缩、块压缩等压缩方法对社交网络图进行压缩,能够保证节点间相同的的部分只需存储一次,实现了对社交网络图的高效压缩存储。本文采用六组经典的社交网络数据对实验结果进行测试。主要的测试内容包括存储每条链接所用的比特数和随机访问每个节点所用的时间。最后,通过比较和分析实验结果,验证了本文的社交网络压缩算法的可行性,并且和MPk(Multi-Position linearization of degree k)算法相比,本压缩方案在压缩效率方面有所提高。