面向比特幣交易網(wǎng)絡(luò)的拓?fù)浣Y(jié)構(gòu)可視探索方法*

潘嘉鋮, 韓東明, 郭方舟, 鄭文庭, 于金輝, 陳 為

(計(jì)算機(jī)輔助設(shè)計(jì)與圖形學(xué)國(guó)家重點(diǎn)實(shí)驗(yàn)室(浙江大學(xué)),浙江 杭州 310058)

1 引 言

比特幣交易以錢包作為基本單位,比特幣在錢包之間進(jìn)行流動(dòng).若將比特幣錢包當(dāng)作節(jié)點(diǎn),并將錢包之間的交易當(dāng)作連接節(jié)點(diǎn)的邊,比特幣交易就可以被轉(zhuǎn)化為一個(gè)交易網(wǎng)絡(luò).它具有兩個(gè)特點(diǎn):首先,網(wǎng)絡(luò)中的節(jié)點(diǎn)是匿名的.其次,網(wǎng)絡(luò)規(guī)模大.

因?yàn)榻灰椎哪涿?常常需要基于交易網(wǎng)絡(luò)的拓?fù)浣Y(jié)構(gòu)對(duì)比特幣交易進(jìn)行分析.但是,當(dāng)網(wǎng)絡(luò)的規(guī)模非常大時(shí),用戶在分析之前很難對(duì)整個(gè)交易網(wǎng)絡(luò)有清晰的認(rèn)知.因此,在分析比特幣交易網(wǎng)絡(luò)之前,用戶對(duì)整個(gè)網(wǎng)絡(luò)進(jìn)行交互式探索非常有必要.已有一些方法用于支持大圖探索[1-3].一般基于兩種通用的策略:(1)自頂向下的探索,往往會(huì)提供網(wǎng)絡(luò)結(jié)構(gòu)的一個(gè)概覽,然后通過(guò)過(guò)濾或者查詢來(lái)引導(dǎo)分析者到一個(gè)局部細(xì)節(jié)上.(2)自下向上的探索[4],首先在分析者需求的基礎(chǔ)上,展示局部細(xì)節(jié),并且能夠支持跟蹤感興趣的節(jié)點(diǎn)和邊(DOI).

在這兩種策略下,分析者需要非常頻繁地進(jìn)入到局部區(qū)域來(lái)進(jìn)行探索.在不同層次的細(xì)節(jié)間進(jìn)行切換以對(duì)整個(gè)網(wǎng)絡(luò)進(jìn)行導(dǎo)航,或者說(shuō)是在節(jié)點(diǎn)和邊之間進(jìn)行逐步探索,這是一個(gè)常用的操作.因此,自動(dòng)推薦合適的視圖(view)或者結(jié)構(gòu)就會(huì)是一種更高效的方法[1,5,6].

在圖論中,結(jié)構(gòu)指的是圖中一系列節(jié)點(diǎn)和邊的集合,在本文中,節(jié)點(diǎn)指的是交易網(wǎng)絡(luò)中的一部分錢包,邊則是錢包之間的聯(lián)系,故而結(jié)構(gòu)指的是錢包和錢包之間的交易模式.一個(gè)結(jié)構(gòu)描述了交易網(wǎng)絡(luò)中的一個(gè)特定的交易模式.在根據(jù)范例來(lái)推薦結(jié)構(gòu)的過(guò)程中,最主要的挑戰(zhàn)就是子圖匹配問(wèn)題,但這個(gè)問(wèn)題在無(wú)標(biāo)記的簡(jiǎn)單網(wǎng)絡(luò)中被證明是一個(gè)NP 問(wèn)題[7].已存在的子圖匹配方法經(jīng)常以有特定特征的網(wǎng)絡(luò)為目標(biāo)[8](比如有標(biāo)記或?qū)傩缘木W(wǎng)絡(luò)節(jié)點(diǎn)).找尋相似子圖還難以被實(shí)時(shí)計(jì)算,通過(guò)推薦相似結(jié)構(gòu)的交互式探索仍然是一個(gè)挑戰(zhàn).本文通過(guò)將網(wǎng)絡(luò)中的節(jié)點(diǎn)轉(zhuǎn)換成向量,將相似子圖搜索的過(guò)程轉(zhuǎn)換到高維空間中進(jìn)行,從而有效地加速了相似子圖的搜索過(guò)程,使得推薦的交互式探索成為可能.

本文提出了一種基于拓?fù)浣Y(jié)構(gòu)推薦的比特幣交易網(wǎng)絡(luò)可視分析系統(tǒng).系統(tǒng)使用了一種“表達(dá)&查詢”的構(gòu)架,支持在用戶探索比特幣交易網(wǎng)絡(luò)的過(guò)程中,以用戶定義的范例結(jié)構(gòu)為基礎(chǔ),為用戶推薦合適的結(jié)構(gòu).在基于樣本查詢所有候選結(jié)構(gòu)之前,預(yù)先計(jì)算每個(gè)結(jié)構(gòu)的向量化表示.本文所提方法從一個(gè)范例結(jié)構(gòu)開(kāi)始,支持交互式查詢、辨認(rèn)、標(biāo)記、比較和分析.

