特定用戶群體關(guān)系挖掘與分析研究

陳志揚 曹金璇 聶世民

摘 要：為挖掘當(dāng)前社交網(wǎng)絡(luò)中具有相同內(nèi)在因素、特定組織結(jié)構(gòu)的群體，提出一種基于特定用戶的群體關(guān)系挖掘與分析方法。首先，以特定用戶為切入點，改進基于最短路徑的圖聚類算法，以此關(guān)聯(lián)它們之間的關(guān)系，構(gòu)建初級群體;然后，構(gòu)造初級群體屬性特征比對集合，利用動態(tài)權(quán)重相似性對其進行擴展，挖掘它們所處的群體;最后，對挖掘出的群體進行聚類效果評估。實驗結(jié)果表明，該方法聚類效果良好，能夠有效挖掘相關(guān)群體，為社交網(wǎng)絡(luò)中的群體發(fā)現(xiàn)提供了新思路。

關(guān)鍵詞：群體發(fā)現(xiàn);圖聚類;最短路徑算法;特定用戶

DOI：10. 11907/rjdk. 191909 開放科學(xué)（資源服務(wù)）標(biāo)識碼（OSID）：

中圖分類號：TP393文獻標(biāo)識碼：A 文章編號：1672-7800（2019）009-0183-05

Research on Group Relationship Mining and Analyzing Based on Specific Users

CHEN Zhi-yang1， CAO Jin-xuan1，2， NIE Shi-min1

（1. Information Technology & Network Security Institute， Peoples Public Security University of China;

2. CIC of Security & Law for Cyberspace， Peoples Public Security University of China， Beijing 100038， China）

Abstract： In order to mine the groups with the same internal factors and specific organizational structure in the current social network， a method of mining and analyzing group relationships based on specific users is proposed. Firstly， with the specific user as the entry point， the graph clustering algorithm based on the shortest path is improved， and the relationship between them is established to construct the primary group. Then， the primary group attribute feature comparison set is constructed， and the dynamic weight similarity is utilized. It is extended to mine the groups in which they are located; finally， the clustering effect is evaluated on the excavated population. The experimental results show that the method has good clustering effect and can effectively mine relevant groups， which provides a new idea for group discovery in social networks.

Key Words： group discovery; graph clustering; shortest path distance; specific users

0 引言

社會成員通過在互聯(lián)網(wǎng)上進行日常交流、信息發(fā)布以及互動交友，逐漸形成了某種穩(wěn)定關(guān)系，進而形成社交網(wǎng)絡(luò)[1]。社交網(wǎng)絡(luò)群體是一個抽象概念，群體可理解為由許多個體，由于一些相同的興趣、目的與利益等內(nèi)在因素有組織地聚集在一起形成的集合。群體內(nèi)用戶相互交流、傳遞信息[2]。

社交網(wǎng)絡(luò)群體關(guān)系挖掘具有重要意義[3]。一方面，群體關(guān)系挖掘結(jié)果具有最直接的影響價值，能在信息檢索、好友推薦、新聞傳播控制等許多方面有效應(yīng)用。另一方面，當(dāng)前社交網(wǎng)絡(luò)存在一些特殊群體[2]，這些群體基于特定的原因聚集，進行惡意有害行為，如網(wǎng)絡(luò)傳銷群體、網(wǎng)絡(luò)謠言群體和網(wǎng)絡(luò)詐騙群體等，這些群體行為常常對社交網(wǎng)絡(luò)環(huán)境造成巨大危害。將這些特殊群體進行合理管控的基礎(chǔ)便是對其進行有效挖掘。所以，群體關(guān)系挖掘?qū)τ诖龠M社交網(wǎng)絡(luò)發(fā)展和網(wǎng)絡(luò)空間安全都具有重要的研究價值[4]。

社交網(wǎng)絡(luò)群體性問題，往往最先發(fā)現(xiàn)于某些特定用戶，這些用戶之間也許并不存在直接聯(lián)系，但由于他們進行的是相同活動，則必定會通過沒有被發(fā)現(xiàn)的所在群體的其它成員進行勾連，若能找出他們之間的關(guān)系并利用群體屬性特征進行分析，即可得到較為完整的目標(biāo)群體。

本文首先介紹了當(dāng)前社交網(wǎng)絡(luò)中基于結(jié)構(gòu)特征和屬性特征的群體挖掘方法，提出一種基于特定用戶的群體關(guān)系挖掘與分析方法。改進了基于最短路徑的圖聚類算法，以此對特定用戶進行關(guān)系關(guān)聯(lián);針對群體擴展，提出一種基于節(jié)點屬性動態(tài)權(quán)重的群體相似性度量方法，構(gòu)造了初級群體屬性比對集合，用集合與擴展節(jié)點屬性進行比較，以此進行群體關(guān)系擴展;最后，采用Silhouett指數(shù)進行聚類效果評估，為社交網(wǎng)絡(luò)群體發(fā)現(xiàn)提供新方法。

