グラフ理論を用いた循環取引の検知

実際の循環取引は、複雑な商製品の流れと多数の当事者が関与することで、その連鎖が一般的には単純な構造ではない場合が多く、発見は容易ではありません。また、発見されないまま継続的に循環取引が繰り返されることで、財務諸表に与える影響が大きくなる傾向にあります。そこで、循環取引の検知に対する新たなアプローチとして、相互発注の関係にある取引（以下、相互発注取引）に注目し、次の問題を考えます。

企業間取引のデータから相互発注取引のパターンを全て洗い出して、その特徴をつかもう、というものです。
そのためには、まず初めに、企業間取引全体をグラフを用いてモデル化します。ここでいうグラフとは、棒グラフや円グラフのような、いわゆる統計グラフではなく、要素間の関係を抽象化した数理的構造で、各要素を頂点として、要素間のつながりを辺として表現したものです。要素間の関係性を表現するのに、グラフが有効であることはよく知られています。グラフを用いてモデル化することで、問題の構造をより捉えやすくすることができます。また、現実世界の問題を数理的な問題として捉えることで数理的な解析が可能になります。
例として、A社、B社による取引をモデル化してみましょう。売り手であるA社と買い手であるB社をそれぞれ頂点で表し、A社からB社へ向きのある辺でつなげると、＜図1＞のようなグラフになります。

これを、全ての取引について同様に行います。例えば、＜表1＞に示すAからEの5社による七つの取引をモデル化すると、＜表1＞に含まれる各企業を表す五つの頂点と、それぞれの取引を表す7本の辺からなる＜図2＞のようなグラフになります。

ここで、相互発注取引は、＜図2＞のグラフ上でどのように表されるでしょうか。相互発注取引では、複数の企業間で転売を繰り返していき、最終的に当初の売り手が買い手になるので、つまり、ぐるりと"循環"します。＜表2＞でハイライトした四つの取引について見てみましょう。

これらの四つの取引について、それぞれの取引に相当する辺に注目すると、＜図3＞でグレーの太矢印で示した「A社→B社→D社→E社→A社」を順にたどって循環する辺の集合になります。つまり、この四つの取引は相互発注取引であることが分かります。以降では、このように循環する頂点と辺の集合を、"閉路"と呼ぶことにします。

同様に、＜表1＞の中のいくつかの取引を組み合わせると、＜図3＞に示した閉路以外に、＜図4＞および＜図5＞に示す閉路を構成することが分かります。

以上より、企業間取引において、相互発注取引を全て見つけるには、企業間取引をモデル化したグラフ上で全ての閉路を見つければ良い、ということが分かります。従って、＜問題1＞は＜問題2＞のように書き換えることができます。

ここで、＜図2＞のグラフを、グラフ理論の言葉を用いて、あらためてグラフGとして定義します。
グラフGは、頂点集合Vと辺集合Eからなり、

G＝（V, E）

と表記します。＜図2＞のグラフの頂点は、AからEの5社で、

V＝{A, B, C, D, E}

となります。一方、辺集合Eは、＜表1＞に示す七つの取引で、売り手から買い手に向かう向きのある辺の集合となり、

E={（A, B）, （A, C）, （B, D）, （C, E）,（D, C）, （D, E）, （E, A）}

となります。辺集合Eが向きのある辺（有向辺）の集合であるとき、グラフGを有向グラフと呼びます。頂点と辺とが交互に現れる列（交互列）で、頂点と辺が全て異なるものをパスと呼び、始点と終点が同一頂点となるパスを閉路と呼びます。例えば、＜図3＞に示した閉路をCとすると、閉路Cは、

C＝（A, （A, B）, B, （B, D）, D, （D, E）, E, （E, A）, A）

という、始点と終点が一致する交互列で表現することができます。
以上の定義を用いると、＜問題2＞は＜問題3＞のように書き換えることができます。

つまり、当初の＜問題1＞は、グラフを用いたモデル化によって、企業間取引が有効グラフに、相互発注取引が閉路に、それぞれ置き換わったのです。
実は、＜問題3＞は、グラフ理論において閉路列挙問題としてよく知られています。
列挙問題とは、与えられた条件を満たす解や要素などを漏れなく、重複なく出力する問題です。全ての解を見つける必要がありますが、一つの解を見つけることさえ難しい、という問題も多く存在します。また、列挙問題は膨大な解を持つことが多く、問題の規模によっては全ての解を列挙し尽くすまでには相当な時間を要することがあります。全ての解を見つけるのは、けして簡単なことではありませんが、問題全体の構造を理解する上では非常に有効です。列挙問題を効率良く解くためのアルゴリズムの研究は古くから行われており、閉路列挙問題を解くためのアルゴリズムも多数提案されています。代表的なアルゴリズムの一つに、1970年代にR. E. Tarjan^※によって提案されたアルゴリズムがあります。
以上により、企業間取引において相互発注取引を全て見つける、という問題は、与えられた有向グラフにおける全ての閉路を列挙する、という、グラフ理論で古くから研究されている閉路列挙問題に帰着され、既存のアルゴリズムを適用すれば解くことができる、ということが分かりました。

さて、既存のアルゴリズムを適用し、＜問題3＞の閉路列挙問題が解けて、企業間取引をモデル化したグラフ上の全ての閉路が列挙できたとします。それぞれの閉路は、相互発注取引に相当しますので、一つ一つの閉路を見てみると、複数の企業を介して循環する取引の一連のつながりが見えてきます。
列挙された閉路が表す相互発注取引の中には、不正な循環取引に該当するものが含まれている可能性があります。ただし、閉路を形成しているからといって、列挙した全ての相互発注取引が、意図的な不正な循環取引である、と即座に断定することはできません。循環取引に類似しているが、循環取引には該当しない適正な取引も含まれているので、それらを取り除く必要があります。グラフを用いてモデル化した際には考慮しなかった取引の詳細情報を活用し、不正な循環取引と適正な取引を判別し不正を検知するプロセスが大変重要になります。
一方、実務的な観点では、実際の企業間取引のデータを網羅的に入手するのは容易ではなく、また、もし入手できたとしても非常に大規模なグラフとなるため、分析には膨大な計算を伴う、といった課題もあります。

今号では、循環取引の検知の新しい方法として、グラフ理論を用いたアプローチを紹介しました。企業間取引をグラフを用いてモデル化し、グラフ上の閉路を全て列挙することで、相互発注取引を全て見つけることができます。全てを列挙するのは簡単ではありませんが、列挙することにより循環取引という不正の構造を理解し把握することが可能となり、複雑な構造のために発見が容易ではない、とされる循環取引を効率良く検知する一助になることが期待されます。
また、巨大な企業間取引の中で、企業と企業がどのように結びつき、どのような商流を形成しているのか、その全貌を捉え理解する上でも、このようなグラフ理論の応用が可能だということがお分かりいただけたでしょうか。取引先のさらに先にいる多くの企業と、自社がどのようなつながりを成しているのか、可視化し把握する上でも、グラフを用いたモデル化は非常に有用だと言えるでしょう。