陳志揚(yáng) 曹金璇 聶世民

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

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

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

中圖分類號(hào)：TP393文獻(xiàn)標(biāo)識(shí)碼：A 文章編號(hào)：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 引言

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

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

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

本文首先介紹了當(dāng)前社交網(wǎng)絡(luò)中基于結(jié)構(gòu)特征和屬性特征的群體挖掘方法，提出一種基于特定用戶的群體關(guān)系挖掘與分析方法。改進(jìn)了基于最短路徑的圖聚類算法，以此對(duì)特定用戶進(jìn)行關(guān)系關(guān)聯(lián);針對(duì)群體擴(kuò)展，提出一種基于節(jié)點(diǎn)屬性動(dòng)態(tài)權(quán)重的群體相似性度量方法，構(gòu)造了初級(jí)群體屬性比對(duì)集合，用集合與擴(kuò)展節(jié)點(diǎn)屬性進(jìn)行比較，以此進(jìn)行群體關(guān)系擴(kuò)展;最后，采用Silhouett指數(shù)進(jìn)行聚類效果評(píng)估，為社交網(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)或者個(gè)體屬性上的可挖掘特征作為發(fā)現(xiàn)基礎(chǔ)，對(duì)具有特定組織結(jié)構(gòu)或?qū)傩蕴卣鞯挠脩糇蛹M(jìn)行挖掘的過(guò)程。通常把社交網(wǎng)絡(luò)群體發(fā)現(xiàn)方法分為基于群體結(jié)構(gòu)的圖聚類算法和基于屬性特征相似度兩類。

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

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

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

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

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

算法步驟如下：

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

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

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

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

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

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

表1為擴(kuò)展用戶與初級(jí)群體比對(duì)集合的比較列表。

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

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

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

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

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

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

3 聚類效果評(píng)估

3.1 群體挖掘評(píng)價(jià)標(biāo)準(zhǔn)

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

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

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

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

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

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

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