社交網(wǎng)絡(luò)中基于K核分解的意見(jiàn)領(lǐng)袖識(shí)別算法

李美子，米一菲，張 倩，張 波，2，3*

（1.上海師范大學(xué)信息與機(jī)電工程學(xué)院，上海 201418；2.上海師范大學(xué)人工智能教育研究院，上海 201418；3.上海智能教育大數(shù)據(jù)工程技術(shù)研究中心（上海師范大學(xué)），上海 200234）

0 引言

社交網(wǎng)絡(luò)中意見(jiàn)領(lǐng)袖可以在信息傳播過(guò)程產(chǎn)生巨大的作用，其發(fā)表的言論、持有的態(tài)度等一系列行為和后續(xù)影響力可以通過(guò)用戶之間的鏈接關(guān)系產(chǎn)生逐層裂變式擴(kuò)散［1］。這種擴(kuò)散效果促使意見(jiàn)領(lǐng)袖對(duì)于預(yù)測(cè)信息傳播狀態(tài)、監(jiān)督和引導(dǎo)輿論，以及影響網(wǎng)絡(luò)信息擴(kuò)散趨勢(shì)有著極其關(guān)鍵的作用［2-4］。因此，如何發(fā)現(xiàn)并識(shí)別社交網(wǎng)絡(luò)中的意見(jiàn)領(lǐng)袖群體是當(dāng)前社交網(wǎng)絡(luò)研究的熱點(diǎn)問(wèn)題。

目前，對(duì)于意見(jiàn)領(lǐng)袖識(shí)別算法的研究主要分為三個(gè)方面：一是基于對(duì)網(wǎng)絡(luò)拓?fù)涞姆治鰜?lái)檢測(cè)意見(jiàn)領(lǐng)袖，使用網(wǎng)絡(luò)拓?fù)浞治錾缃痪W(wǎng)絡(luò)圖模型的相關(guān)特性，例如，在意見(jiàn)領(lǐng)袖挖掘中，度中心性、中介性中心性、接近中心性和K 核等都是非常有效并且常用的方法［5-7］。二是基于社交網(wǎng)絡(luò)中用戶的歷史行為數(shù)據(jù)挖掘意見(jiàn)領(lǐng)袖。朋友的數(shù)量、發(fā)布信息的總數(shù)、轉(zhuǎn)發(fā)或評(píng)論信息的總數(shù)，以及信息所表達(dá)的情感都可以用來(lái)識(shí)別意見(jiàn)領(lǐng)袖［8-9］。三是綜合考慮社交網(wǎng)絡(luò)的網(wǎng)絡(luò)拓?fù)浜陀脩舻臍v史行為數(shù)據(jù)來(lái)挖掘意見(jiàn)領(lǐng)袖。然而，這三種方法都存在以下問(wèn)題：在大型社交網(wǎng)絡(luò)中識(shí)別意見(jiàn)領(lǐng)袖時(shí)通常需要很大的計(jì)算量。盡管在社交網(wǎng)絡(luò)中并不是每一個(gè)用戶都有足夠的條件成為意見(jiàn)領(lǐng)袖，但當(dāng)前的意見(jiàn)領(lǐng)袖識(shí)別算法大多以相同的方式來(lái)評(píng)估每個(gè)用戶的重要性。

考慮到上述問(wèn)題，本文提出基于K 核分解的CR（CandidateRank）算法來(lái)識(shí)別意見(jiàn)領(lǐng)袖。該算法依據(jù)K 核分解的基本原理，結(jié)合所設(shè)置的分解規(guī)則，判定用戶是否為意見(jiàn)領(lǐng)袖的概率，將具有較大K 核值的用戶加入到建立的意見(jiàn)領(lǐng)袖候選集中，加入意見(jiàn)領(lǐng)袖候選集的用戶數(shù)由用戶的需求決定；然后提出用戶相似性的概念，其包括位置相似性和鄰居相似性，依據(jù)K 核值、入度數(shù)、平均K 核變化率和用戶追隨者個(gè)數(shù)等來(lái)計(jì)算用戶相似性，最終根據(jù)用戶相似性對(duì)候選集中的用戶計(jì)算全局影響力，以獲得所需的意見(jiàn)領(lǐng)袖。在實(shí)驗(yàn)部分使用兩種評(píng)價(jià)指標(biāo)在三個(gè)大小不同的數(shù)據(jù)集上對(duì)該算法選出的意見(jiàn)領(lǐng)袖集進(jìn)行評(píng)估，并通過(guò)與其他三種識(shí)別意見(jiàn)領(lǐng)袖的算法對(duì)比來(lái)驗(yàn)證本文算法的可行性。

對(duì)于大規(guī)模網(wǎng)絡(luò)，特別是用戶關(guān)系比較集中的一些網(wǎng)絡(luò)，其中大部分用戶都屬于“邊緣用戶”，他們幾乎沒(méi)有成為意見(jiàn)領(lǐng)袖的潛質(zhì)，但是根據(jù)一些意見(jiàn)領(lǐng)袖識(shí)別算法依然要對(duì)他們進(jìn)行計(jì)算，極大延長(zhǎng)了整體的計(jì)算時(shí)間，而本文提出的CandidateRank 算法通過(guò)建立意見(jiàn)領(lǐng)袖候選集解決了這個(gè)問(wèn)題；另外本文提出的用戶相似度的計(jì)算通過(guò)拓?fù)浣Y(jié)構(gòu)建立用戶位置向量也是比較輕量級(jí)的計(jì)算。

本文的主要工作有：

1）基于K 核分解區(qū)分社交網(wǎng)絡(luò)中的潛在意見(jiàn)領(lǐng)袖與普通用戶。在潛在意見(jiàn)領(lǐng)袖（意見(jiàn)領(lǐng)袖候選集）中識(shí)別意見(jiàn)領(lǐng)袖，能夠避免重復(fù)計(jì)算“邊緣用戶”的重要度，從而降低計(jì)算的復(fù)雜度。

2）提出平均K 核變化率的概念和計(jì)算方法，將它作為判斷位置相似性的指標(biāo)之一；提出用戶相似性包括位置相似性和鄰居相似性的概念和計(jì)算方法，以及一種有效的全局影響力的計(jì)算方法。