1 社交網(wǎng)絡(luò)群體發(fā)現(xiàn)方法

社交網(wǎng)絡(luò)群體發(fā)現(xiàn)就是把群體作為檢索目標(biāo)，利用群體在關(guān)系結(jié)構(gòu)或者個體屬性上的可挖掘特征作為發(fā)現(xiàn)基礎(chǔ)，對具有特定組織結(jié)構(gòu)或?qū)傩蕴卣鞯挠脩糇蛹M行挖掘的過程。通常把社交網(wǎng)絡(luò)群體發(fā)現(xiàn)方法分為基于群體結(jié)構(gòu)的圖聚類算法和基于屬性特征相似度兩類。

圖2是對6個特定用戶（‘773356516，‘865386618，‘553356308，‘983345203，‘543365407，‘245364320）進行群體關(guān)系全關(guān)聯(lián)的可視化展示結(jié)果，圖3是基于改進的最短路徑圖聚類算法可視化展示結(jié)果?？梢钥闯鰣D3是對圖2使用最短路徑距離計算的結(jié)果，群體呈現(xiàn)樹狀結(jié)構(gòu)。

2.4 初級群體特定用戶節(jié)點屬性特征分析

特定用戶組成的初級群體不僅僅從結(jié)構(gòu)上有聯(lián)系，在進行群體活動時，它們還具有相同或相似的屬性特征，基于此，對特定用戶組成的初級群體拓撲圖利用關(guān)系與屬性特征相似度進行擴展。

特定用戶構(gòu)成初級群體時，它們中的相同特征越多，出現(xiàn)次數(shù)最多的那個特征權(quán)值也越大。結(jié)合初級群體關(guān)系拓撲圖與特定用戶屬性特征分析，本文提出基于初級群體特定用戶節(jié)點屬性動態(tài)權(quán)重的群體擴展算法。

初級群體中的特定用戶個體屬性信息在某種程度上反映了用戶特征。同一群體必然有相同的特征，特定用戶之間相似度最高的特征必然也是完整群體所包含的特征，基于此，利用這些特征進行擴群。本文采用對特定用戶打標(biāo)簽的方式，將標(biāo)簽作為關(guān)鍵字并對關(guān)鍵字進行分類，關(guān)鍵字分屬于不同的屬性[15]。首先對初級群體中的用戶進行分析，找出它們的相似特征，建立初級群體屬性比對集合，在與擴展群體個體用戶屬性對比時，對同一種屬性的關(guān)鍵字出現(xiàn)的次數(shù)進行統(tǒng)計，把出現(xiàn)次數(shù)最多的前n個屬性關(guān)鍵字作為該屬性占總值的比例，作為節(jié)點屬性的具體數(shù)值。本文根據(jù)群體聚類的不同目的對屬性權(quán)值進行設(shè)置，依據(jù)不同群體的劃分目的，對屬性權(quán)重大小進行分配，以此達到更加有效擴展群體的目的。

算法步驟如下：

（1）在特定用戶組成的網(wǎng)絡(luò)關(guān)系拓撲結(jié)構(gòu)（即初級群體）中，每個節(jié)點代表一個用戶，用戶存在若干屬性。假設(shè)存在n個屬性（Q1，Q2…Qn），統(tǒng)計初級群體各個用戶n個屬性分別出現(xiàn)的次數(shù)，依此建立初級群體特征屬性比對集合（R1，R2…Rn）。

（2）對初級群體進行擴展，將擴展群體中的個體用戶屬性與比對集合進行比較，各個屬性出現(xiàn)的次數(shù)設(shè)為屬性值集合為（O1，O2…On）。

（3）基于各個屬性的重要程度不同，為屬性集（O1，O2…On）每個元素分配權(quán)值P1，P2…Pn，Pi的取值，根據(jù)不同的群體特征以及屬性的相關(guān)程度動態(tài)分配權(quán)值，P1，P2…Pn需要滿足P1+P2…Pn=1。

（4）設(shè)置擴展用戶與初級群體相似度k，k的取值范圍為（0，1）。k值計算公式如下：

[ki=1nj=1nQjRjOjPj，0k1] （1）

其中，[QjRj]是各個屬性與初級群體比對集合的比值，[OjPj]是屬性集進行權(quán)值分配后的結(jié)果。

表1為擴展用戶與初級群體比對集合的比較列表。