2 相關(guān)工作

2.1 比特幣交易網(wǎng)絡(luò)分析

Baumann 等人在2014 年的工作[9]將描述統(tǒng)計(jì)學(xué)和圖挖掘算法應(yīng)用于比特幣交易網(wǎng)絡(luò)數(shù)據(jù)分析,他們利用了一些聚合算法來(lái)突出網(wǎng)絡(luò)特征,并聚焦于研究網(wǎng)絡(luò)的時(shí)序變化.

在利用可視化系統(tǒng)對(duì)比特幣交易網(wǎng)絡(luò)進(jìn)行深層次的分析方面,Battista 等人在2015 年的工作[10]中利用高級(jí)隱喻來(lái)表示交易網(wǎng)絡(luò)以及交易的特征,從而能夠?qū)Ρ忍貛啪W(wǎng)絡(luò)進(jìn)行高層次的分析.他們引入一個(gè)真實(shí)的洗錢系統(tǒng)的例子來(lái)進(jìn)行分析,證明了工作的有效性.在此基礎(chǔ)上,2017 年,Kinkeldey 等人開(kāi)發(fā)了一個(gè)可視分析系統(tǒng)[11],用于分析比特幣交易網(wǎng)絡(luò)上的金融活動(dòng),該系統(tǒng)通過(guò)后端的數(shù)據(jù)轉(zhuǎn)換,可以訪問(wèn)基于實(shí)體的區(qū)塊鏈數(shù)據(jù),并開(kāi)發(fā)了一個(gè)前端系統(tǒng),通過(guò)過(guò)濾和聚類等方式,使用戶能夠在高層次視角下觀察比特幣的交易數(shù)據(jù).

針對(duì)利用比特幣交易來(lái)進(jìn)行洗錢的行為,M?ser 等人[12]的工作系統(tǒng)地介紹了比特幣交易系統(tǒng)中存在的洗錢模式,并以此作為提出反洗錢工具的基礎(chǔ)工作.在此基礎(chǔ)上,Dan 等人在2016 年[13]利用力引導(dǎo)圖可視化來(lái)幫助加速大規(guī)模比特幣交易數(shù)據(jù)的探索,并提供了協(xié)作模式,用以發(fā)現(xiàn)一些意想不到卻又高頻發(fā)生的交易模式,比如洗錢操作.

2.2 大圖可視化

大圖可視化往往用于進(jìn)行大規(guī)模網(wǎng)絡(luò)數(shù)據(jù)的分析和認(rèn)知[14],這些大圖可視化的技術(shù)可以分成兩大類:自頂向下的技術(shù)和自下向上的技術(shù).