3）對(duì)社交網(wǎng)絡(luò)圖模型進(jìn)行K 核分解后，具有較大K 核值的用戶有較大的可能性是意見(jiàn)領(lǐng)袖，因此可以將具有最大K核值的用戶加入到意見(jiàn)領(lǐng)袖候選集中。

1 相關(guān)工作

研究表明，K 核分解可以識(shí)別社交網(wǎng)絡(luò)中最具影響力的節(jié)點(diǎn)［10］。根據(jù)用戶的K 核值，可以粗粒度地區(qū)分社交網(wǎng)絡(luò)中的潛在意見(jiàn)領(lǐng)袖與普通用戶。CandidateRank 算法的主要工作是基于K 核分解獲得潛在的意見(jiàn)領(lǐng)袖加入到意見(jiàn)領(lǐng)袖候選集中，然后依據(jù)平均K 核變化率、用戶相似性等指標(biāo)對(duì)候選集中的用戶進(jìn)行全局影響力計(jì)算，以獲得所需的意見(jiàn)領(lǐng)袖。

近年來(lái)，識(shí)別意見(jiàn)領(lǐng)袖的模型根據(jù)是否基于K 核分解可以分為兩類：和K 核分解相關(guān)的算法、和K 核分解無(wú)關(guān)的算法。與K 核分解無(wú)關(guān)的算法比較靈活，Li 等［11］提出了一種基于連續(xù)時(shí)間馬爾可夫鏈的動(dòng)態(tài)信息傳播模型來(lái)尋找有影響力的節(jié)點(diǎn)組。Aghdam 等［12］提出根據(jù)用戶之間的信任關(guān)系計(jì)算用戶的總信任值以評(píng)估出意見(jiàn)領(lǐng)袖。Xia 等［13］通過(guò)評(píng)估用戶在Twitter 中的行為來(lái)計(jì)算用戶影響力。Zhou 等［14］提出了一種擴(kuò)展的獨(dú)立級(jí)聯(lián)模型——EIC（Extended Independent Cascade model）和一種影響力最大化算法GAUP（Greedy Algorithm based on User Preference），結(jié)合用戶對(duì)信息的偏好，找到對(duì)于特定信息主題，能夠得到最大影響力的種子節(jié)點(diǎn)集。陳志雄等［15］提出了基于回帖者的情感傾向挖掘意見(jiàn)領(lǐng)袖。

與K 核分解相關(guān)的算法多集中于基于K 核值影響力算法改進(jìn)，區(qū)分具有相同K 核值的節(jié)點(diǎn)的影響力，使得意見(jiàn)領(lǐng)袖的識(shí)別更加有效或準(zhǔn)確。例如，Wei 等［16］綜合考慮邊兩端節(jié)點(diǎn)的度，構(gòu)造加權(quán)網(wǎng)絡(luò)，提出加權(quán)K 核分解方法。Yang等［17］定義局部K 核值總和（Local K-Shell Sum，LKSS），計(jì)算給定節(jié)點(diǎn)相鄰2 跳鄰居的K 核值之和，再通過(guò)計(jì)算與給定節(jié)點(diǎn)直接相連的節(jié)點(diǎn)的LKSS 總和（Extended LKSS，ELKSS）來(lái)對(duì)節(jié)點(diǎn)進(jìn)行排名。Zeng 等［18］同時(shí)考慮節(jié)點(diǎn)的K 核值和分解過(guò)程中被移除節(jié)點(diǎn)的K 核值，提出一種混合度分解（Mixed Degree Decomposition，MDD）算法。Bae 等［19］根據(jù)鄰居節(jié)點(diǎn)的K 核值來(lái)估計(jì)節(jié)點(diǎn)在網(wǎng)絡(luò)中的影響力，提出擴(kuò)展近鄰核（Extended Neighborhood Coreness，Cnc+）。Liu 等［20］認(rèn)為網(wǎng)絡(luò)中某個(gè)節(jié)點(diǎn)到網(wǎng)絡(luò)最內(nèi)核的距離能夠決定該節(jié)點(diǎn)的傳播影響力，這里網(wǎng)絡(luò)中的最內(nèi)核是指通過(guò)K-Shell 分解后，網(wǎng)絡(luò)中具有最大K 核值的節(jié)點(diǎn)（或節(jié)點(diǎn)集）；在此基礎(chǔ)上，提出了一種改進(jìn)的中心性度量方法θ。Hou 等［21］結(jié)合度中心性、介數(shù)中心性和K-Shell 分解定義了一種all-around nodes。Tong等［22］提出結(jié)合K-Shell 分解與接近中心性對(duì)網(wǎng)絡(luò)中節(jié)點(diǎn)的傳播影響力進(jìn)行排序，其主要思想是：如果某個(gè)節(jié)點(diǎn)有較大的傳播影響力，那么該節(jié)點(diǎn)除了擁有較大的K 核值以外，還應(yīng)該與網(wǎng)絡(luò)中其他節(jié)點(diǎn)之間的平均最短距離較短。和K 核分解相關(guān)的算法主要針對(duì)無(wú)法對(duì)比具有相同K 核值的節(jié)點(diǎn)之間的重要度的問(wèn)題進(jìn)行改進(jìn)，往往都是在K 核分解的基礎(chǔ)上計(jì)算社交網(wǎng)絡(luò)中所有節(jié)點(diǎn)的影響力。

2 算法和相關(guān)定義

2.1 算法結(jié)構(gòu)

如圖1，對(duì)全體用戶進(jìn)行K 核分解找出意見(jiàn)領(lǐng)袖候選集L，對(duì)L中的候選者進(jìn)行平均K 核變化率和用戶相似性計(jì)算，最終得到全局影響力。

圖1 CandidateRank算法結(jié)構(gòu)Fig.1 CandidateRank algorithm structure

2.2 算法步驟

用于檢測(cè)意見(jiàn)領(lǐng)袖的CandidateRank 算法步驟主要分為三個(gè)：

步驟1 用K 核分解獲取社交網(wǎng)絡(luò)中每個(gè)用戶的K 核值，并選擇K 核值最大的用戶加入到意見(jiàn)領(lǐng)袖候集中。