2.5 基于節(jié)點屬性動態(tài)權(quán)重的群體擴展算法設(shè)計

接下來依照初級群體起始節(jié)點與初級群體屬性特征對初級群體進行擴展。由于社交網(wǎng)絡(luò)交錯復(fù)雜，在網(wǎng)絡(luò)數(shù)據(jù)理想的情況下，初級群體可以無限擴展[16]，但無限擴展并無意義。因此，設(shè)定擴展閾值，一次擴展代表擴展用戶的直接好友。擴展算法如下：

（1）以初級群體起始點為起始，按照初級群體特征表對比結(jié)果中的相似度k1進行第一次擴展，其中k1根據(jù)實際群體特點設(shè)定。

（2）把第一次擴展的結(jié)果設(shè)為起始節(jié)點，計算擴展節(jié)點與初級群體屬性比對集合相似度k2。按照相似度k2進行第二次擴展，其中k2根據(jù)實際群體特點設(shè)定。

（3）設(shè)置擴展閾值n，相應(yīng)的節(jié)點與初級群體屬性比對集合相似度為kn，既可逐次擴展，也可一次完成多級擴展，結(jié)合目標(biāo)群體特征進行擴展閾值設(shè)置。

對‘873567812節(jié)點進行5級好友關(guān)系擴展結(jié)果如圖4所示，擴展結(jié)果顯示了以該節(jié)點為起始點的5級好友關(guān)系路徑，圖5則是所有路徑結(jié)果的圖形可視化展示。

3 聚類效果評估

3.1 群體挖掘評價標(biāo)準(zhǔn)

對群體挖掘效果進行評估，通常采用內(nèi)聚系數(shù)、SD指數(shù)、DB指數(shù)和Silhoueete指數(shù)這幾個評價標(biāo)準(zhǔn)。

內(nèi)聚系數(shù)指聚類好的簇的標(biāo)準(zhǔn)差，標(biāo)準(zhǔn)差越小，簇內(nèi)各個節(jié)點越聚集，簇中節(jié)點與質(zhì)心的距離越小，聚類效果越準(zhǔn)確。SD指數(shù)[17]是基于簇的平均離散度和簇間總體離散度的有效評價方法。DB指數(shù)[18]用來表示簇內(nèi)分離度及簇間相似度，DB指數(shù)越小說明聚類效果越好，它是聚類指標(biāo)中最為常用的有效性指標(biāo)。Silhoueete指數(shù)[19]結(jié)合了內(nèi)聚度和離散度兩種因素，既考慮了簇內(nèi)各個節(jié)點的內(nèi)聚性，也考慮了簇與簇之間質(zhì)心的離散性。對于節(jié)點i來說，定義其Silhouett指數(shù)為：

其中A（i）指計算節(jié)點到所屬簇中所有其它節(jié)點的平均距離，B（i）指計算節(jié)點到各個非本身所在簇的所有節(jié)點的平均距離。Silhouett指數(shù)取值范圍在-1到1之間，指數(shù)越接近1，則群體關(guān)系圖聚類結(jié)果越明顯。

3.2 實驗結(jié)果與分析

實驗所用數(shù)據(jù)來自某單位經(jīng)過脫密處理的社交網(wǎng)絡(luò)數(shù)據(jù)，節(jié)點數(shù)為5 790個，邊數(shù)為2 407條。對于本實驗數(shù)據(jù)結(jié)果，由于內(nèi)聚系數(shù)、SD指數(shù)、DB指數(shù)沒有統(tǒng)一的歸一化處理[20]，所以采用Silhouett指數(shù)進行評估即可。

為避免標(biāo)準(zhǔn)數(shù)據(jù)集單一，本文抽取兩個數(shù)據(jù)集，選取6組屬性相異度較大的特定用戶進行實驗。表2是數(shù)據(jù)集與群體挖掘結(jié)果Silhouett指數(shù)對比。

實驗結(jié)果顯示：6組特定用戶的挖掘結(jié)果中，Silhouett指數(shù)有5組大于原數(shù)據(jù)集Silhouett指數(shù)。其中第5組人為選定特定用戶時，對用戶特征的判斷出現(xiàn)偏差，因此出現(xiàn)Silhouett指數(shù)略低于原數(shù)據(jù)集的情況。基于第一個數(shù)據(jù)集中3組挖掘結(jié)果（即第1、2、3組）與第二個數(shù)據(jù)集中2組挖掘結(jié)果（即第4、6組）Silhouett指數(shù)與原數(shù)據(jù)集相比，都相當(dāng)接近于1，說明本方法聚類效果良好，聚類結(jié)果具有較高的參考價值。