自頂向下的技術(shù)往往比較直觀,一般會(huì)先為用戶提供一整個(gè)網(wǎng)絡(luò)結(jié)構(gòu)的概覽,幫助用戶對(duì)整體網(wǎng)絡(luò)數(shù)據(jù)有一個(gè)初步認(rèn)知[15,16].但當(dāng)網(wǎng)絡(luò)規(guī)模擴(kuò)大時(shí),生成網(wǎng)絡(luò)概覽的計(jì)算代價(jià)也會(huì)跟著升高,用戶在分析網(wǎng)絡(luò)時(shí)的認(rèn)知代價(jià)也會(huì)相應(yīng)提升.一般會(huì)用諸如聚類[17,18]、采樣[19]、過(guò)濾[20]等方式來(lái)降低需要用于網(wǎng)絡(luò)概覽計(jì)算、展示的對(duì)象的數(shù)量,或者通過(guò)邊綁定的技術(shù)來(lái)降低視覺(jué)擁擠[21,22],并輔助以縮放[23,24]、展開(kāi)[3,25]等交互技術(shù),以應(yīng)對(duì)大規(guī)模網(wǎng)絡(luò)數(shù)據(jù).自下向上的方法,則提供了另外一種思路.用戶從某個(gè)節(jié)點(diǎn)或者網(wǎng)絡(luò)中一個(gè)小結(jié)構(gòu)出發(fā),開(kāi)始迭代地探索和分析這些已展示的節(jié)點(diǎn)的鄰接或者相關(guān)節(jié)點(diǎn).像Link Sliding 和Bring&Go[4]的技術(shù)則單純基于網(wǎng)絡(luò)拓?fù)溥M(jìn)行探索分析,而對(duì)于有標(biāo)記的圖,則可以用一些基于相似度的方法來(lái)找到相關(guān)節(jié)點(diǎn)用以探索[1,5,26],Peinta 等人設(shè)計(jì)了稱為Facets 的技術(shù)[6],通過(guò)相似度以及“驚奇分?jǐn)?shù)”對(duì)大規(guī)模網(wǎng)絡(luò)進(jìn)行探索分析.在焦點(diǎn)上下文可視化中,往往會(huì)使用興趣度(DOI)技術(shù)來(lái)幫助用戶進(jìn)行大規(guī)模網(wǎng)絡(luò)探索[27-29].Van Ham等人的工作[3]使用興趣度(DOI)技術(shù)在某個(gè)選定的節(jié)點(diǎn)周圍抽取了一個(gè)最小興趣子圖,并支持用戶在任意方向?qū)@個(gè)子圖進(jìn)行伸展.Abello 等人的工作[30]提出了一種交互式的DOI 技術(shù),用以分析動(dòng)態(tài)網(wǎng)絡(luò).Kairam 等人開(kāi)發(fā)的稱為Refinery[31]的可視化系統(tǒng),通過(guò)計(jì)算DOI 分?jǐn)?shù)來(lái)支持異構(gòu)網(wǎng)絡(luò)的探索.最近,Srinivasan 等人開(kāi)發(fā)的Orko 系統(tǒng)[2]則是用多模式交互來(lái)支持網(wǎng)絡(luò)探索分析.最近的一些可視查詢技術(shù),通過(guò)交互式地構(gòu)造圖查詢并對(duì)查詢結(jié)構(gòu)進(jìn)行分析.Cao 等人提出的g-miner 技術(shù)[32]用來(lái)對(duì)多元網(wǎng)絡(luò)的節(jié)點(diǎn)組進(jìn)行可視挖掘.Graphite[33]、Vogue[34]和Visage[35]則為用戶提供了可視化界面,用來(lái)交互式地構(gòu)造、優(yōu)化圖查詢.而Vigor[36]作為一個(gè)可視化系統(tǒng),用戶可以在其中交互式地對(duì)圖查詢結(jié)構(gòu)進(jìn)行交互式的探索和分析.

2.3 相似子圖挖掘

子圖挖掘是數(shù)據(jù)挖掘中的重要領(lǐng)域,已有許多工作總結(jié)了近年來(lái)的子圖挖掘相關(guān)算法[37,38].例如,VF2plus[39]、VF3[40]等同構(gòu)子圖挖掘算法,這些算法可以得到完全匹配的子圖,這需要龐大的計(jì)算量進(jìn)行支持,很難在交互的時(shí)間內(nèi)返回結(jié)果;gSpan[41]、rami[42]等頻繁子圖挖掘算法等可以搜索得到圖中的頻繁子圖,但是不能搜索到子圖所處位置.而本文所用的方法是搜索相似的結(jié)構(gòu),并可以返回其所在網(wǎng)絡(luò)中的位置.

3 方法概述

本文主要聚焦于無(wú)標(biāo)記的簡(jiǎn)單比特幣交易網(wǎng)絡(luò)(無(wú)向無(wú)權(quán),不帶自循環(huán)和多重邊)的可視探索.首先計(jì)算每個(gè)網(wǎng)絡(luò)結(jié)構(gòu)中節(jié)點(diǎn)的向量化表達(dá),再根據(jù)向量化表達(dá)查詢候選結(jié)構(gòu).在進(jìn)行向量化表達(dá)時(shí),節(jié)點(diǎn)會(huì)被轉(zhuǎn)化到高維空間中.相對(duì)于拓?fù)淇臻g而言,在高維空間對(duì)節(jié)點(diǎn)的分析和比較會(huì)更快,進(jìn)而加快了基于結(jié)構(gòu)的查詢和探索.

本文工作的基礎(chǔ)流程分成3 步:(1)首先在預(yù)處理過(guò)程中,比特幣交易數(shù)據(jù)會(huì)被抽取為比特幣交易網(wǎng)絡(luò),并且利用將網(wǎng)絡(luò)中的每一個(gè)節(jié)點(diǎn)轉(zhuǎn)換成向量化表達(dá);(2)在可視化系統(tǒng)中,用戶可以通過(guò)交互,指定一個(gè)范例.系統(tǒng)將與范例具有拓?fù)湎嗨菩缘慕Y(jié)構(gòu)推薦給用戶,用戶可以對(duì)被推薦的結(jié)構(gòu)進(jìn)行探索和分析;(3)通過(guò)對(duì)整個(gè)比特幣交易網(wǎng)絡(luò)的迭代式的探索分析,用戶能夠修正該推薦結(jié)構(gòu).

經(jīng)過(guò)上述過(guò)程后,用戶可以迭代式地對(duì)比特幣交易網(wǎng)絡(luò)進(jìn)行高效探索,在這種探索模式下,即便不同的區(qū)域在網(wǎng)絡(luò)中相距較遠(yuǎn),也能夠被同時(shí)展示給用戶.

4 算法設(shè)計(jì)