步驟2 通過(guò)多次使用K 核分解，分別計(jì)算刪除意見(jiàn)領(lǐng)袖候選集中的用戶后所造成的平均K 核變化率，用于步驟3中評(píng)估位置相似性。對(duì)于意見(jiàn)領(lǐng)袖候選集中的每個(gè)用戶，找到該用戶的追隨者集合，以及追隨者的追隨者集合，用于步驟3 計(jì)算意見(jiàn)候選集中的用戶和其追隨者的鄰居相似性。

步驟3 評(píng)估意見(jiàn)領(lǐng)袖候選集中每個(gè)用戶和其追隨者的位置相似性和鄰居相似性，計(jì)算用戶全局影響力以識(shí)別意見(jiàn)領(lǐng)袖。

2.3 相關(guān)指標(biāo)

接近中心性（Closeness Centrality）［23］：是節(jié)點(diǎn)到網(wǎng)絡(luò)中所有其他節(jié)點(diǎn)最短路徑之和的倒數(shù)，表示節(jié)點(diǎn)在網(wǎng)絡(luò)中與其他節(jié)點(diǎn)的距離，接近中心性越大，則用戶與其他用戶的距離越近。

中介中心性（Betweenness Centrality）［24］：是穿過(guò)節(jié)點(diǎn)的最短路徑占網(wǎng)絡(luò)中最短路徑的比例。

特征向量中心性（Eigenvector Centrality）［25］：基于鄰居節(jié)點(diǎn)的重要度評(píng)估節(jié)點(diǎn)重要性。

Katz 中心性（Katz Centrality）［25］：在特征向量中心性的基礎(chǔ)上，給和節(jié)點(diǎn)直接連接的鄰居以及間接連接的鄰居分配不同的影響力權(quán)值。

肯德?tīng)栂嚓P(guān)性系數(shù)（Kendall’tau）：是一種秩相關(guān)系數(shù)，計(jì)算式如下：

其中：nc與nd分別代表兩個(gè)列表中的相容元素對(duì)與不相容元素對(duì)的數(shù)量。n是列表長(zhǎng)度即列表中元素?cái)?shù)，兩個(gè)列表的長(zhǎng)度相同。

2.4 算法相關(guān)定義

一些社交平臺(tái)中用戶與用戶之間會(huì)通過(guò)一些方式產(chǎn)生公開(kāi)交互，如微博、Facebook、豆瓣等，用戶與用戶之間的行為可以構(gòu)成社交網(wǎng)絡(luò)，本文將這樣由用戶和用戶間交互關(guān)系構(gòu)成的社交網(wǎng)絡(luò)轉(zhuǎn)化為一個(gè)有向圖G=(V，M)，其中V={u1，u2，…，uN}是社交網(wǎng)絡(luò)中的節(jié)點(diǎn)（用戶）集合，N是節(jié)點(diǎn)（用戶）總數(shù)，E={e1，e2，…，eM}是邊的集合，邊表示用戶之間的互動(dòng)關(guān)系，如評(píng)論、點(diǎn)贊、轉(zhuǎn)發(fā)等行為在用戶間建立起有向關(guān)系（即有向邊），M是社交網(wǎng)絡(luò)中邊的總數(shù)。

定義 1K核值。在圖G中，若存在子圖Gk={(Vk，Ek)，Vk?V，Ek?E}，對(duì)每個(gè)節(jié)點(diǎn)v∈Vk，v的度（出度及入度）大于或等于k，則圖的子圖Gk是圖的K 核。K 核值是經(jīng)過(guò)K 核分解分配給圖中每個(gè)節(jié)點(diǎn)的重要度分值，并且當(dāng)v∈V，v?Vk時(shí)，v的K 核值等于k。

定義2全局影響力。在社交網(wǎng)絡(luò)中，用戶的影響力通過(guò)追隨者向外擴(kuò)散。用戶的追隨者越多，其在社交網(wǎng)絡(luò)中影響力的擴(kuò)散范圍越大，即全局影響力越大。本文用戶全局影響力用inf(u) 來(lái)表示，其大小計(jì)算考慮多種影響因素（第3章詳細(xì)闡述）。

定義3追隨者。在社交網(wǎng)絡(luò)圖中，若存在u，v∈V，ek∈E同時(shí)ek={u，v}，則用戶u是用戶v的追隨者。

定義4意見(jiàn)領(lǐng)袖。在社交網(wǎng)絡(luò)中，用戶的影響擴(kuò)散范圍越大，可理解為用戶的全局影響力越大，影響力最大的用戶即為意見(jiàn)領(lǐng)袖，意見(jiàn)領(lǐng)袖在大眾傳播過(guò)程中起到引領(lǐng)作用。

定義5意見(jiàn)領(lǐng)袖候選集（潛在意見(jiàn)領(lǐng)袖）。在計(jì)算用戶重要度之前，選擇最有可能成為意見(jiàn)領(lǐng)袖的用戶加入到意見(jiàn)領(lǐng)袖候選集L中，V、O、L之間的關(guān)系為O?L?V。

定義6意見(jiàn)領(lǐng)袖集。意見(jiàn)領(lǐng)袖集O是節(jié)點(diǎn)集合V的子集，由集合V中的s個(gè)節(jié)點(diǎn)組成，并且滿足條件min{inf(v)}＞max{inf(u)}，v∈O，u∈V，u?O，s是由實(shí)際需求決定的。普通用戶是除O以外的其他用戶，用C表示，且C=V-O。

本文中有4 種用戶角色：追隨者、普通用戶、意見(jiàn)領(lǐng)袖候選者和意見(jiàn)領(lǐng)袖，它們的關(guān)系可以用圖2 表示。

圖2 用戶角色關(guān)系Fig.2 User role relationship

3 基于K核分解的CandidateRank算法

