淺述二部圖社區檢測算法及在電子商務異常檢測中的應用

張文超 何逸章 王麗蘋

1. 中國建設銀行齊齊哈爾分行 黑龍江 齊齊哈爾 161000

2. 新南威爾士大學 計算機科學與工程學院 澳大利亞 2052

3. 華東師范大學 軟件學院 上海 200062

前言

現實生活中兩組實體之間的相互聯系常常被建模成二部圖。在二部圖上，如果一個子圖中的點相互聯系緊密，那么它被稱作一個凝聚子圖。電子商務平臺上的異常檢測是二部圖上的凝聚子圖計算的應用場景之一。電子商務平臺中的用戶常依賴于平臺顯示的商品評分和評價來做決策。許多商家為了提高口碑，會借助虛假賬號來獲得虛假的評分和訂單，以此誤導消費者[1]。為了找出惡意用戶，當前的異常檢測手段著眼于對可疑行為本身，比如對可疑用戶的特征進行總結[2]。這忽視了可疑用戶之間存在的緊密聯系，而且需要不定時地重新訓練模型。由于反欺詐技術的日益完善，惡意商戶只能依賴少數賬戶進行操作[3]。這導致這些用戶和他們嘗試推銷的商品之間形成聯系緊密的群體，因而很自然地可以被二部圖上的凝聚子圖搜索算法檢測。

1 問題定義

給定一個二部圖G，整數 和，本文旨在設計高效的算法來計算所有的-群。

2 BFS-CD算法和UF-CD算法

2.1 基于BiCore索引查詢-core

2.2 基于廣度優先搜索的社區檢測

2.3 基于并查集的社區檢測

算法4 基于并查集的社區檢測算法(UF-CD)

3 實驗結果與分析

3.1 數據集

表1 實驗過程中的數據集說明

3.2 算法的效率驗證

圖1 BFS-CD以及UF-CD在8個數據集上的運行時間

圖2 BFS-CD以及UF-CD 運行時間受α 和β的影響

4 結束語