在開(kāi)始詳細(xì)描述向量化表達(dá)和結(jié)構(gòu)查詢的過(guò)程之前,需要定義一些符號(hào).定義一個(gè)簡(jiǎn)單的無(wú)標(biāo)記網(wǎng)絡(luò)為G=(V,E),其中,V={v1,v2,…,vn}是n個(gè)節(jié)點(diǎn)的集合,E={e1,e2,…,ek|ei=(vm,vn),vm,vn∈V}表示連接V中節(jié)點(diǎn)的邊.我們用N(v)來(lái)表示節(jié)點(diǎn)v的鄰接節(jié)點(diǎn)的集合,gS表示用戶指定的范例結(jié)構(gòu),C+表示gS中的所有節(jié)點(diǎn)的k最近鄰中包含的所有連通子圖,C表示C+中的一個(gè)連通子圖.Dis 則是G的所有節(jié)點(diǎn)之間的距離矩陣.Co 表示了范例結(jié)構(gòu)中的節(jié)點(diǎn)與檢測(cè)到的結(jié)構(gòu)中的節(jié)點(diǎn)之間的對(duì)應(yīng)關(guān)系.order 函數(shù)的兩個(gè)參數(shù)分別為一組連通子圖和目標(biāo)子圖,返回這組連通子圖以及和目標(biāo)子圖的相似度從大到小排序后的結(jié)果.

4.1 向量化表達(dá)

近年來(lái),用圖的小波變換(GraphWave[43])來(lái)生成向量化表達(dá)已經(jīng)引起了很多關(guān)注,并應(yīng)用在很多模式挖掘、噪聲移除、信息壓縮等領(lǐng)域[44],圖的小波變換也被證明能夠很好地提取到圖中的一些局部拓?fù)涮卣?所以本文希望使用小波變換生成的向量化表達(dá)來(lái)捕獲圖的局部拓?fù)涮卣?并以之支持相似結(jié)構(gòu)查詢等.

算法的關(guān)鍵思想是為每個(gè)節(jié)點(diǎn)v(及其相關(guān)的局部結(jié)構(gòu))生成向量化表達(dá),從而能夠使用基于向量的相似度度量和查詢.節(jié)點(diǎn)的拓?fù)浣Y(jié)構(gòu)信息可以對(duì)節(jié)點(diǎn)的表達(dá)進(jìn)行定義,本系統(tǒng)選擇了GraphWave 技術(shù)來(lái)對(duì)網(wǎng)絡(luò)生成節(jié)點(diǎn)表達(dá).其通過(guò)圖的小波擴(kuò)散模式,利用節(jié)點(diǎn)鄰域的信息,為每個(gè)節(jié)點(diǎn)生成向量化表達(dá).GraphWave 將小波視作是圖上的概率分布,生成的向量即表達(dá)了這種概率分布.GraphWave 保證了局部鄰域相似的節(jié)點(diǎn),其對(duì)應(yīng)的生成向量也會(huì)相似.

4.2 相似結(jié)構(gòu)查詢

對(duì)于用戶給定的范例,要查詢出相似的結(jié)構(gòu)需要以下4 步(如圖1 所示).

Fig.1 Pseudo-code of similar structure detection and the procedure diagram圖1 相似結(jié)構(gòu)檢測(cè)算法偽代碼和過(guò)程示意

(1)通過(guò)給定范例中節(jié)點(diǎn)向量化表達(dá)的相似度,構(gòu)造一組候選節(jié)點(diǎn)的集合.

本工作通過(guò)選擇與范例中的節(jié)點(diǎn)類似的節(jié)點(diǎn)來(lái)構(gòu)建候選節(jié)點(diǎn)集.具體地,給出一個(gè)包含了m個(gè)節(jié)點(diǎn)的范例,檢查每個(gè)節(jié)點(diǎn)v的k個(gè)最近鄰,并將它們組合為候選節(jié)點(diǎn)集N.但是,不同節(jié)點(diǎn)的最近鄰可能有重復(fù),N的大小將小于m×k.

節(jié)點(diǎn)v的k最近鄰是根據(jù)節(jié)點(diǎn)的向量化表示的相似度來(lái)構(gòu)造的.本文使用了歐氏距離來(lái)表達(dá)向量之間的相異度.

(2)在這群候選節(jié)點(diǎn)中,根據(jù)原圖存在的拓?fù)浣Y(jié)構(gòu),構(gòu)造出多個(gè)連通的子圖.

給定了m個(gè)節(jié)點(diǎn)k個(gè)最近鄰,精確的搜索空間是km.完全遍歷這個(gè)空間以找到類似的結(jié)構(gòu)將會(huì)有兩個(gè)挑戰(zhàn).首先,時(shí)間復(fù)雜度太高,不足以支持交互式的探索;其次,它只支持精確匹配,即探測(cè)出的結(jié)構(gòu)的節(jié)點(diǎn)必須與范例中的節(jié)點(diǎn)存在一一對(duì)應(yīng)的映射關(guān)系.事實(shí)上,探測(cè)的結(jié)構(gòu)很少能夠完全一樣,所以結(jié)構(gòu)的檢測(cè)必須容忍一定程度的差異.