在社交網(wǎng)絡(luò)中，并不是所有的用戶都有可能是意見(jiàn)領(lǐng)袖，例如新加入社交網(wǎng)絡(luò)并沒(méi)有得到其他人關(guān)注的用戶，或者在數(shù)據(jù)收集時(shí)被遺漏了大部分追隨者的用戶，這些用戶在所分析的社交網(wǎng)絡(luò)中成為意見(jiàn)領(lǐng)袖的可能性均較小。在識(shí)別意見(jiàn)領(lǐng)袖的過(guò)程中，沒(méi)有必要對(duì)這些用戶的重要度進(jìn)行評(píng)估；并且，在社交網(wǎng)絡(luò)中，大部分用戶是普通用戶，只有少數(shù)用戶是意見(jiàn)領(lǐng)袖。因此，在評(píng)估用戶重要度之前，可以通過(guò)選擇意見(jiàn)領(lǐng)袖候選集來(lái)過(guò)濾掉大部分的普通用戶。相對(duì)于所有用戶，在具有較少用戶的意見(jiàn)領(lǐng)袖候選集中確定意見(jiàn)領(lǐng)袖，既可以提高意見(jiàn)領(lǐng)袖識(shí)別的效率，又可以增強(qiáng)算法對(duì)于大規(guī)模社交網(wǎng)絡(luò)的適用性。

通過(guò)K 核分解得到的最具影響力的節(jié)點(diǎn)是一個(gè)集合，集合中節(jié)點(diǎn)的具體重要度并不明確。通過(guò)K 核分解，選擇K 核值最大的用戶加入意見(jiàn)領(lǐng)袖候選集，一方面避免了無(wú)法選擇區(qū)分普通用戶和潛在意見(jiàn)領(lǐng)袖的標(biāo)準(zhǔn)的問(wèn)題，另一方面當(dāng)具有最大K 核值的用戶總數(shù)不足時(shí)，可以選擇具有次大K 核值（即排名第二大的K 核值）的用戶補(bǔ)充到意見(jiàn)領(lǐng)袖候選集中。

3.1 K核分解

K 核分解迭代地刪除社交網(wǎng)絡(luò)圖中度小于k的節(jié)點(diǎn)及其連邊，得到子圖：k-核，k-核中每個(gè)節(jié)點(diǎn)的度值均等于或大于k。當(dāng)圖中的某個(gè)節(jié)點(diǎn)存在于圖的k-核中，而不存在圖的k+1-核中時(shí)，該節(jié)點(diǎn)的K 核值等于k。K 核分解確定了社交網(wǎng)絡(luò)中每個(gè)節(jié)點(diǎn)的K 核值，其具體步驟如下：假設(shè)社交網(wǎng)絡(luò)中每個(gè)節(jié)點(diǎn)的度均大于或等于1，整個(gè)社交網(wǎng)絡(luò)圖是G的1-核G1；然后，迭代地刪除G1中度小于2 的節(jié)點(diǎn)及其相關(guān)的邊，得到的子圖G2是圖的2-核，被刪除的節(jié)點(diǎn)存在于圖的1-核中，而不存在于圖的2-核中，所以被刪除節(jié)點(diǎn)的K 核值等于1。接下來(lái)，迭代地刪除G2中度小于3 的節(jié)點(diǎn)及其相關(guān)的邊，得到的子圖G3是圖的3-核，被刪除的節(jié)點(diǎn)存在于圖的2-核中，而不存在于圖的3-核中，所以被刪除節(jié)點(diǎn)的K 核值為2。以此類推，直到得到社交網(wǎng)絡(luò)中所有節(jié)點(diǎn)的K 核值。

選擇具有最大K 核值的用戶作為意見(jiàn)領(lǐng)袖候選集L。當(dāng)具有最大K 核值的用戶總數(shù)少于所需意見(jiàn)領(lǐng)袖總數(shù)時(shí)，將具有次大K 核值的用戶加入到意見(jiàn)領(lǐng)袖候選集L中。K 核分解得到的用戶是在圖中受到最多用戶關(guān)注或者和最多用戶有聯(lián)系的，因?yàn)樗麄兂蔀橐庖?jiàn)領(lǐng)袖的概率非常大。

3.2 平均K核變化率

在意見(jiàn)領(lǐng)袖候選集中，具有相同K 核值的用戶，其用戶重要度也不盡相同。在復(fù)雜網(wǎng)絡(luò)的節(jié)點(diǎn)重要度研究中，刪除法通過(guò)對(duì)比刪除節(jié)點(diǎn)前和刪除節(jié)點(diǎn)后網(wǎng)絡(luò)的連通性變化情況對(duì)節(jié)點(diǎn)重要度進(jìn)行排序。在本文中，意見(jiàn)領(lǐng)袖候選集中的用戶本身具有最大的K 核值，是社交網(wǎng)絡(luò)中較重要的用戶。因此，考慮通過(guò)對(duì)比刪除某個(gè)用戶前后其他用戶K 核值的變化情況，計(jì)算出平均K 核變化率，來(lái)說(shuō)明該用戶對(duì)網(wǎng)絡(luò)中其他用戶的平均影響力。平均K 核變化率的計(jì)算式如下：

其中：Sumk是社交網(wǎng)絡(luò)G中所有用戶的K 核值總和，k(u)是社交網(wǎng)絡(luò)G中用戶u的K 核值，Sum(u)是社交網(wǎng)絡(luò)G去掉用戶u及其連邊后其他用戶的K 核值總和，n是社交網(wǎng)絡(luò)中的用戶總數(shù)，L代表意見(jiàn)領(lǐng)袖候選集。以圖1（a）為例，對(duì)于用戶2，首先用戶總數(shù)n=19，再計(jì)算圖中網(wǎng)絡(luò)每一個(gè)用戶的K核值，由圖中節(jié)點(diǎn)的顏色可明顯看出該圖中的最大K 核值為4，而Sumk=36；同樣，由圖明顯得到k(2)=3。圖1（b）描述的是去掉用戶2 及其連邊之后的過(guò)程，可看到此時(shí)其他用戶的K 核值總和Sum(2)=30。綜上計(jì)算出akc(2)=0.167。

3.3 用戶相似性

在社交網(wǎng)絡(luò)中，用戶通過(guò)與其他用戶交互，擴(kuò)散自己的影響力，提高自己的重要度。平均K 核變化率能夠反映用戶在整個(gè)社交網(wǎng)絡(luò)中對(duì)其他用戶的平均影響力，但在評(píng)估用戶交互過(guò)程中擴(kuò)散影響力的能力時(shí)需要考慮相似性因素。用戶與其追隨者的相似性對(duì)追隨者對(duì)該用戶的影響力擴(kuò)散情況造成影響。在本文中，將相似性分為位置相似性和鄰居相似性。

