在侦破虚开增值税发票案件的实践中,从资金交易流中找到资金环路是检测虚开增值税发票行为的关键环节。资金交易流可以抽象成由顶点和边组成的有向图,因此研究基于有向图的虚开增值税发票行为检测方法是非常必要的。本文首先研究了虚开增值税发票行为中的增值税发票环路虚开行为表象与检测方法,将从资金交易流中搜索资金环路问题抽象成对具有多重边的有向图环路搜索问题,其次研究了有向图的存储以及图的环路搜索常用算法,并对算法的适用性进行比较,发现常用的环路搜索算法均不能很好地解决具有多重边的有向图环路搜索问题,因此,提出了基于深度优先的有向图环路搜索算法。先对原始数据预处理,将资金交易流和账户信息使用账号编号关联起来,找出每个顶点的边集合并按交易时间升序排列,避免在运算过程中多次遍历所有边,通过约束边的权值来避免遍历无效边,搜索过程采用逐层退回的方式来保证能遍历到有效的多重边且能找到有向图中的所有环路,并在单机上验证了算法的正确性。但是当有向图的边数增大到100万条以上时,算法执行会发生内存溢出,从而无法得到结果。针对该问题又提出了一种基于Spark的有向图环路搜索算法,先将原始数据抽象成Spark中GraphX图数据结构,然后利用数据缓存、尾递归等方法并使用GraphX框架及Scala语言在本地模式下验证了算法的正确性,但是在相同的数据集下该算法时间效率明显低于最初提出的算法。为了提高该算法的执行效率,通过优化循环、建立索引等方法对其进行优化,在本地模式下验证后,使用边数为10000条以上的图数据集在Spark集群下实验,结果表明,优化后的算法不仅能够解决具有多重边的大规模有向图环路搜索问题,具有良好的扩展性,而且执行效率得到明显提高。最后,本文设计并实现了界面友好且可操作性强的虚开增值税发票行为检测系统。经测试,该系统能够从资金交易流中搜索出资金环路并能够查询出环路关联账户的详细信息,为稽查部门检测虚开增值税发票行为提供了重要的依据,节约了稽查成本。