因此,本工作建議檢測(cè)所有搜索空間中的連通子圖,它由候選節(jié)點(diǎn)及其邊組成.檢測(cè)到的子圖被視為候選的目標(biāo)結(jié)構(gòu).這里的假設(shè)條件是,檢測(cè)到的結(jié)構(gòu)必須是原始網(wǎng)絡(luò)中的連通子圖,并且其中每個(gè)節(jié)點(diǎn)必須與范例中的某個(gè)節(jié)點(diǎn)相似.

(3)建立范例中的節(jié)點(diǎn)與候選節(jié)點(diǎn)之間的對(duì)應(yīng)關(guān)系.

對(duì)于檢測(cè)到的結(jié)構(gòu),從連接的每個(gè)子圖(組件)C中的節(jié)點(diǎn)會(huì)在范例gS中尋找向量空間中距離最短的節(jié)點(diǎn),并與之建立對(duì)應(yīng)關(guān)系.

(4)將檢測(cè)出來(lái)的子圖根據(jù)它們和范例的結(jié)構(gòu)相似度進(jìn)行排序和過(guò)濾.

檢測(cè)到的結(jié)構(gòu)會(huì)根據(jù)Weisfeiler-Lehman 圖核[45]計(jì)算得到的結(jié)構(gòu)相似度分?jǐn)?shù)進(jìn)行排序.與范例最為相似的結(jié)構(gòu)會(huì)進(jìn)行展示,而一些不相似的結(jié)構(gòu)則會(huì)被過(guò)濾掉以減少需要探索的結(jié)構(gòu)數(shù)量.在本文中,過(guò)小的連通結(jié)構(gòu)或者過(guò)大的結(jié)構(gòu)均會(huì)被過(guò)濾.

5 可視分析系統(tǒng)

本文開(kāi)發(fā)了一個(gè)可視分析系統(tǒng),用以支持基于拓?fù)浣Y(jié)構(gòu)的針對(duì)比特幣交易網(wǎng)絡(luò)推薦式探索分析.圖2 展示了整個(gè)系統(tǒng)的用戶界面,該系統(tǒng)由5 個(gè)主要視圖組成:(1)節(jié)點(diǎn)鏈接視圖(如圖2(C)所示),顯示了比特幣交易網(wǎng)絡(luò)的詳細(xì)結(jié)構(gòu),用戶可以在其中探索、識(shí)別感興趣的結(jié)構(gòu);(2)熱力圖視圖(如圖2(A)所示),通過(guò)對(duì)交易網(wǎng)絡(luò)的二維布局進(jìn)行核密度估計(jì)生成的熱力圖,作為其概覽;(3)向量投影視圖(如圖2(B)所示):交易網(wǎng)絡(luò)中的節(jié)點(diǎn)向量化表達(dá)的投影視圖,用以觀察不同結(jié)構(gòu)的節(jié)點(diǎn)向量化表達(dá)差異;(4)推薦展示視圖(如圖2(D)所示),用以展示推薦的結(jié)構(gòu);(5)探索歷史樹(shù),用以記錄探索過(guò)的結(jié)構(gòu).

Fig.2 System interface design圖2 系統(tǒng)界面設(shè)計(jì)

5.1 節(jié)點(diǎn)鏈接視圖

節(jié)點(diǎn)鏈接視圖(如圖2(C)所示)是對(duì)比特幣交易網(wǎng)絡(luò)進(jìn)行探索以及對(duì)用戶感興趣的范例結(jié)構(gòu)進(jìn)行選取的主要工作空間.該視圖用預(yù)先計(jì)算完畢的力引導(dǎo)布局來(lái)呈現(xiàn)比特幣交易網(wǎng)絡(luò)的詳細(xì)結(jié)構(gòu),并提供了平移和縮放工具來(lái)支持對(duì)網(wǎng)絡(luò)的探索導(dǎo)航.

5.2 熱力圖視圖

為幫助用戶了解網(wǎng)絡(luò)的大致形狀并定位感興趣的結(jié)構(gòu),系統(tǒng)展示了基于核密度估計(jì)的熱力圖以及提取的輪廓線(如圖2(A)所示).該視圖中,用戶已經(jīng)探索過(guò)的區(qū)域會(huì)被標(biāo)記為灰色,未探索到的區(qū)域標(biāo)注為藍(lán)色.熱力圖視圖提供了一系列的交互工具,包括放大/縮小、興趣區(qū)域(ROI)的選擇和平移以及推薦結(jié)構(gòu)的定位.