位置相似性 位置相似性評(píng)估用戶在社交網(wǎng)絡(luò)拓?fù)湮恢蒙系南嗨菩?，通常情況下，常用度中心性、中介中心性、緊密中心性、特征向量中心性等中心性指標(biāo)來(lái)說(shuō)明用戶在社交網(wǎng)絡(luò)拓?fù)渖系奈恢茫薪橹行男?、緊密中心性和特征向量中心性的計(jì)算均涉及全網(wǎng)用戶，計(jì)算復(fù)雜度較高。同時(shí)，在有向圖中，入度數(shù)比出度數(shù)更能體現(xiàn)用戶的中心性，本文選擇入度數(shù)和K 核變化率表征用戶在社交網(wǎng)絡(luò)中的拓?fù)湮恢?。此外，由于在選擇意見(jiàn)領(lǐng)袖候選集時(shí)，可能會(huì)加入具有次大K 核值的用戶，候選集中用戶的K 核值并不完全相同。因此從K 核值、入度數(shù)、K 核變化率三個(gè)方面考慮用戶的位置相似性，構(gòu)建位置特征向量：

則用戶u和用戶v的位置相似性p_s(u，s)計(jì)算式為：

其中：fol(u)是用戶u的追隨者集合，也就是在社交網(wǎng)絡(luò)中關(guān)注用戶u的用戶集合；fu是用戶u的位置特征向量，fv是用戶v的位置特征向量。如圖1（c），用戶2 的位置特征向量為f2=(3，4，0.167)，其追隨者1的位置特征向量為f1=(4，1，0.056)，因此p_s(2，1)=0.55。

鄰居相似性 鄰居相似性用來(lái)評(píng)估兩個(gè)用戶的追隨者之間的相似性。假設(shè)v是u的追隨者，且v一定能接收到u的信息。在極端情況下，當(dāng)u和v的追隨者之間沒(méi)有相同用戶時(shí)，u的信息能夠通過(guò)v被網(wǎng)絡(luò)中的更多人接收；而當(dāng)v的追隨者都是u的追隨者時(shí)，u的信息無(wú)法通過(guò)v進(jìn)行傳播。因此鄰居相似性與用戶的信息擴(kuò)散能力呈反比，這里計(jì)算用戶u和用戶v的鄰居相似性為n_s(u，v)：

以圖1 為例，用戶2 有四位追隨者，用戶1 有一位追隨者，其中用戶4 是他們的共有追隨者，于是n_s(2，1)=0.25。

3.4 用戶全局影響力

在社交網(wǎng)絡(luò)中，用戶的影響力通過(guò)追隨者向外擴(kuò)散。用戶的追隨者越多，其在社交網(wǎng)絡(luò)中影響力的擴(kuò)散范圍越大，即重要度越大。但不同追隨者對(duì)用戶影響力的擴(kuò)散意愿并不相同，追隨者的擴(kuò)散意愿越大，用戶的影響擴(kuò)散范圍越大，可理解為用戶的全局影響力越大，影響力最大的用戶即為意見(jiàn)領(lǐng)袖。

本文使用用戶間的位置相似度評(píng)估不同追隨者對(duì)用戶影響力的擴(kuò)散意愿，提出用戶全局影響力的計(jì)算式如下：

當(dāng)用戶及其追隨者都是意見(jiàn)領(lǐng)袖候選者時(shí)，追隨者與用戶的位置越相似，則追隨者轉(zhuǎn)發(fā)用戶信息的可能性越大；當(dāng)用戶追隨者不是意見(jiàn)領(lǐng)袖候選者時(shí)，追隨者與用戶的位置相似度越小，追隨者轉(zhuǎn)發(fā)用戶信息的可能性越大。

此外，考慮到追隨者和用戶的鄰居相似性對(duì)用戶信息擴(kuò)散范圍的影響，修改用戶全局影響力的計(jì)算式為：

其中fol(u)是用戶的追隨者集合。根據(jù)上述方法，對(duì)于用戶2，在意見(jiàn)領(lǐng)袖候選集L中的追隨者有用戶1、3、4，不在L中的追隨者有用戶6，如圖1（c）所示，根據(jù)上述方法分別計(jì)算四位追隨者的位置相似性以及鄰居相似性，p_s(2，1)=0.55，n_s(2，1)=0.2，p_s(2，3)=0.7，n_s(2，3)=0.33，p_s(2，4)=0.67，n_s(2，4)=0，p_s(2，6)=0.42，n_s(2，6)=0，最終計(jì)算fol(u)=8.76。

算法1 基于K 核分解的意見(jiàn)領(lǐng)袖識(shí)別算法CandidateRank。

下面對(duì)CandidateRank 進(jìn)行時(shí)間復(fù)雜度分析。CandidateRank 首先通過(guò)K 核分解得到意見(jiàn)領(lǐng)袖候選集，所以在獲取所有節(jié)點(diǎn)K 核值時(shí)花費(fèi)O(m)，其中m是網(wǎng)絡(luò)中邊的數(shù)量。后面的Sumk是所有節(jié)點(diǎn)K 核值之和，因此花費(fèi)O(n)，n為節(jié)點(diǎn)個(gè)數(shù)。對(duì)于全局影響力的計(jì)算均在候選集中進(jìn)行，候選集節(jié)點(diǎn)個(gè)數(shù)為l，通常l 遠(yuǎn)小于n，k是節(jié)點(diǎn)的平均度數(shù)，在位置核鄰居相似性計(jì)算時(shí)時(shí)間復(fù)雜度為O(nk2)，因此CandidateRank 的時(shí)間復(fù)雜度為O(m+n+lk2)，在最壞情況下，l=n，此時(shí)時(shí)間復(fù)雜度為O(m+n(1+k2))。本文提出的算法時(shí)間復(fù)雜度高于MDD 和Cnc+算法，與ELKSS 算法復(fù)雜度相似，遠(yuǎn)小于θ 方法的O(n(n+m))，而且明顯低于相關(guān)工作中提到的其他幾種與K 核分解相關(guān)的方法，那些方法涉及一些中心性度量，因此時(shí)間復(fù)雜度都較高。因此，CandidateRank 在時(shí)間復(fù)雜度上有一定的優(yōu)勢(shì)。

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

