張文超 何逸章 王麗蘋

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

2. 新南威爾士大學(xué) 計(jì)算機(jī)科學(xué)與工程學(xué)院 澳大利亞 2052

3. 華東師范大學(xué) 軟件學(xué)院 上海 200062

前言

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

1 問題定義

給定一個(gè)二部圖G，整數(shù) 和，本文旨在設(shè)計(jì)高效的算法來計(jì)算所有的-群。

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

2.1 基于BiCore索引查詢-core

2.2 基于廣度優(yōu)先搜索的社區(qū)檢測

2.3 基于并查集的社區(qū)檢測

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

3 實(shí)驗(yàn)結(jié)果與分析

3.1 數(shù)據(jù)集

表1 實(shí)驗(yàn)過程中的數(shù)據(jù)集說明

3.2 算法的效率驗(yàn)證

圖1 BFS-CD以及UF-CD在8個(gè)數(shù)據(jù)集上的運(yùn)行時(shí)間

圖2 BFS-CD以及UF-CD 運(yùn)行時(shí)間受α 和β的影響

4 結(jié)束語