(1)縮放:支持了不同級(jí)別縮放技術(shù),多級(jí)別利用不同帶寬的核密度估計(jì)函數(shù)來(lái)生成.

(2)興趣區(qū)域(ROI)的選擇和平移:用戶可以通過(guò)在該視圖中繪制一個(gè)矩形來(lái)選擇興趣區(qū)域(ROI).用戶可以通過(guò)拖動(dòng)來(lái)平移興趣區(qū)域(ROI),并在節(jié)點(diǎn)鏈接視圖中同步瀏覽該興趣區(qū)域(ROI)的詳細(xì)信息.

(3)推薦結(jié)構(gòu)的定位:當(dāng)用戶定義了一個(gè)范例時(shí),該范例及推薦結(jié)構(gòu)將會(huì)被標(biāo)記在熱力圖視圖中.用戶能夠通過(guò)點(diǎn)擊標(biāo)記來(lái)定位范例或推薦結(jié)構(gòu).

5.3 向量投影視圖

向量投影視圖(如圖2(B)所示),利用了t-SNE 投影算法[29],將比特幣交易網(wǎng)絡(luò)中每個(gè)節(jié)點(diǎn)的向量化表達(dá)投影至二維空間中.首先,t-SNE 投影算法將兩個(gè)向量之間的相似度表示成概率分布,使得相似的向量表示為高概率,不相似的向量表示為低概率,之后,在二維空間中構(gòu)建這些點(diǎn)的概率分布,并優(yōu)化這個(gè)二維空間的概率分布,使其盡可能地接近高位空間的概率分布.在該視圖中,用戶能比較不同網(wǎng)絡(luò)結(jié)構(gòu)中節(jié)點(diǎn)的向量化表達(dá)的差別.當(dāng)用戶指定某個(gè)結(jié)構(gòu)時(shí),該結(jié)構(gòu)會(huì)在向量投影視圖中高亮顯示.當(dāng)用戶指向懸浮在某個(gè)投影點(diǎn)上時(shí),會(huì)高亮該節(jié)點(diǎn)、該節(jié)點(diǎn)的一級(jí)鄰域以及它們之間的連接邊.向量投影視圖還提供了縮放、平移等交互.在該視圖中,用戶也可以指定范例,通過(guò)雙擊某個(gè)節(jié)點(diǎn),將會(huì)選中該節(jié)點(diǎn)以及該節(jié)點(diǎn)的鄰接節(jié)點(diǎn),然后,用戶可以通過(guò)套索工具(lasso)來(lái)刪減不需要的節(jié)點(diǎn),最終將選中的節(jié)點(diǎn)及其連接邊作為范例結(jié)構(gòu).

5.4 推薦展示視圖

推薦展示視圖(如圖2(D)所示),利用推薦結(jié)構(gòu)和指定范例之間的結(jié)構(gòu)相似度,對(duì)推薦結(jié)構(gòu)進(jìn)行降序排列.用戶可以通過(guò)“上一頁(yè)”和“下一頁(yè)”按鈕,對(duì)這些推薦結(jié)構(gòu)進(jìn)行瀏覽.范例位于視圖的最左側(cè).推薦的結(jié)構(gòu)和范例通過(guò)以下3 個(gè)步驟進(jìn)行統(tǒng)一的布局,以便進(jìn)行比較.

(1)使用力引導(dǎo)布局來(lái)計(jì)算指定的范例的布局.

(2)設(shè)置每個(gè)推薦結(jié)構(gòu)的初始布局.推薦結(jié)構(gòu)的每個(gè)節(jié)點(diǎn)都能映射到范例的節(jié)點(diǎn),將推薦結(jié)構(gòu)的節(jié)點(diǎn)初始位置設(shè)置為范例中相對(duì)應(yīng)的節(jié)點(diǎn)的位置.

(3)在上一步的初始布局中加入擾動(dòng)以防止重疊.當(dāng)多個(gè)節(jié)點(diǎn)映射到范例的同一個(gè)節(jié)點(diǎn)時(shí),會(huì)有視覺(jué)混亂.可以用力引導(dǎo)算法對(duì)節(jié)點(diǎn)位置進(jìn)行幾次迭代產(chǎn)生擾動(dòng)來(lái)避免該問(wèn)題.實(shí)現(xiàn)過(guò)程中發(fā)現(xiàn),3 次迭代就足夠有效.

6 用戶實(shí)驗(yàn)

我們實(shí)現(xiàn)了一個(gè)基于Web 的系統(tǒng).系統(tǒng)采用React、D3.js 和PixiJS 來(lái)實(shí)現(xiàn)前端應(yīng)用.使用Python 3.0 來(lái)實(shí)現(xiàn)后端服務(wù)器.數(shù)據(jù)處理使用了Scipy 和Numpy.MongoDB 用于數(shù)據(jù)存儲(chǔ).