本文實(shí)驗(yàn)在三個(gè)真實(shí)的數(shù)據(jù)集上進(jìn)行，三個(gè)數(shù)據(jù)集分別是：1）數(shù)據(jù)集1 選取來(lái)自微博的320 個(gè)用戶以及用戶間的互動(dòng)行為來(lái)構(gòu)建出網(wǎng)絡(luò)模型；2）數(shù)據(jù)集2 來(lái)自斯坦福公開(kāi)的社交網(wǎng)絡(luò)數(shù)據(jù)集，該數(shù)據(jù)集由來(lái)自Facebook 的“圈子”（或“好友列表”）組成。Facebook 數(shù)據(jù)是從使用這個(gè)Facebook 應(yīng)用程序的調(diào)查參與者那里收集的。3）數(shù)據(jù)集3 選自微博，該數(shù)據(jù)集收集2016-12-16—2017-12-16 期間，942 740 個(gè)用戶在微博平臺(tái)上的關(guān)注關(guān)系和用戶行為信息，這些用戶之間的關(guān)注關(guān)系多達(dá)1 048 575 條。為了便于計(jì)算，本文選取其中較為活躍（有轉(zhuǎn)發(fā)、發(fā)布、評(píng)論行為）的49 613 個(gè)用戶構(gòu)建社交網(wǎng)絡(luò)模型。統(tǒng)計(jì)描述如表1 所示，數(shù)據(jù)集1、3 來(lái)自微博，數(shù)據(jù)集2來(lái)自Facebook。

表1 實(shí)驗(yàn)用數(shù)據(jù)集Tab.1 Datasets for experiment

為了評(píng)估CandidateRank 算法的性能，本文將CandidateRank 算法的實(shí)驗(yàn)結(jié)果與其他意見(jiàn)領(lǐng)袖識(shí)別算法的實(shí)驗(yàn)結(jié)果進(jìn)行對(duì)比，其他算法包括DegreeRank 算法、PageRank 算法、ELKSS 算法。DegreeRank 算法是度中心性算法，以網(wǎng)絡(luò)中節(jié)點(diǎn)的度數(shù)來(lái)度量節(jié)點(diǎn)重要性。PageRank 算法根據(jù)網(wǎng)頁(yè)間的相互鏈接評(píng)估網(wǎng)頁(yè)重要度，常被用來(lái)計(jì)算用戶在網(wǎng)絡(luò)圖中的重要度。ELKSS 算法是Yang 等［17］基于K-Shell改進(jìn)的算法。使用兩個(gè)指標(biāo)來(lái)評(píng)估以上各算法的性能：基于獨(dú)立級(jí)聯(lián)模型（Independent Cascade Model，ICM）預(yù)測(cè)的用戶影響力和基于用戶中心性的用戶重要度。

4.1 基于獨(dú)立級(jí)聯(lián)模型預(yù)測(cè)的用戶影響力

本文在獨(dú)立級(jí)聯(lián)模型（ICM）下，使用Monte-Carlo 模擬評(píng)估各個(gè)算法所識(shí)別出的意見(jiàn)領(lǐng)袖在社交網(wǎng)絡(luò)信息傳播過(guò)程中能夠影響到的用戶數(shù)，表征用戶影響力。假設(shè)網(wǎng)絡(luò)中每個(gè)用戶的傳播概率相同，在給定傳播概率后，經(jīng)過(guò)實(shí)驗(yàn)發(fā)現(xiàn)Monte-Carlo 模擬次數(shù)達(dá)到10 000 次時(shí)，節(jié)點(diǎn)的影響范圍較為穩(wěn)定。同時(shí)，設(shè)置節(jié)點(diǎn)的傳播概率p=｛0.02，0.04，0.06，0.08｝，在不同傳播概率p下比較各算法所識(shí)別Top-N位意見(jiàn)領(lǐng)袖的用戶影響力。在本文設(shè)定N=15，即選擇每個(gè)方法所識(shí)別出的前15 個(gè)意見(jiàn)領(lǐng)袖進(jìn)行評(píng)估，其結(jié)果如圖3～6 所示，其中：橫軸代表各算法，縱軸表示用戶在給定p值下，各算法所識(shí)別的前15 位意見(jiàn)領(lǐng)袖能夠影響到的用戶數(shù)的統(tǒng)計(jì)情況。

圖3 p=0.02時(shí)在三個(gè)數(shù)據(jù)集上各算法的性能Fig.3 Performance of each algorithm on three datasets with p=0.02

圖4 p=0.04時(shí)在三個(gè)數(shù)據(jù)集上各算法的性能Fig.4 Performance of each algorithm on three datasets with p=0.04

圖5 p=0.06時(shí)在三個(gè)數(shù)據(jù)集上各算法的性能Fig.5 Performance of each algorithm on three datasets with p=0.06

圖6 p=0.08時(shí)在三個(gè)數(shù)據(jù)集上各算法的性能Fig.6 Performance of each algorithm on three datasets with p=0.08

本文利用箱線圖3～6，觀察不同算法的意見(jiàn)領(lǐng)袖，在三個(gè)數(shù)據(jù)集中不同傳播概率p下的用戶影響力分布范圍。由圖3～6 可知，節(jié)點(diǎn)的平均影響力取值差異顯著，且分布情況不同。

當(dāng)p=0.02 時(shí)，在數(shù)據(jù)集1 上，四種算法得到的前15 位意見(jiàn)領(lǐng)袖影響力值（IC）的中位數(shù)十分接近，而得到的影響力最值差距較大，其中PageRank 算法得到的最大影響力均高于其他三種算法，而ELKSS 得到的最大影響力最小。DegreeRank 算法發(fā)現(xiàn)的意見(jiàn)領(lǐng)袖中最小用戶影響力數(shù)值遠(yuǎn)遠(yuǎn)低于其他三種算法，CandidateRank 算法在該數(shù)據(jù)集上效果整體優(yōu)于ELKSS 算法和DegreeRank 算法。在數(shù)據(jù)集2 中，四種算法發(fā)現(xiàn)的意見(jiàn)領(lǐng)袖中所具有最大用戶影響力值均相同，而其他用戶影響力值分布差距較大，CandidateRank 算法發(fā)現(xiàn)的意見(jiàn)領(lǐng)袖影響力值中位數(shù)和最小影響力值遠(yuǎn)高于其他三種算法。而在數(shù)據(jù)集3 上四種算法表現(xiàn)較為相似。

