در سال‌های اخیر، بیتکوین به یک ارز دیجیتال محبوب تبدیل شده است و به طور گسترده برای معاملات مختلف به کار میرود. شبکه تراکنش‌های بیتکوین را میتوان به صورت یک شبکه پیچیده مدل کرد که آدرس ها و تراکنش‌ها ، نودها و یال‌های شبکه را تشکیل دهند . در بخش اول با استفاده از تکنیک‌های تجزیه و تحلیل شبکه پیچیده، ویژگی‌های توپولوژیکی شبکه از جمله توزیع درجه، ضریب خوشه‌ای و رشد، شبکه معاملات بیتکوین را تجزیه و تحلیل میکنیم و در بخش دوم با استفاده از از داده‌های تراکنش‌های بیتکوین که در وبسایت Kaggle موجود است و بهره‌گیری از تکنیک‌های هوش مصنوعی، نشان می‌دهیم که میتوان تراکنش‌های مشکوک در این شبکه را کشف کرد.
این مقاله در دو بخش سازماندهی شده است. در بخش اول، مروری کوتاه بر بیتکوین و تحلیل شبکه پیچیده آن را ارائه میکنیم و در بخش بعدی، با استفاده از داده‌ی زمانی محدود و مشخص استخراج شده از وبسایت Kaggle و بهره گیری از شبکه عصبی گراف(Graph Neural Networks) و روش LPA، مدل هایی ایجاد میکنیم که توانایی تشخیص تراکنش های مشکوک با دقت بالا را دارد.
مقدمه
بیت کوین یک ارز دیجیتال غیرمتمرکز است که در شبکه همتا به همتا(peer-to-peer) بدون نیاز به مرجع مرکزی یا واسط، عمل میکند. تراکنش‌های بیت کوین در یک دفتر عمومی(public ledger) به نام بلاکچین ثبت می‌شوند که شامل تاریخچه کاملی از تمام تراکنش‌های بیت کوین است. این شبکه بلاک چین توسط یک شبکه غیرمتمرکز از گره‌ها نگهداری میشود که تراکنش‌ها را تایید و پردازش میکند.
شبکه تراکنش بیت کوین یک سیستم پیچیده است که در آن گره‌ها تراکنش‌ها را نشان می‌دهند و یالها نشان دهنده انتقال بیت کوین بین این تراکنش‌ها هستند. تحلیل این شبکه پیچیده، به ما اجازه می‌دهد تا ویژگی‌های ساختاری شبکه، مانند توزیع درجه، ضریب خوشه بندی و ساختار آن را بررسی کنیم.
هدف این مقاله استفاده از تکنیک‌های تحلیل شبکه پیچیده در شبکه تراکنش بیت کوین برای به دست آوردن درک بهتری از ساختار و پویایی آن است. به طور خاص، هدف ما شناسایی گره‌ها و یال های کلیدی در شبکه، تجزیه و تحلیل توپولوژی آن، و بررسی چگونگی تکامل شبکه در طول زمان است. دلیل این که شبکه را در بازه های کوتاه و مختلف زمانی بررسی کردیم این است که شبکه تراکنش بیتکوین در کل بازه زمانی از بدو تولد، بسیار حجیم شده است و نیاز به آنالیز کل شبکه نیست زیرا خصوصیات شبکه در بازه های مختلف زمانی تقریبا ثابت بوده است، به جز مواردی که به صورت مجزا با تغییر زمان، دچار تغییر شده است همچنین مقالات مرجع که برای بررسی انتخاب شدند دوره های مختلف شبکه را تحلیل کرده اند.
این مطالعه نتیجه قابل توجهی برای درک رفتار اکوسیستم بیت کوین دارد. با تجزیه و تحلیل تکامل شبکه در طول زمان، میتوانیم بینشی در مورد چگونگی رشد و انطباق اکوسیستم بیتکوین در طول زمان به دست آوریم.
روش شناسی(Methodology)
بلاکچین یک دفتر (ledger) عمومی توزیع شده میباشد که تراکنش‌های اتفاق افتاده در شبکه را ذخیره میکند و از زنجیره‌ای از بلوک‌ها ایجاد شده است که هر بلوک حاوی آدرس بلوک قبلی میباشد و دسته ای از تراکنش‌های مجاز را نگه میدارد. در این سیستم پرداخت کننده و دریافت کننده می‌تواند به تعداد نامحدود آدرس داشته باشد. یک تراکنش در سیستم ارزهای دیجیتال، نوعی تراکنش عادی بانکی میباشد که اجازه می‌دهد چندین آدرس فرستنده و چندین آدرس گیرنده در یک تراکنش وجود داشته باشد .
در سیستم بیتکوین، یک تراکنش به صورت یک واحد رکورد پرداخت یکباره (one-time payment) تعریف میشود. در یک تراکنش، فرستنده با رجوع به دریافتی‌هایی که از دیگران داشته، وجهی را انتقال می‌دهد . در بیتکوین مفهوم بالانس حساب وجود ندارد و پرداخت‌ها همیشه به معنای خرج کردن دریافتی‌های قبلی میباشد.
یک تراکنش دارای دو بخش اصلی میباشد: (i) لیست وروردی و (ii) لیست خروجی . هر ورودی شامل اطلاعات مربوط به تراکنش‌های قبلی و اطلاعات امضای تایید شده، از طرفی خروجی تراکنش، حجم پول پرداختی و اطلاعات آدرس گیرنده‌ها را نشان می‌دهد. هر تراکنش بیتکوین به صورت منحصر به فرد با یک شناسه که مقدار هش تراکنش میباشد مشخص میشود.
تراکنش کوین بیس (Coinbase transaction) نوع دیگری از تراکنش است که سیستم بیتکوین به عنوان جایزه به ماینری که بتواند کد بلوک کامل شده را از طریق محاسبات پیچیده پیدا کند، اختصاص می‌دهد. این نوع تراکنش تنها یک ورودی دارد و تراکنش قبلی در ورودی ندارد، زیرا این پول توسط خود شبکه ایجاد شده است و از جای دیگری منتقل نشده است.
در یک بلوک علاوه بر تراکنش‌ها، شامل داده‌های دیگری نیز می باشد از جمله، هش بلوک قبلی، برچسب زمان(timestamp) و nonce.
در شکل بالا قسمت A یک نمونه از تراکنش بیتکوین با دو آدرس فرستنده و دو آدرس گیرنده که در تاریخ 2011-05-01 به بلاکچین اضافه شده است را نشان می‌دهد . در جزئیات این انتقال مشاهده میکنیم که یک بیتکوین از آدرس اول و 135 بیتکوین از آدرس دوم منتقل شده و گیرنده اول 0.33 بیتکوین و بقیه به آدرس گیرنده دوم فرستاده شده است . در قسمت B شکل، یک نمونه از تبدیل داده های تراکنش به یک گراف را نشان می‌دهد که ai ها بیانگر آدرس و ti ها بیانگر تراکنش‌ها میباشد، که t3 تراکنش مورد نظر ما و a1 و a2 دو ورودی و a3 و a4 خروجی مثال ما می‌باشند. یک ورودی در یک تراکنش، یا خروجی یک تراکنش قبلی میباشد و یا جایزه(Coinbase) میباشد.
تحلیل شبکه
در این بخش به تحلیل نتایج به دست آمده از طریق مدل کردن تراکنش‌های بیتکوین به صورت یک شبکه پیچیده می‌پردازیم. جدول زیر انواع مختلف تراکنش را نشان می‌دهد، برای مثال 0->1 تراکنشی را نشان می‌دهد که آدرس ورودی ندارد و تنها یک آدرس خروجی دارد. بیشتر تراکنش‌ها مربوط به 1->n می باشد که 64.56 درصد تراکنش‌ها را شامل میشود. تراکنش‌هایی با صفر آدرس ورودی 0.12 درصد را شامل میشود که مربوط به جایزه ماینینگ(mining reward) میباشد که شبکه بیتکوین به ماینرهایی که بلوک جدید را ایجاد می‌کنند، اهدا میکند.
شکل زیر طول مدت زمان لازم برای یک میلیون تراکنش(حجم تراکنش نسبت به زمان) را نشان می‌دهد. قبل از 2013 تراکنش به ندرت اتفاق می‌افتاد به خاطر این که فاز اول مارکت بود و بیتکوین توجه بسیاری را هنوز جلب نکرده بود، سپس با مطرح شدن بیتکوین توسط رسانه ها و اتفاقات موازی دیگر، کم کم ارزش بیتکوین افزایش پیدا کرد و حجم تراکنش ها نیز رشد پیدا کرد و این طول زمانی به صورت قابل توجهی کاهش پیدا کرد. کمترین طول زمان لازم برای یک میلیون تراکنش 2 روز میباشد که مربوط به سال 2020 میباشد. مشاهده میشود که تعداد تراکنش و حجم معاملات که در ابتدا رشد بالایی داشت، در طی سال ها این رشد به شدت کاهش یافت و تقریبا به مقدار ثابتی رسیده است و می تواند به نوعی نشان دهنده عدم مقیاس پذیری این شبکه و استقبال محدود کاربران از این شبکه باشد.
توزیع درجه
ابتدا ما دو جنبه، اندازه شبکه(تعداد گره ها و یالها) و میانگین درجه را آنالیز میکنیم، برای درک بهتر تغییرات بیتکوین و مقایسه با دیگر ارزهای دیجیتال، نمودار تغییرات بیتکوین همراه با دو رمز ارز دیگر (Namecoin و Ethereum) نمایش داده شده است.
تعداد گره‌ها و یالها به نوعی نشان دهنده اندازه شبکه میباشد و نرخ تطابق و رقابت پذیری ارز را نشان می‌دهد . با توجه به شکل پایین ، فرآیند رشد شبکه را میتوان به دو فاز تقسیم کرد :
فاز ابتدایی: سیستم فعالیت کم دارد و کاربران ارز را فقط به صورت آزمایشی و برای مقایسه با دیگر ارزها و یافتن مزایای آن، امتحان می‌کنند.
فاز معاملاتی : با تعداد مشخصی از پذیرندگان(adopters)، رشد کند شده و تغییر شدیدی نمیکند، یک دلیل این است که ارز دائما بخاطر رقابت با دیگر ارزها پذیرفته و رد میشود.
دلیل طولانی بودن فاز اولیه بیتکوین(دو و نیم سال اول) در مقایسه با Namecoin و Ethereum ، این است که طی سال‌های اولیه، رمز ارز، مفهومی جدید بود و بیتکوین تنها ارز دیجیتال موجود در بازار بود و کاربرانی که می‌خواستند ارز دیجیتال را امتحان کنند گزینه ی دیگری نداشتند.
با تحلیل میانگین درجه طی زمان میتوانیم تمایل شبکه به چگال تر شدن را بررسی کنیم. الگوی رشد در شکل زیر برای سه شبکه مختلف متفاوت میباشد، برای بیتکوین میانگین درجه تا سپتامبر 2015 روند صعودی داشت سپس روند نزولی به مدت حدود دو سال تا جولای 2017 ادامه یافت که احتمالا بخاطر ماینینگ سخت و نوسان شدید قیمت بیتکوین بوده است و همچنین از طرفی دیگر اتریوم، گزینه جدیدی به نام قرارداد هوشمند برای کاربران رمز ارز ارائه کرد.
با بررسی تکامل شبکه بیتکوین طی زمان(شکل پایین) مشاهده میکنیم که در بیتکوین نسبت تعداد یال به گره از قانون توانی(power law) تبعیت میکند، این قانون شبکه بیان میکند که نرخ رشد یالها نسبت به رشد گره‌ها سوپر خطی(super linear) میباشد. تحول شبکه بیتکوین نشان می‌دهد که آدرس‌های بیتکوین به صورت مستمر ایجاد میشود و یالها به صورت سوپر خطی به عنوان تابعی از رشد حساب‌های جدید، افزایش می‌یابد، که باعث افزایش سازگاری و استفاده از سیستم اقتصادی بیتکوین را نتیجه می‌دهد.
قانون توان چگالی(densification power law) به صورت ریاضی به شرح زیر است :
E(t) ∝ N(t)^ α where 1 < α ≤ 2
که E(t) و N(t) تعداد یال ها و گره های گراف در زمان t می‌باشند شبکه تراکنش های بیتکوین طی زمان متراکم‌تر میشود و با شیب α = 1.15 با توجه به شکل بالا فیت میشود. توجه شود که مقدار α برای شبکه های مختلف در رنج بین یک و دو میباشد، به عنوان مثال این عدد برای شبکه arXive و emails به ترتیب برابر با 1.69 و 1.12 میباشد.
در شکل زیر توزیع درجه ورودی و خروجی بین سال‌های 2010 تا 2013 را مشاهده میکنیم که از قانون توان تبعیت میکند و تعداد زیادی از گره ها درجه پایینی دارند و تنها کسر کوچکی درجه بالا دارند. برای این دو نمودار شکل پایین ضریب α برای درجه ورودی(indegree) و درجه خروجی(outdegree) به ترتیب 2.18 و 2.06 میباشد. این مقدار برای شبکه‌های واقعی مقداری بین 2 و 3 دارد.(typically 2 ≤ α ≤ 3)
میانگین ضریب خوشه بندی (Average clustering coefficient)
میانگین ضریب خوشه بندی احتمال ارتباط گره های همسایه(ایجاد مثلث) را محاسبه میکند. در شکل زیر این معیار برای تراکنش های بیتکوین از سال 2009 تا 2020 نشان داده شده است. مشاهده میشود که در 20 میلیون تراکنش اول بیتکوین مقدار c حدود 0.13 میباشد که دلیل غیرعادی بودن این ضریب بخاطر کمبود معامله‌گر در فاز ابتدایی میباشد. پس از فاز ابتدایی میانگین ضریب خوشه بندی نسبتا پایدار شده و بین 0.04 و 0.05 ثابت می‌ماند.
نتیجه گیری
با بررسی شبکه تراکنش های بیت کوین، مخصوصا بعد از سال های 2013، 2014 که فاز ابتدایی خودش را تمام کرد و به حالت پایداری رسید، مشاهده می کنیم که این شبکه، از قانون power law که یک ویژگی مهم در اکثر شبکه های واقعی است و بیانگر تمرکز قدرت می باشد تبعیت میکند، با این که هدف اصلی شبکه بیت کوین، عدم تمرکز و توزیع شبکه تا جای ممکن بود. همچنین نکته جالبی که در بررسی ها به آن اشاره شد، برخلاف انتظار، تعداد تراکنش و حجم معاملات که در ابتدا رشد بالایی داشت، در طی سال ها این رشد به شدت کاهش یافت و تقریبا به مقدار ثابتی رسیده است و می تواند به نوعی نشان دهنده عدم مقیاس پذیری این شبکه و استقبال محدود کاربران باشد. علاوه بر این، با توجه به قانون توان چگالی، شبکه تراکنش‌های بیتکوین مانند اکثر شبکه های واقعی، نرخ رشد یال ها نسبت به گره ها بالاتر است و شبکه طی زمان چگال تر میشود.
مقدمه
در بخش اول، روش مدل کردن شبکه گراف تراکنش های بیتکوین را بررسی کردیم و خصوصیات این شبکه را در بازه های مختلف زمانی تحلیل کردیم، در این بخش با استفاده از از داده‌های تراکنش‌های بیتکوین مربوط به یک دوره کوتاه دو هفته که در وبسایت Kaggle موجود است را به صورت یک شبکه گراف مدلسازی می کنیم و خصوصیات آن را بررسی میکنیم سپس نشان می‌دهیم که با بهره گیری از تکنیک های یادگیری ماشین و هوش مصنوعی میتوان تراکنش‌های مشکوک در این شبکه را کشف کرد.
کد مربوط به قسمت پیاده‌سازی در وبسایت گیت هاب به آدرس زیر قرار داده شده است، لازم به ذکر است که برای استخراج دیتاست از وبسایت Kaggle نیاز به اکانت وبسایت است.
دیتاست Elliptic Bitcoin
ما از مجموعه داده Elliptic Bitcoin Data Set (kaggle)استفاده می کنیم که توسط وبر و همکارانشان به عنوان بخشی از مقاله آنها در KDD 2019 ارائه شده است. این مجموعه داده را می توان به عنوان یک گراف جهت دار تفسیر کرد که در آن گره ها تراکنش ها را نشان می دهند و یال ها جریان بیت کوین ها را از یک تراکنش به تراکنش دیگر نشان می دهند. در زیر تجسم زیرمجموعه ای از مجموعه داده است که به صورت گراف نشان داده شده است.
هر تراکنش یا قانونی است یا غیر قانونی. در شکل زیر گره های زرد در شکل نشان دهنده تراکنش های غیرقانونی هستند در حالی که گره های بنفش نشان دهنده تراکنش های قانونی هستند.
هر گره دارای 167 ویژگی ثبت شده(مانند کارمزد تراکنش، تعداد ورودی و خروجی، حجم خروجی و ...) و همچنین یک مهر زمانی(timestamp) است که به ما می گوید چه زمانی تراکنش پست شده است. در مجموع 49 مُهر زمانی متمایز وجود دارد و گام های زمانی (از 1 تا 49) به طور مساوی با فاصله ای حدود دو هفته قرار می گیرند. یک مهر زمانی همچنین یک زیرگراف متصل را توصیف می کند که نشان دهنده تراکنش های اضافه شده به بلاک چین در کمتر از سه ساعت بین یکدیگر است.
سه جدول برای دانلود از مخزن داده Kaggle در دسترس است:
- جدول یالها: یال های بین تراکنش های بیت کوین (گره های شناسایی شده توسط شناسه تراکنش) لازم برای ساخت گراف
-جدول گروه بندی گره‌ها: به سه کلاس قانونی ، غیر قانونی و ناشناخته تقسیم شده‌اند.
- جدول مشخصه ها با 168 ستون
اطلاعات کلی دیتاست به صورت زیر میباشد
گراف تراکنش‌های بیت کوین
ما داده های خود را در قالب جدول داریم، اما می خواهیم خصوصیات گراف ساخته شده از داده ها را بررسی کنیم. برای ایجاد گراف تراکنش، از کتابخانه networkx استفاده می کنیم. یک مولتی گراف جهت دار ایجاد می کنیم (گراف جهت دار که اجازه می دهد چندین یال بین دو گره وجود داشته باشد) و ویژگی labelرا به هر تراکنش اضافه می کنیم. حال میتوانیم نشان دهیم که 49 مؤلفه متصل (کامپوننت‌های ضعیف مرتبط در مورد گراف های جهت‌دار) برای هر گام زمانی ساخته شده است. این به این معنی است که مجموعه داده شامل 49 زیرگراف مختلف است که هر کدام مربوط به یک گام زمانی است که در شکل زیر، زیرگراف مربوط به دو گام زمانی 25 و 45 نمایش داده شده است
با توجه به شکل، می بینیم که بیشتر تراکنش ها برچسب گذاری نشده اند و از بین برچسب دار ها، تنها تعداد کمی مربوط به تراکنش های غیرقانونی است. همچنین شبکه دارای چگالی بسیار پایینی است .
در شکل زیر خصوصیات زیرگراف‌ها با گام زمانی متفاوت نمایش داده شده است، مشاهده میکنیم که در هر گام زمانی، تعداد گره های شرکت کننده در تراکنش ها حدود 5000 می باشد و متوسط درجه حدود 2 میباشد و به همین ترتیب چگالی زیرگراف ها زیر 0.0005 میباشد که خیلی پایین است همچنین ضریب کلاسترینگ زیرگراف ها کمتر از 0.02 می باشد که عدد نسبتا پایینی است، البته چون هر کدام از این زیرگراف ها مربوط به یک گام زمانی میباشد، تنها بیانگر رابطه بین گره ها در یک دوره کوتاه میباشد.
طبقه بندی تراکنش‌ها
در این بخش دو روش مختلف برای طبقه بندی تراکنش ها بررسی می کنیم.
1.روش Label Propagation
الگوریتم انتشار برچسب (LPA) یک الگوریتم تکرار است که در آن با انتشار برچسب ها از طریق مجموعه داده، برچسب ها را به نقاط بدون برچسب پخش می دهیم. این الگوریتم برای اولین بار توسط (Ghahramani, 2002) در سال 2002 ارائه شد. LPA تحت یادگیری transductive قرار می گیرد، زیرا ما می خواهیم برچسب های نقاط داده بدون برچسب را پیش بینی کنیم.
فرض کنید شبکه ای از افراد داریم که در زیر آورده شده است با دو دسته برچسب "علاقه مند به کریکت" و "علاقه مند به کریکت" نیست. بنابراین سؤال این است که آیا می توانیم پیش بینی کنیم که آیا افراد باقی مانده به کریکت علاقه دارند یا خیر؟
برای اینکه LPA در این مورد کار کند، باید یک فرضیه بسازیم. یالی که دو گره را به هم متصل می کند مفهوم شباهت را به همراه دارد. یعنی اگر دو نفر با هم مرتبط باشند، به این معنی است که به احتمال زیاد این دو نفر علایق مشترکی دارند. ما می توانیم این فرض را داشته باشیم زیرا مردم تمایل دارند با افراد دیگری که علایق مشابهی دارند، ارتباط برقرار کنند.
قدم زدن تصادفی درشبکه(Walking Randomly in the Graph)
نمودار نمونه ارائه شده در شکل زیر را در نظر بگیرید، که در آن 2 کلاس برچسب (قرمز و سبز) و 4 گره رنگی داریم. می خواهیم برچسب گره 4 را پیش بینی کنیم.
میتوانیم به‌طور تصادفی در نمودار قدم بزنیم، از گره 4 شروع کنیم تا زمانی که با هر گره برچسب‌گذاری شده مواجه شویم. وقتی به یک گره برچسب خورده برخورد می کنیم، راه رفتن را متوقف می کنیم. از این رو، این گره های برچسب گذاری شده به عنوان حالت های جذب شناخته می شوند. بیایید همه راه‌های ممکن از گره 4 را در نظر بگیریم. از همه راه‌های ممکن، راه‌های زیر به یک گره سبز ختم می‌شوند.
4 → 9 → 15 → 16
4 → 9 → 13 → 14
4 → 9 → 13 → 15 → 16
4 → 9 → 15 → 13 → 14
و قدم زدن‌های زیر به یک گره قرمز ختم خواهند شد.
4 → 7 → 8
4 → 7 → 6 → 5 → 1
4 → 5 → 1
4 → 5 → 6 → 7 → 8
4 → 2 → 1
بر اساس تمام قدم زدن های تصادفی ممکن که از گره 4 شروع می‌شوند، میتوانیم ببینیم که اکثر مسیرها به یک گره قرمز ختم می‌شوند. بنابراین، می توانیم گره 4 را قرمز رنگ کنیم. این شهود اساسی پشت LPA است.
فرمول بندی ریاضی
اجازه دهید Xₗ مجموعه گره‌های برچسب‌گذاری شده باشد و Yₗ برچسب‌های one-hot داده‌های برچسب‌گذاری شده باشد. فرض کنید برچسب های کلاس {1,…,C} وجود دارد. Xᵤ رئوس بدون برچسب هستند. ما Yᵤرا نمی دانیم و از این رو Yᵤ حاوی صفر خواهد بود.
می توانیم قدم زدن های تصادفی را به صورت زیر بیان کنیم
در فرم ماتریسی، معادله به شکل زیر خواهد بود
دلیل قرار دادن مقدار بینهایت برای گام این است که، بعد از رسیدن به یکی از گره‌های برچسب دار، دیگر قدم زدن را ادامه نمی‌دهد و در همان نقطه باقی می‌ماند و به توعی با گام بینهایت، نقاط انتهایی قدم زدن را به دست می‌آوریم. اگر بتوانیم ماتریس انتقال احتمالی T (probabilistic transition matrix T)را محاسبه کنیم، می توانیم تمام احتمالات برچسب گره های بدون برچسب را محاسبه کنیم.
چگونه ماتریس انتقال احتمالی را محاسبه کنیم؟
گراف نمونه را با حالت های جذبی(absorbing states) که در شکل بالا نشان داده شده است در نظر بگیرید. برای هر گره، باید احتمال پرش به گره های دیگر را محاسبه کنیم. هنگامی که به حالت های جذبی می رسیم، قدم زدن به پایان می رسد زیرا ما در حالت جذب به دام می افتیم (که به عنوان یک حلقه خود در نمودار نشان داده می شود). این یک نمودار بدون جهت است، بنابراین ما می توانیم در هر جهت حرکت کنیم.
با فرض اینکه احتمال انتقال از یک گره به همسایگانش برابر است، می توانیم T را به صورت زیر بنویسیم.
احتمال رسیدن از گره 1 به گره 1 برابر با 1 است زیرا گره 1 حالت جذبی است. از گره 1 نمی توانیم به هیچ گره دیگری برسیم. بنابراین احتمال دستیابی به گره های دیگر از گره 1برابر با صفر خواهد بود. به همین ترتیب برای گره 2 نیز همین شرایط وجود دارد.
از گره 4، می توانید به گره های 1، 3 و 5 بروید. بنابراین به همان اندازه احتمال انتقال از گره 4 به گره های 1، 3 و 5 با احتمال 0.33 برای هر گره وجود دارد. به همین ترتیب، از گره 5، می توانیم به گره های 4 و 6 با احتمال 0.5 برای هر گره حرکت کنیم.
توجه داشته باشید که می توانیم Tرا با استفاده از ماتریس درجه (D) و ماتریس مجاورت (A) گراف با استفاده از رابطه زیر محاسبه کنیم.
T = D⁻¹A
در این صورت 2^T ماتریس انتقال احتمالی پس از یک بار قدم زدن را نشان می‌دهد. وقتی T را به توانی بسیار بزرگ برسانید، احتمالات تغییر نمی کنند (اشباع می شوند) و منجر به احتمالات انتقال ثابت می شوند.
پیاده سازی روش LPA
ابتدا جدول مشخصه و برچسب ها را ادغام میکنیم تا بتوانیم گره هایی بدون برچسب که شامل بخش بزرگی از گره ها می باشند را حذف کنیم، همچنین به دلیل محدودیت رم لپ تاپ و colab مجبوریم تنها بخشی از گراف را برای تحلیل جدا کنیم، که گام زمانی بین صفر تا 20 را انتخاب می کنیم.
جدول را براساس گام زمانی مرتب کنیم و برای گره ها به جای آی دی طولانی، از صفر شماره گذاری می کنیم، سپس تمام داده مربوط به شبکه را به torch_geometric.dataوارد می کنیم تا بتوانیم بعدا تحلیل راحت تری داشته باشیم.
داده ها را به مجموعه های آموزش/ اعتبارسنجی/آزمون با نسبت 0.7/0.15/0.15 تقسیم می کنیم. از روش تقسیم stratified split استفاده می کنیم زیرا برچسب ها به شدت نامتعادل هستند (گره های غیرقانونی بسیار کمتری نسبت به گره های قانونی وجود دارد) و می خواهیم مطمئن شویم که هر پارتیشن دارای گره های غیرقانونی کافی است. علاوه بر این، بر اساس مهر زمانی تقسیم نمی کنیم.
فانکشن LPA(k) را تعریف میکنیم که k گام در گراف حرکت میکند یا به معنای دیگر ماتریس انتقالی به توان k می رساند، حال با استفاده از این فانکشن و داده train_dataبرچسب گره های بدون برچسب را برای مقادیر مختلف k(بین 1 تا 9) را محاسبه میکنیم، با استفاده از validation_data، می توانیم f1_score را برای kهای مورد نظر محاسبه کنیم که نتایج به صورت زیر میباشد
که نشان می دهد بعد از k=6 به مقدار ثابتی می رسیم، پس این عدد بهترین مقدار برای پیش بینی برچسب های test_data می باشد. در حالت k=6 نتایج زیر برای داده تست به دست می آید
مقدار دقت 0.95 می باشد و عدد بالایی است ولی نمی تواند نشان دهنده دقت بالای مدل باشد زیرا نسبت گره های غیرقانونی به قانونی بسیار پایین می باشد و حتی با فرض پیش بینی تمام گره ها به عنوان قانونی، به دقت بالای 90 درصد به سادگی می توان رسید پس در این شرایط معیار f1 می تواند، معیار خوبی برای ارزیابی باشد که ترکیبی از دو معیار precisionو recall می باشد. مقدار f1حدود 0.4 است که نسبتا مقدار پایینی می باشد.
با توجه به ماتریس confusion_matrix، تعداد 2089 گره به درستی قانونی(true negatives) تشخیص داده شده اند، تعداد 97 گره به اشتباه قانونی(false negatives) تشخیص داده شده است، 35 گره به درستی غیرقانونی(true positives) تشخیص داده است و 9 گره قانونی را به اشتباه غیرقانونی(false positives) پیش بینی شده است.
با توجه به این که از 132 گره غیرقانونی، تنها توانسته 35 گره را درست تشخیص بدهد، معیار recall به همین خاطر خیلی پایین می باشد و نشان می دهد این مدل، ابزار خوبی برای تشخیص تراکنش‌های غیر قانونی نیست.
2. روش Graph Convolutional Networks (GCN)
چالش استفاده از گراف در شبکه عصبی
در تشخیص گفتار، واج(phoneme) Yᵢ و مدل آکوستیک xᵢ یک HMM (گرافی برای تشخیص گفتار) تشکیل می دهند.
در CNN، یک تصویر ورودی می تواند به عنوان یک نمودار مدل شود. به عنوان مثال، نمودار سمت راست زیر نمودار یک تصویر 5 × 5 است. هر گره نشان دهنده یک پیکسل است و برای فیلتر 3×3، هر گره به هشت همسایه مستقیم خود متصل است.
حتی اگر نشان دادن یک تصویر به این شکل اغراق آمیز است، این نوع مدل کردن توسط یک گراف در یادگیری ماشین (ML) بسیار موثر خواهد بود. در CNN، ما در فضای اقلیدسی کار می کنیم. نحوه ارتباط وزن ها با ویژگی های ورودی (پیکسل) به خوبی تعریف شده است.
به طور کلی، شبکه های عصبی (NN) ورودی x را برای پیش بینی z می گیرند.
حال، فرض کنید ارتباطات دوستان در یک شبکه اجتماعی را به صورت گراف زیر نمایش دهیم، چالشی که برای تحلیل این شبکه با استفاده از شبکه عصبی داریم این است که چگونه یک NN می تواند یک گراف را به طور مستقیم پردازش کند، با توجه به این که روابط بین گره‌های همسایه نامنظم و دارای ابعاد بالا هستند.
در GCN (شبکه کانولوشن گراف)، ورودی به NN یک گراف خواهد بود. همچنین با توجه به شکل زیر، به جای به دست آوردن خروجی منفرد z ، مقدار zᵢ را برای هر گره i در گراف به دست می آورد. و برای پیش‌بینی Zᵢ، GCN از Xᵢ و گره‌های همسایه‌اش در محاسبه استفاده میکند.
مدل GCN(Graph Convolutional Networks)
ایده کلی GCN این است که کانولوشن را روی یک گراف اعمال کند. به جای داشتن یک آرایه دوبعدی به عنوان ورودی، GCN یک گراف را به عنوان ورودی می گیرد.
در شکل زیر، نمودار اول (ردیف اول) همان طور که می دانیم NN است و نمودار دوم GCN با یک گراف شامل چهار گره به عنوان ورودی است.
مدل NN، حاوی چندین لایه متراکم (لایه های کاملاً متصل) است. x ورودی لایه اول و zᵢ خروجی لایه i است. برای هر لایه، z (یا x برای لایه اول) را با ماتریس وزن W چند برابر می کنیم و خروجی را به تابع فعالسازی σ می فرستیم، مثلا ReLU.
مدل GCN بسیار شبیه NN است، اما ورودی σ به جای Wᵢzᵢ ، ورودی ÂHⁱWⁱ است که در آن zᵢ و Hⁱ بردارهای خروجی از آخرین لایه پنهان برای NN و GCN هستند. اما توجه داشته باشید که Wⁱ و Wᵢ متفاوت هستند و ابعاد متفاوتی دارند. و برای اولین لایه در GCN، X شامل آرایه ای از گره ها به جای یک گره منفرد x است. X (ورودی GCN) به صورت یک ماتریس تعریف می شود که هر ردیف دارای ویژگی های یک گره است.
ماتریس Â چیست؟ GCN یک ماتریس مجاورت A را معرفی می کند. اگر گره i و j به هم متصل باشند، عنصر Aᵢⱼ در A برابر است با 1، در غیر این صورت صفر می شود. بنابراین Â همسایگان یک گره را نشان می دهد. اما ما یک تنظیم دیگر انجام خواهیم داد تا نشان دهیم همه گره ها به خود متصل هستند. این نشان می دهد که خروجی یک گره در یک لایه پنهان به خودش و همسایگانش بستگی دارد. بنابراین، تمام عناصر مورب A را به 1 تبدیل می کنیم تا ماتریس Â. ایجاد شود. از نظر ریاضی Â ، برابر با A + I است.
با توجه به خروجی لایه پنهان σ(ÂHⁱWⁱ)، اگر W را برای موقتا نادیده بگیریم، برای هر گره در یک لایه پنهان، ÂHⁱ ویژگی های هر گره را با همسایگانش خلاصه می کند.
برای جلوگیری از مشکل کاهش یا انفجار(diminishing or exploding problem) در GCN، ماتریس  باید نورمالایز شود تا مقیاس بردارهای مشخصه خروجی حفظ گردد. یک روش، ضرب  با D̂⁻¹ است که در آن D ماتریس درجه هر گره  است. در یک سطح بالا، به جای اینکه خودش را با همسایه‌اش جمع کند، حاصل جمع را به D̂⁻¹ ضرب میکنیم تا آنها را به‌طور میانگین محاسبه کنیم. به طور خاص، D̂ یک ماتریس مورب است که هر عنصر مورب آن D̂ᵢᵢ تعداد یال ها را برای گره مربوطه i می شمارد. و خروجی برای هر لایه پنهان به جای σ(ÂHⁱWⁱ) تبدیل به σ(D̂⁻¹ÂHⁱWⁱ) می شود.
به عنوان مثال ماتریس D̂ را برای گراف زیر محاسبه می کنیم . برای یک گراف بدون جهت، درجه یک گره به تعداد دفعاتی که یک یال به آن گره ختم می شود، شمرده می شود. بنابراین یک حلقه خودکار دو برابر خواهد شد. در مثال ما، گره 0 دارای 2 یال است که به همسایگان خود متصل می شود به اضافه یک حلقه self-loop. درجه آن برابر است با 4 (یعنی 2 + 2). برای گره 3، درجه آن برابر است با 5 (3 + 2).
نمودار زیر مدل مورد بحث تا کنون را خلاصه می کند. در این مثال، مدل دارای 3 لایه پنهان است و برای هر لایه پنهان، خروجی آن را به صورت σ(D̂⁻¹ÂHⁱWⁱ) محاسبه می کند.
از نگاه دیگر، GCN اطلاعات را از همسایگان هر گره با استفاده از شبکه های عصبی تجمیع می کند. هر گره ای که از یک لایه GCN عبور می کند، پیام وزن شده از گره های همسایه را که با درجه گره آن نرمال شده است، خلاصه می کند. یک تابع فعالسازی sigmoid یا ReLU به صورت اختیاری به پیام یا تجمیع اضافه میشود تا مقداری غیرخطی را شامل شود، که بیانگر بودن مدل(model’s expressiveness) را افزایش می‌دهد.
ساخت مدل GCN
ما ماژول‌های یادگیری عمیق مانند batch normalization ، dropout و تابع های فعالسازی را در معماری GCN خود به کار می‌گیریم و در پیاده سازی در مجموع از سه لایه GCN استفاده کردیم.
داده ها را به مجموعه های آموزش/ اعتبارسنجی/آزمون با نسبت 0.7/0.15/0.15 تقسیم می کنیم. از روش تقسیم stratified split استفاده می کنیم زیرا برچسب ها به شدت نامتعادل هستند (گره های غیرقانونی بسیار کمتری نسبت به گره های قانونی وجود دارد) و می خواهیم مطمئن شویم که هر پارتیشن دارای گره های غیرقانونی کافی است.
برای طبقه‌بندی نتیجه(پیش‌بینی قانونی یا غیرقانونی بودن یک گره تراکنش)، ورودی اولیه ما(hᵤ⁰)، بردارهای ویژگی هر گره در مجموعه داده های Elliptic می باشد که دارای 166 بعد است. برای معیارهای ارزیابی، precision ، recall و f1(ترکیبی از دو معیار قبلی)را به کار می‌گیریم و میزان عملکرد مدل را از جنبه‌های مختلف اندازه‌گیری میکنیم.
تحلیل نتایج مدل GCN
نمودارهای خروجی زیر که سمت راست مربوط به معیار f1در حالت train(آبی) و validation(قرمز) می باشد و سمت چپ مربوط به مقدار loss در حین trainاست همچنین محور x بیانگر تعداد epochای است که مدل train شده است.
تقریبا در epoch نزدیک به 500 مقدار پیشرفت دقت و کاهش loss افقی شده و نیازی به ادامه یادگیری مدل نیست. نتایج ارزیابی مدل بر روی داده های testرا در شکل زیر مشاهده می کنیم
مقدار دقت(acc) 0.97 می باشد و عدد بالایی است ولی نمی تواند نشان دهنده دقت بالای مدل باشد زیرا نسبت گره های غیرقانونی به قانونی بسیار پایین می باشد و حتی با فرض پیش بینی تمام گره ها به عنوان قانونی، به دقت بالای 90 درصد به سادگی می توان رسید پس در این شرایط معیار f1 می تواند، معیار خوبی برای ارزیابی باشد که ترکیبی از دو معیارprecision وrecall می باشد. مقدار f1 حدود 0.75 است که نسبتا مقدار بالایی می باشد.
با توجه به ماتریس confusion_matrix، تعداد 2083 تراکنش به درستی قانونی(true negatives) تشخیص داده شده اند، تعداد 43 تراکنش به اشتباه قانونی(false negatives) تشخیص داده شده است، 89 تراکنش به درستی غیرقانونی(true positives) تشخیص داده است و 15 تراکنش قانونی را به اشتباه غیرقانونی(false positives) پیش بینی شده است.
با توجه به این که از 132 تراکنش غیرقانونی، توانسته 89 تراکنش را درست تشخیص بدهد، معیار recall به همین خاطر حدود 0.67 می باشد. این مدل، روش بهتری برای پیدا کردن و تشخیص تراکنش های غیر قانونی نسبت به روش LPAاست.
نتیجه گیری
برای تشخیص تراکنش های مشکوک باتوجه به دیتاستی که داشتیم از دو روش LPAو GCN استفاده کردیم که در جدول زیر نتایج این دو روش را مشاهده می کنیم
مشاهده می کنیم که روش GCN در مقایسه با روش مبتدی LPA، نتایج بسیار بهتری می دهد و در تشخیص تراکنش های مشکوک کاراتر می باشد. البته نتایج ما علاوه بر روش، به نوع تقسیم بندی داده در هنگام train نیز وابسته است که ما در روش هایی که بررسی کردیم به صورت رندوم، دیتاست را تقسیم کردیم ولی میتوان با توجه به برچسب زمانی نیز جدا کرد. همچنین می توان مدل های بهینه تر GCN و همچنین ترکیب دو روش مطرح شده استفاده کرد تا بتوان دقت را افزایش داد تا بتوان به روش هایی بهینه و موثر برای تشخیص تراکنش های مشکوک در شبکه بیت کوین دست یافت.
A GRAPH-BASED INVESTIGATION OF BITCOIN TRANSACTIONS [Journal] / auth. Chen Zhao & Yong Guan. - 2015.
Anti-Money Laundering in Bitcoin: Experimenting with Graph Convolutional Networks for Financial Forensics [Journal] / auth. M. Weber G. Domeniconi, J. Chen, D. K. I. Weidele, C. Bellei, T. Robinson. - 2019.
Bitcoin transactions as a graph [Journal] / auth. Zhensheng Di, Guan Wang, Lili Jia, Zhuoyi Chen. - 2022.
Do the rich get richer? An empirical analysis of the BitCoin transaction network [Journal] / auth. Dániel Kondor, Márton Pósfai, István Csabai, Gábor Vattay. - 2014.
Elliptic Data Set [Online] / auth. kaggle. - https://www.kaggle.com/ellipticco/elliptic-data-set.
Evolutionary dynamics of cryptocurrency transaction networks [Journal] / auth. Jiaqi Liang, Linjing Li, Daniel Zeng. - 2018.
Fraud Detection on Bitcoin Transaction Graphs Using Graph Convolutional Networks [Online] / auth. Li Cynthia. - 2022. - https://medium.com/stanford-cs224w/fraud-detection-on-bitcoin-transaction-graphs-using-graph-convolutional-networks-5fc50a903687.
Graph Convolutional Networks (GCN) & Pooling [Online] / auth. Hui Jonathan. - 2021. - https://jonathan-hui.medium.com/graph-convolutional-networks-gcn-pooling-839184205692.
Graph Convolutional Networks for Fraud Detection of Bitcoin Transactions [Online] / auth. Arcos-Díaz Dario. - https://www.arcosdiaz.com/blog/graph%20neural%20networks/fraud%20detection/2019/12/15/btc-fraud-detection.html.
Illegal Bitcoin Transactions? Not on Graph ML’s Watch! [Online] / auth. Hugh Grant. - 2022. - https://medium.com/stanford-cs224w/illegal-bitcoin-transactions-not-on-graph-mls-watch-23a76c6c5b98.
Intro to Graphs and Label Propagation Algorithm in Machine Learning [Online]. - https://www.youtube.com/watch?v=OI0Jo-5d190.
Label Propagation Demystified [Online]. - https://towardsdatascience.com/label-propagation-demystified-cd5390f27472.
Learning from labeled and unlabeled data with label propagation [Journal] / auth. Ghahramani Xiaojin Zhu and Zoubin. - 2002.
The Anti-Social System Properties: Bitcoin Network Data Analysis [Journal] / auth. Israa Alqassem; Iyad Rahwan; Davor Svetinovic. - 2020.