我們邀請(qǐng)一名網(wǎng)絡(luò)關(guān)系分析相關(guān)研究者來(lái)使用我們的系統(tǒng),在基本的指導(dǎo)下,使用者開(kāi)始對(duì)一個(gè)真實(shí)世界存在的比特幣交易網(wǎng)絡(luò)進(jìn)行分析.網(wǎng)絡(luò)數(shù)據(jù)是從Blockchain 的公開(kāi)數(shù)據(jù)中提取的比特幣交易網(wǎng)絡(luò).該網(wǎng)絡(luò)是2018 年1 月1 日交易日志的子集,包含了207 689 個(gè)節(jié)點(diǎn)和547 500 條邊.

案例1 展示了系統(tǒng)最基礎(chǔ)的功能:概覽+細(xì)節(jié)交互模式的應(yīng)用,用戶可以在熱力圖視圖中刷選感興趣區(qū)域,在節(jié)點(diǎn)鏈接視圖中查看細(xì)節(jié);案例2 則展示了系統(tǒng)的相似結(jié)構(gòu)檢測(cè)算法用于比特幣交易網(wǎng)絡(luò)分析的過(guò)程.

假設(shè)有一個(gè)財(cái)務(wù)分析師想要了解比特幣交易的模式,卻從未接觸過(guò)比特幣交易模式的相關(guān)分析.分析師需要向上級(jí)匯報(bào)比特幣交易中存在的一些普遍存在的以及一些特殊的交易模式,以便對(duì)整個(gè)比特幣交易網(wǎng)絡(luò)有一個(gè)大致的了解.

6.1 案例1

首先,這名分析師將網(wǎng)絡(luò)載入系統(tǒng)中,然后從熱力圖視圖開(kāi)始進(jìn)行分析.熱力圖顯示出,有3 個(gè)密度較高的區(qū)域,則先從這些區(qū)域開(kāi)始探索.

分析師首先在熱力圖中進(jìn)行刷選,選擇一個(gè)高密度區(qū)域,以觀察節(jié)點(diǎn)鏈接視圖.在節(jié)點(diǎn)鏈接視圖中,他發(fā)現(xiàn)有少量節(jié)點(diǎn)具有高中心化的性質(zhì),也即,有一些實(shí)體(人或者組織)在與大量的實(shí)體進(jìn)行交易.其中,有一個(gè)節(jié)點(diǎn)與大量的節(jié)點(diǎn)鏈接在一起(如圖3(B)所示).該節(jié)點(diǎn)的高中心化特質(zhì),說(shuō)明其與很多其他實(shí)體在進(jìn)行交易,一般而言,存在這樣高頻次交易的實(shí)體,往往是某個(gè)交易所.同樣地,分析師在另外的高密度區(qū)域也發(fā)現(xiàn)了類似的高中心化的交易模式,分析師認(rèn)為這是一些交易所.但分析師并不確認(rèn)這些交易所是否屬于合法經(jīng)營(yíng)、用戶在這些交易所進(jìn)行的交易行為是否有安全保障.分析師將該節(jié)點(diǎn)記錄下來(lái),寫入報(bào)告中,并建議繼續(xù)調(diào)查該節(jié)點(diǎn).

Fig.3 A:Heatmap of the bitcoin trading network;B:A high-density area:Highly centralized trading mode;C:An examplar;D:Structures found by using the examplar圖3 A:所用比特幣交易數(shù)據(jù)的熱力圖;B:其中一個(gè)高密度區(qū):高中心化的交易模式;C:范例;D:基于范例確定的結(jié)構(gòu)

6.2 案例2

在檢查各個(gè)高密度中心時(shí),分析師在附近發(fā)現(xiàn)了一種特殊的交易模式,幾個(gè)不同的節(jié)點(diǎn)都與一群公共的節(jié)點(diǎn)進(jìn)行連接,這些公共的節(jié)點(diǎn)互相之間不存在任何交易(如圖3(C)所示),于是他在節(jié)點(diǎn)鏈接視圖中選取這個(gè)結(jié)構(gòu)作為范例結(jié)構(gòu),然后通過(guò)系統(tǒng)推薦算法,獲得一些相似的推薦結(jié)構(gòu),如圖3(D)所示.分析師把這種結(jié)構(gòu)稱為多中心的星狀結(jié)構(gòu).

這些結(jié)構(gòu)零散地出現(xiàn)在了其他區(qū)域中,表達(dá)了相似的交易模式:往往都是大量的實(shí)體與少量的實(shí)體存在交易,而這些大量的實(shí)體之間并不存在交易.