當(dāng)p=0.04 時(shí)，由于p值的增大，在三個(gè)數(shù)據(jù)集上發(fā)現(xiàn)的意見(jiàn)領(lǐng)袖的影響力值均有增大。在數(shù)據(jù)集1 上，與p=0.02 不同，PageRank 算法發(fā)現(xiàn)的最大影響力值不是最高，而DegreeRank 算法發(fā)現(xiàn)的意見(jiàn)領(lǐng)袖的最大影響力值高于其他三種算法，但最小影響力值仍遠(yuǎn)低于其他算法，CandidateRank 的影響力值中位數(shù)與最小值也不低于其他三種算法，分布依然保持穩(wěn)定。在數(shù)據(jù)集2 上，與p=0.02 相似，四種算法發(fā)現(xiàn)的意見(jiàn)領(lǐng)袖中所具有最大用戶影響力值均相同，但DegreeRank 算法選出的最大影響力值低于其他三種算法較多，而CandidateRank 算法無(wú)論是最大值、中位數(shù)及最小值均高于其他算法，性能較佳。

當(dāng)p=0.06 時(shí)，在數(shù)據(jù)集1 上四種算法選出的影響力值分布與p=0.02 時(shí)相似；而在數(shù)據(jù)集2 上，與p=0.04 較為不同的是，CandidateRank 算法發(fā)現(xiàn)的影響力值中位數(shù)不再明顯高于其他方法，而是與PageRank 算法相近，但也優(yōu)于其他兩種算法。

當(dāng)p=0.08 時(shí)，在數(shù)據(jù)集1 上，四種算法發(fā)現(xiàn)的意見(jiàn)領(lǐng)袖的影響力值中位數(shù)仍然保持相近，而CandidateRank 算法發(fā)現(xiàn)的最大影響力值高于其他算法，最小值也高于DegreeRank。在數(shù)據(jù)集2 中，本文提出的算法CandidateRank發(fā)現(xiàn)的影響力值中位數(shù)最高值比p=0.06 時(shí)均有所下降，但最小值依然遠(yuǎn)遠(yuǎn)高于其他算法。在數(shù)據(jù)集3 上CandidateRank 算法發(fā)現(xiàn)的影響力值中位數(shù)低于PageRank 算法較多，但最小值依然較高。

從圖3～6 可以看出，本文提出的CandidateRank 算法在數(shù)據(jù)集1 上表現(xiàn)比較穩(wěn)定，而且總體性能僅次于PageRank，隨著p值的增加，CandidateRank 表現(xiàn)越來(lái)越好。而在數(shù)據(jù)集3上本文提出的算法在最高值、中位數(shù)、以及最小值方面都有很好的表現(xiàn)，尤其是在p=0.04 時(shí)CandidateRank 算法的性能最佳。對(duì)于數(shù)據(jù)集3，可以看到除了影響力前三的意見(jiàn)領(lǐng)袖，其他影響力值都很低，說(shuō)明該數(shù)據(jù)集的意見(jiàn)領(lǐng)袖比較集中突出，在這樣的特殊數(shù)據(jù)集上本文提出的算法依然能選出影響力值最大的意見(jiàn)領(lǐng)袖。

為了對(duì)比四種算法識(shí)別出的意見(jiàn)領(lǐng)袖在基于獨(dú)立級(jí)聯(lián)模型預(yù)測(cè)的用戶影響力與其排名的關(guān)系，本文選擇了一組數(shù)據(jù)進(jìn)行對(duì)比，表2 為p=0.02 時(shí)在Facebook 數(shù)據(jù)集上前15 個(gè)節(jié)點(diǎn)的影響力值。由表2 可以發(fā)現(xiàn)，四種算法均識(shí)別出影響力值最大的為第一意見(jiàn)領(lǐng)袖，但PageRank、DegreeRank、ELKSS 算法識(shí)別出的其他意見(jiàn)領(lǐng)袖排名與其影響力值大小并不相符，本文提出的CandidateRank 算法識(shí)別出的意見(jiàn)領(lǐng)袖影響力值隨著排名的下降而下降，從這個(gè)角度看本文提出的CandidateRank 算法性能更優(yōu)。綜上所述，在基于獨(dú)立級(jí)聯(lián)模型預(yù)測(cè)的用戶影響力上，本文提出的CandidateRank 算法在不同的數(shù)據(jù)集上均能表現(xiàn)出優(yōu)勢(shì)，總體性能較好。

表2 p=0.02時(shí)在Facebook數(shù)據(jù)集上Top-15節(jié)點(diǎn)的影響力值Tab.2 Influence values of Top-15 nodes on Facebook dataset with p=0.02

4.2 基于用戶中心性的用戶重要度

在復(fù)雜網(wǎng)絡(luò)的研究中，接近中心性、中介中心性、特征向量中心性等中心性指標(biāo)能有效識(shí)別網(wǎng)絡(luò)中的高影響力節(jié)點(diǎn)。因此使用包括上述3 個(gè)中心性在內(nèi)的4 個(gè)中心性指標(biāo)來(lái)評(píng)估各個(gè)算法所識(shí)別的意見(jiàn)領(lǐng)袖的重要度，4 個(gè)中心性指標(biāo)在2.3 節(jié)中有詳細(xì)介紹。在評(píng)估用戶重要度時(shí)，4 個(gè)中心性指標(biāo)都是中心性越大，用戶重要度越大。本文選擇在數(shù)據(jù)集1上對(duì)CandidateRank、PageRank、DegreeRank 和ELKSS 4 個(gè)算法所識(shí)別的前15 位意見(jiàn)領(lǐng)袖進(jìn)行用戶中心性計(jì)算，結(jié)果如圖7 所示，4 個(gè)子圖的橫軸是4 種算法選出的Top-15 意見(jiàn)領(lǐng)袖排名，縱軸分別為4 個(gè)中心性值。

圖7 四種算法的中心性指標(biāo)值Fig.7 Centrality index values of four algorithms

