Uncovering illicit supply networks and their interfaces to licit counterparts through graph-theoretic algorithms

The rapid market growth of different illicit trades in recent years can be attributed to their discreet, yet effective, supply chains. This article presents a graph-theoretic approach for investigating the composition of illicit supply networks using limited information. Two key steps constitute our strategy. The first is the construction of a broad network that comprises entities suspected of participating in the illicit supply chain. Two intriguing concepts are involved here: unification of alternate Bills-of-materials and identification of entities positioned at the interface of licit and illicit supply chain; logical graph representation and graph matching techniques are applied to achieve those objectives. In the second step, we search for a set of dissimilar supply chain structures that criminals might likely adopt. We provide an integer linear programming formulation as well as a graph-theoretic representation for this problem, the latter of which leads us to a new variant of Steiner Tree problem: Generalized Group Steiner Tree Problem. Additionally, a three-step algorithmic approach of extracting single (cheapest), multiple and dissimilar trees is proposed to solve the problem. We conclude this work with a semi-real case study on counterfeit footwear to illustrate the utility of our approach in uncovering illicit trades. We also present extensive numerical studies to demonstrate scalability of our algorithms.