分析師認(rèn)為,一般而言,這種小規(guī)模的多中心網(wǎng)絡(luò)存在兩種可能:(1)度數(shù)較低的節(jié)點(diǎn)只與中心節(jié)點(diǎn)進(jìn)行交易的模式,可能代表了這是一種分布式比特幣挖掘計(jì)算的模式,中心節(jié)點(diǎn)所代表的實(shí)體擁有一群用于比特幣挖掘計(jì)算的“礦機(jī)”.而該實(shí)體習(xí)慣于和另一個(gè)實(shí)體進(jìn)行交易,或者在這個(gè)雙星結(jié)構(gòu)中,兩個(gè)中心所代表的賬戶為一個(gè)實(shí)體所有.(2)這種模式可能與洗錢行為相關(guān).洗錢過(guò)程往往會(huì)存在大量重復(fù)的交易以掩蓋非法手段獲得的金錢轉(zhuǎn)換成合法資產(chǎn)的過(guò)程,并且,為了逃避監(jiān)管,洗錢者往往會(huì)將大筆的資金分割成多筆小數(shù)目的資金同時(shí)進(jìn)行交易.于是,比特幣從一個(gè)賬戶出發(fā),通過(guò)大量的小筆交易,又匯總到一個(gè)賬戶下,經(jīng)過(guò)幾次迭代,達(dá)到洗錢的目的.

7 討 論

與以往的分析系統(tǒng)相比,本文提出的方法支持用戶通過(guò)選定范例來(lái)進(jìn)行推薦式的交互探索.而與傳統(tǒng)的查詢方式(往往為圖數(shù)據(jù)庫(kù)設(shè)計(jì))相比,本文提到的算法具有如下優(yōu)勢(shì):(1)算法可以更廣泛地應(yīng)用于圖數(shù)據(jù)查詢,而基于數(shù)據(jù)庫(kù)的查詢方法往往是為帶有屬性的圖設(shè)計(jì)的,而本文的方法只需要拓?fù)湫畔?并且在無(wú)標(biāo)記圖上也可以使用.(2)算法具有更高的容錯(cuò)率,所推薦的相似結(jié)構(gòu)能夠容忍細(xì)微的結(jié)構(gòu)差異,從而提供更加包容性的查詢結(jié)果.基于數(shù)據(jù)庫(kù)的查詢方法,通常需要顯式表達(dá)范例結(jié)構(gòu),并且可能產(chǎn)生冗余的查詢結(jié)果.例如,在一幅6 個(gè)節(jié)點(diǎn)的完全連通圖中,查詢一幅具有5 個(gè)節(jié)點(diǎn)的完全連通圖,基于數(shù)據(jù)庫(kù)的方法會(huì)返回6 個(gè)相互重疊的結(jié)果,而本文的方法使用的是描述性的結(jié)構(gòu),能夠容忍一定程度的差異(比如節(jié)點(diǎn)數(shù)量),會(huì)直接返回一幅6 個(gè)節(jié)點(diǎn)的完全連通圖,而非5 個(gè)互相重疊的結(jié)果.(3)本文的方法可以為更多的用戶服務(wù),他們可以在圖中自由地選定需要查詢的結(jié)構(gòu),而非像基于數(shù)據(jù)庫(kù)的查詢方法那樣,需要用戶根據(jù)自己的經(jīng)驗(yàn)來(lái)構(gòu)建具有節(jié)點(diǎn)屬性、節(jié)點(diǎn)之間關(guān)系的目標(biāo)結(jié)構(gòu)表達(dá)式來(lái)進(jìn)行顯式查詢.

當(dāng)然,本文的方法還存在一些局限性.在構(gòu)建查詢范例時(shí),往往不關(guān)注這個(gè)范例的上下文信息,然而節(jié)點(diǎn)的向量化表達(dá)來(lái)源于其上下文信息,因此推薦的結(jié)果傾向于與查詢的范例擁有相似的上下文,但這個(gè)上下文的相似性往往不被關(guān)注,當(dāng)網(wǎng)絡(luò)結(jié)構(gòu)非常復(fù)雜時(shí),可能會(huì)導(dǎo)致一些意想不到的結(jié)果.

8 結(jié) 語(yǔ)

在未來(lái)的研究工作中,將對(duì)目前的查詢算法作進(jìn)一步的優(yōu)化,深入研究如何進(jìn)一步提高查詢算法的準(zhǔn)確度和計(jì)算效率,以更快、更準(zhǔn)確地為用戶在探索、分析比特幣交易網(wǎng)絡(luò)的過(guò)程中提供推薦結(jié)果.此外,希望能夠?qū)W(wǎng)絡(luò)的向量化表達(dá)方法進(jìn)行優(yōu)化,縮短向量化表達(dá)的計(jì)算時(shí)間,降低預(yù)計(jì)算的耗時(shí).最后,我們還將繼續(xù)挖掘基于目前的探索分析模式在比特幣網(wǎng)絡(luò)上的分析場(chǎng)景,結(jié)合更多的信息來(lái)支持更多的分析任務(wù).例如,結(jié)合一些公開(kāi)的錢包信息,分析與比特幣交易所相關(guān)的賬戶的交易模式,探索其中的異常交易行為等等.