從圖7 的接近中心性中可以看出，隨著排名數(shù)的增大，CandidateRank 算法的意見(jiàn)領(lǐng)袖在接近中心性上整體呈現(xiàn)下降趨勢(shì)，符合排名數(shù)越靠后、重要度越小現(xiàn)象。而DegreeRank 算法所識(shí)別的前15 位意見(jiàn)領(lǐng)袖接近中心性的變化波動(dòng)特別大，說(shuō)明其性能不穩(wěn)定。同時(shí)，CandidateRank 算法所識(shí)別的Top-1 意見(jiàn)領(lǐng)袖具有最大的接近中心性，因此說(shuō)明CandidateRank 算法能夠有效識(shí)別社交網(wǎng)絡(luò)中的重要用戶。

在中介中心性中，CandidateRank 算法和PageRank 算法的中心性變化趨勢(shì)十分相似，且中心性隨著排名下降的趨勢(shì)比較明顯，表明CandidateRank 和Page 算法在識(shí)別具有高中介中心性用戶時(shí)性能較優(yōu)。

在特征向量中心性和Katz 中心性中，4 種算法所識(shí)別的意見(jiàn)領(lǐng)袖的兩種中心性均相似，隨著排名數(shù)的增大，兩種中心性波動(dòng)頻繁，PageRank、DegreeRank 2 種算法沒(méi)有明顯的隨著排名而下降的趨勢(shì)，而CandidateRank 和ELKSS 算法的中心性變化相對(duì)比較明顯。對(duì)比CandidateRank 算法在特征向量中心性和Katz 中心性上的不同表現(xiàn)，可以發(fā)現(xiàn)CandidateRank 算法對(duì)意見(jiàn)領(lǐng)袖候選集中用戶的排序更接近Katz 中心性對(duì)用戶的排序。這是因?yàn)樵谟?jì)算用戶的Katz 中心性時(shí)，與用戶直接連接和間接連接的鄰居被分配不同的權(quán)重，在CandidateRank 算法中，根據(jù)用戶追隨者身份的不同（是否屬于意見(jiàn)領(lǐng)袖候選集），對(duì)追隨者分配不同的權(quán)重。相較于特征向量中心性，CandidateRank 算法在Katz 中心性指標(biāo)上表現(xiàn)更優(yōu)，表明CandidateRank 算法在計(jì)算不同鄰居對(duì)用戶貢獻(xiàn)的影響力時(shí)具有較高的準(zhǔn)確性。從圖7 中還可以看到，在用戶中心性指標(biāo)上，CandidateRank 算法的性能優(yōu)于PageRank 算法和DegreeRank 算法，和ELKSS 算法的性能較為接近；但是在基于獨(dú)立級(jí)聯(lián)模型預(yù)測(cè)的用戶影響力上，CandidateRank 算法在整體上優(yōu)于ELKSS 算法。因此認(rèn)為CandidateRank 算法在識(shí)別社交網(wǎng)絡(luò)中的意見(jiàn)領(lǐng)袖時(shí)是可行的，且有效的。

4.3 相關(guān)性

4.1、4.2 節(jié)的實(shí)驗(yàn)反映了4 種算法識(shí)別出的最重要的意見(jiàn)領(lǐng)袖前15 位的實(shí)際影響力和中心性的情況，但是沒(méi)有反映出這些節(jié)點(diǎn)的排序和該網(wǎng)絡(luò)中真實(shí)傳播能力較強(qiáng)的前15位排序的相關(guān)性，并且所對(duì)比的4 種算法中只有ELKSS 是與K 核相關(guān)的方法，因此本節(jié)僅針對(duì)與K 核相關(guān)的方法引入肯德?tīng)栂嚓P(guān)性系數(shù)來(lái)評(píng)估算法效果，真實(shí)節(jié)點(diǎn)影響力還是IC模型的仿真結(jié)果。4 種算法分別是相關(guān)工作中提到的混合度分解法（MDD）、擴(kuò)展近鄰核，以及之前的對(duì)比方法ELKSS。表3 中列出了包括CandidateRank 方法在內(nèi)的4 種意見(jiàn)領(lǐng)袖識(shí)別算法前15 位與這些節(jié)點(diǎn)真實(shí)傳播影響力的排序之間的相關(guān)性，可以看出在2 個(gè)數(shù)據(jù)集上CandidateRank 算法的相關(guān)性都優(yōu)于其他3 種算法，只有在Facebook 數(shù)據(jù)集上略低于MDD 方法，總體來(lái)看結(jié)果較優(yōu)。

表3 四種算法計(jì)算出的意見(jiàn)領(lǐng)袖排序與真實(shí)節(jié)點(diǎn)影響力排序的相關(guān)性Tab.3 Correlation between ranking of opinion leaders calculated by four algorithms and ranking of influence of real nodes

5 結(jié)語(yǔ)

本文提出了一種社交網(wǎng)絡(luò)中基于K 核分解的意見(jiàn)領(lǐng)袖識(shí)別算法CandidateRank。由于在社交網(wǎng)絡(luò)中并非所有用戶都有相同的機(jī)會(huì)成為意見(jiàn)領(lǐng)袖，所以通過(guò)K 核分解，選擇社交網(wǎng)絡(luò)中具有最大K 核數(shù)的用戶加入到意見(jiàn)領(lǐng)袖候選集中；再根據(jù)用戶的平均K 核變化率、位置相似性和鄰居相似性等指標(biāo)來(lái)確定用戶追隨者對(duì)用戶影響力的貢獻(xiàn)程度，并計(jì)算用戶的全局影響力，識(shí)別意見(jiàn)領(lǐng)袖。在意見(jiàn)領(lǐng)袖候選集中確定意見(jiàn)領(lǐng)袖，一方面可以極大減少需要評(píng)估重要度的節(jié)點(diǎn)總數(shù)，另一方面可以增強(qiáng)意見(jiàn)領(lǐng)袖識(shí)別算法的適用性。在真實(shí)社交網(wǎng)絡(luò)數(shù)據(jù)中的實(shí)驗(yàn)結(jié)果表明，本文提出算法是可行的，且有效的。后續(xù)研究將圍繞如何使用圖神經(jīng)網(wǎng)絡(luò)改進(jìn)本文的算法使其在較大的網(wǎng)絡(luò)中性能更優(yōu)繼續(xù)進(jìn)行。