社交網絡中基于K核分解的意見領袖識別算法

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

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

0 引言

社交網絡中意見領袖可以在信息傳播過程產生巨大的作用，其發表的言論、持有的態度等一系列行為和后續影響力可以通過用戶之間的鏈接關系產生逐層裂變式擴散［1］。這種擴散效果促使意見領袖對于預測信息傳播狀態、監督和引導輿論，以及影響網絡信息擴散趨勢有著極其關鍵的作用［2-4］。因此，如何發現并識別社交網絡中的意見領袖群體是當前社交網絡研究的熱點問題。

目前，對于意見領袖識別算法的研究主要分為三個方面：一是基于對網絡拓撲的分析來檢測意見領袖，使用網絡拓撲分析社交網絡圖模型的相關特性，例如，在意見領袖挖掘中，度中心性、中介性中心性、接近中心性和K 核等都是非常有效并且常用的方法［5-7］。二是基于社交網絡中用戶的歷史行為數據挖掘意見領袖。朋友的數量、發布信息的總數、轉發或評論信息的總數，以及信息所表達的情感都可以用來識別意見領袖［8-9］。三是綜合考慮社交網絡的網絡拓撲和用戶的歷史行為數據來挖掘意見領袖。然而，這三種方法都存在以下問題：在大型社交網絡中識別意見領袖時通常需要很大的計算量。盡管在社交網絡中并不是每一個用戶都有足夠的條件成為意見領袖，但當前的意見領袖識別算法大多以相同的方式來評估每個用戶的重要性。

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

對于大規模網絡，特別是用戶關系比較集中的一些網絡，其中大部分用戶都屬于“邊緣用戶”，他們幾乎沒有成為意見領袖的潛質，但是根據一些意見領袖識別算法依然要對他們進行計算，極大延長了整體的計算時間，而本文提出的CandidateRank 算法通過建立意見領袖候選集解決了這個問題；另外本文提出的用戶相似度的計算通過拓撲結構建立用戶位置向量也是比較輕量級的計算。

本文的主要工作有：

1）基于K 核分解區分社交網絡中的潛在意見領袖與普通用戶。在潛在意見領袖（意見領袖候選集）中識別意見領袖，能夠避免重復計算“邊緣用戶”的重要度，從而降低計算的復雜度。

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

3）對社交網絡圖模型進行K 核分解后，具有較大K 核值的用戶有較大的可能性是意見領袖，因此可以將具有最大K核值的用戶加入到意見領袖候選集中。

1 相關工作

研究表明，K 核分解可以識別社交網絡中最具影響力的節點［10］。根據用戶的K 核值，可以粗粒度地區分社交網絡中的潛在意見領袖與普通用戶。CandidateRank 算法的主要工作是基于K 核分解獲得潛在的意見領袖加入到意見領袖候選集中，然后依據平均K 核變化率、用戶相似性等指標對候選集中的用戶進行全局影響力計算，以獲得所需的意見領袖。

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

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

2 算法和相關定義

2.1 算法結構

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

圖1 CandidateRank算法結構Fig.1 CandidateRank algorithm structure

2.2 算法步驟

用于檢測意見領袖的CandidateRank 算法步驟主要分為三個：

步驟1 用K 核分解獲取社交網絡中每個用戶的K 核值，并選擇K 核值最大的用戶加入到意見領袖候集中。

步驟2 通過多次使用K 核分解，分別計算刪除意見領袖候選集中的用戶后所造成的平均K 核變化率，用于步驟3中評估位置相似性。對于意見領袖候選集中的每個用戶，找到該用戶的追隨者集合，以及追隨者的追隨者集合，用于步驟3 計算意見候選集中的用戶和其追隨者的鄰居相似性。

步驟3 評估意見領袖候選集中每個用戶和其追隨者的位置相似性和鄰居相似性，計算用戶全局影響力以識別意見領袖。

2.3 相關指標

接近中心性（Closeness Centrality）［23］：是節點到網絡中所有其他節點最短路徑之和的倒數，表示節點在網絡中與其他節點的距離，接近中心性越大，則用戶與其他用戶的距離越近。

中介中心性（Betweenness Centrality）［24］：是穿過節點的最短路徑占網絡中最短路徑的比例。

特征向量中心性（Eigenvector Centrality）［25］：基于鄰居節點的重要度評估節點重要性。

Katz 中心性（Katz Centrality）［25］：在特征向量中心性的基礎上，給和節點直接連接的鄰居以及間接連接的鄰居分配不同的影響力權值。

肯德爾相關性系數（Kendall’tau）：是一種秩相關系數，計算式如下：

其中：nc與nd分別代表兩個列表中的相容元素對與不相容元素對的數量。n是列表長度即列表中元素數，兩個列表的長度相同。

2.4 算法相關定義

一些社交平臺中用戶與用戶之間會通過一些方式產生公開交互，如微博、Facebook、豆瓣等，用戶與用戶之間的行為可以構成社交網絡，本文將這樣由用戶和用戶間交互關系構成的社交網絡轉化為一個有向圖G=(V，M)，其中V={u1，u2，…，uN}是社交網絡中的節點（用戶）集合，N是節點（用戶）總數，E={e1，e2，…，eM}是邊的集合，邊表示用戶之間的互動關系，如評論、點贊、轉發等行為在用戶間建立起有向關系（即有向邊），M是社交網絡中邊的總數。

定義 1K核值。在圖G中，若存在子圖Gk={(Vk，Ek)，Vk?V，Ek?E}，對每個節點v∈Vk，v的度（出度及入度）大于或等于k，則圖的子圖Gk是圖的K 核。K 核值是經過K 核分解分配給圖中每個節點的重要度分值，并且當v∈V，v?Vk時，v的K 核值等于k。

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

定義3追隨者。在社交網絡圖中，若存在u，v∈V，ek∈E同時ek={u，v}，則用戶u是用戶v的追隨者。

定義4意見領袖。在社交網絡中，用戶的影響擴散范圍越大，可理解為用戶的全局影響力越大，影響力最大的用戶即為意見領袖，意見領袖在大眾傳播過程中起到引領作用。

定義5意見領袖候選集（潛在意見領袖）。在計算用戶重要度之前，選擇最有可能成為意見領袖的用戶加入到意見領袖候選集L中，V、O、L之間的關系為O?L?V。

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

本文中有4 種用戶角色：追隨者、普通用戶、意見領袖候選者和意見領袖，它們的關系可以用圖2 表示。

圖2 用戶角色關系Fig.2 User role relationship

3 基于K核分解的CandidateRank算法

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

通過K 核分解得到的最具影響力的節點是一個集合，集合中節點的具體重要度并不明確。通過K 核分解，選擇K 核值最大的用戶加入意見領袖候選集，一方面避免了無法選擇區分普通用戶和潛在意見領袖的標準的問題，另一方面當具有最大K 核值的用戶總數不足時，可以選擇具有次大K 核值（即排名第二大的K 核值）的用戶補充到意見領袖候選集中。

3.1 K核分解

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

選擇具有最大K 核值的用戶作為意見領袖候選集L。當具有最大K 核值的用戶總數少于所需意見領袖總數時，將具有次大K 核值的用戶加入到意見領袖候選集L中。K 核分解得到的用戶是在圖中受到最多用戶關注或者和最多用戶有聯系的，因為他們成為意見領袖的概率非常大。

3.2 平均K核變化率

在意見領袖候選集中，具有相同K 核值的用戶，其用戶重要度也不盡相同。在復雜網絡的節點重要度研究中，刪除法通過對比刪除節點前和刪除節點后網絡的連通性變化情況對節點重要度進行排序。在本文中，意見領袖候選集中的用戶本身具有最大的K 核值，是社交網絡中較重要的用戶。因此，考慮通過對比刪除某個用戶前后其他用戶K 核值的變化情況，計算出平均K 核變化率，來說明該用戶對網絡中其他用戶的平均影響力。平均K 核變化率的計算式如下：

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

3.3 用戶相似性

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

位置相似性 位置相似性評估用戶在社交網絡拓撲位置上的相似性，通常情況下，常用度中心性、中介中心性、緊密中心性、特征向量中心性等中心性指標來說明用戶在社交網絡拓撲上的位置，但中介中心性、緊密中心性和特征向量中心性的計算均涉及全網用戶，計算復雜度較高。同時，在有向圖中，入度數比出度數更能體現用戶的中心性，本文選擇入度數和K 核變化率表征用戶在社交網絡中的拓撲位置。此外，由于在選擇意見領袖候選集時，可能會加入具有次大K 核值的用戶，候選集中用戶的K 核值并不完全相同。因此從K 核值、入度數、K 核變化率三個方面考慮用戶的位置相似性，構建位置特征向量：

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

其中：fol(u)是用戶u的追隨者集合，也就是在社交網絡中關注用戶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。

鄰居相似性 鄰居相似性用來評估兩個用戶的追隨者之間的相似性。假設v是u的追隨者，且v一定能接收到u的信息。在極端情況下，當u和v的追隨者之間沒有相同用戶時，u的信息能夠通過v被網絡中的更多人接收；而當v的追隨者都是u的追隨者時，u的信息無法通過v進行傳播。因此鄰居相似性與用戶的信息擴散能力呈反比，這里計算用戶u和用戶v的鄰居相似性為n_s(u，v)：

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

3.4 用戶全局影響力

在社交網絡中，用戶的影響力通過追隨者向外擴散。用戶的追隨者越多，其在社交網絡中影響力的擴散范圍越大，即重要度越大。但不同追隨者對用戶影響力的擴散意愿并不相同，追隨者的擴散意愿越大，用戶的影響擴散范圍越大，可理解為用戶的全局影響力越大，影響力最大的用戶即為意見領袖。

本文使用用戶間的位置相似度評估不同追隨者對用戶影響力的擴散意愿，提出用戶全局影響力的計算式如下：

當用戶及其追隨者都是意見領袖候選者時，追隨者與用戶的位置越相似，則追隨者轉發用戶信息的可能性越大；當用戶追隨者不是意見領袖候選者時，追隨者與用戶的位置相似度越小，追隨者轉發用戶信息的可能性越大。

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

其中fol(u)是用戶的追隨者集合。根據上述方法，對于用戶2，在意見領袖候選集L中的追隨者有用戶1、3、4，不在L中的追隨者有用戶6，如圖1（c）所示，根據上述方法分別計算四位追隨者的位置相似性以及鄰居相似性，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，最終計算fol(u)=8.76。

算法1 基于K 核分解的意見領袖識別算法CandidateRank。

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

4 實驗與結果分析

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

表1 實驗用數據集Tab.1 Datasets for experiment

為了評估CandidateRank 算法的性能，本文將CandidateRank 算法的實驗結果與其他意見領袖識別算法的實驗結果進行對比，其他算法包括DegreeRank 算法、PageRank 算法、ELKSS 算法。DegreeRank 算法是度中心性算法，以網絡中節點的度數來度量節點重要性。PageRank 算法根據網頁間的相互鏈接評估網頁重要度，常被用來計算用戶在網絡圖中的重要度。ELKSS 算法是Yang 等［17］基于K-Shell改進的算法。使用兩個指標來評估以上各算法的性能：基于獨立級聯模型（Independent Cascade Model，ICM）預測的用戶影響力和基于用戶中心性的用戶重要度。

4.1 基于獨立級聯模型預測的用戶影響力

本文在獨立級聯模型（ICM）下，使用Monte-Carlo 模擬評估各個算法所識別出的意見領袖在社交網絡信息傳播過程中能夠影響到的用戶數，表征用戶影響力。假設網絡中每個用戶的傳播概率相同，在給定傳播概率后，經過實驗發現Monte-Carlo 模擬次數達到10 000 次時，節點的影響范圍較為穩定。同時，設置節點的傳播概率p=｛0.02，0.04，0.06，0.08｝，在不同傳播概率p下比較各算法所識別Top-N位意見領袖的用戶影響力。在本文設定N=15，即選擇每個方法所識別出的前15 個意見領袖進行評估，其結果如圖3～6 所示，其中：橫軸代表各算法，縱軸表示用戶在給定p值下，各算法所識別的前15 位意見領袖能夠影響到的用戶數的統計情況。

圖3 p=0.02時在三個數據集上各算法的性能Fig.3 Performance of each algorithm on three datasets with p=0.02

圖4 p=0.04時在三個數據集上各算法的性能Fig.4 Performance of each algorithm on three datasets with p=0.04

圖5 p=0.06時在三個數據集上各算法的性能Fig.5 Performance of each algorithm on three datasets with p=0.06

圖6 p=0.08時在三個數據集上各算法的性能Fig.6 Performance of each algorithm on three datasets with p=0.08

本文利用箱線圖3～6，觀察不同算法的意見領袖，在三個數據集中不同傳播概率p下的用戶影響力分布范圍。由圖3～6 可知，節點的平均影響力取值差異顯著，且分布情況不同。

當p=0.02 時，在數據集1 上，四種算法得到的前15 位意見領袖影響力值（IC）的中位數十分接近，而得到的影響力最值差距較大，其中PageRank 算法得到的最大影響力均高于其他三種算法，而ELKSS 得到的最大影響力最小。DegreeRank 算法發現的意見領袖中最小用戶影響力數值遠遠低于其他三種算法，CandidateRank 算法在該數據集上效果整體優于ELKSS 算法和DegreeRank 算法。在數據集2 中，四種算法發現的意見領袖中所具有最大用戶影響力值均相同，而其他用戶影響力值分布差距較大，CandidateRank 算法發現的意見領袖影響力值中位數和最小影響力值遠高于其他三種算法。而在數據集3 上四種算法表現較為相似。

當p=0.04 時，由于p值的增大，在三個數據集上發現的意見領袖的影響力值均有增大。在數據集1 上，與p=0.02 不同，PageRank 算法發現的最大影響力值不是最高，而DegreeRank 算法發現的意見領袖的最大影響力值高于其他三種算法，但最小影響力值仍遠低于其他算法，CandidateRank 的影響力值中位數與最小值也不低于其他三種算法，分布依然保持穩定。在數據集2 上，與p=0.02 相似，四種算法發現的意見領袖中所具有最大用戶影響力值均相同，但DegreeRank 算法選出的最大影響力值低于其他三種算法較多，而CandidateRank 算法無論是最大值、中位數及最小值均高于其他算法，性能較佳。

當p=0.06 時，在數據集1 上四種算法選出的影響力值分布與p=0.02 時相似；而在數據集2 上，與p=0.04 較為不同的是，CandidateRank 算法發現的影響力值中位數不再明顯高于其他方法，而是與PageRank 算法相近，但也優于其他兩種算法。

當p=0.08 時，在數據集1 上，四種算法發現的意見領袖的影響力值中位數仍然保持相近，而CandidateRank 算法發現的最大影響力值高于其他算法，最小值也高于DegreeRank。在數據集2 中，本文提出的算法CandidateRank發現的影響力值中位數最高值比p=0.06 時均有所下降，但最小值依然遠遠高于其他算法。在數據集3 上CandidateRank 算法發現的影響力值中位數低于PageRank 算法較多，但最小值依然較高。

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

為了對比四種算法識別出的意見領袖在基于獨立級聯模型預測的用戶影響力與其排名的關系，本文選擇了一組數據進行對比，表2 為p=0.02 時在Facebook 數據集上前15 個節點的影響力值。由表2 可以發現，四種算法均識別出影響力值最大的為第一意見領袖，但PageRank、DegreeRank、ELKSS 算法識別出的其他意見領袖排名與其影響力值大小并不相符，本文提出的CandidateRank 算法識別出的意見領袖影響力值隨著排名的下降而下降，從這個角度看本文提出的CandidateRank 算法性能更優。綜上所述，在基于獨立級聯模型預測的用戶影響力上，本文提出的CandidateRank 算法在不同的數據集上均能表現出優勢，總體性能較好。

表2 p=0.02時在Facebook數據集上Top-15節點的影響力值Tab.2 Influence values of Top-15 nodes on Facebook dataset with p=0.02

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

在復雜網絡的研究中，接近中心性、中介中心性、特征向量中心性等中心性指標能有效識別網絡中的高影響力節點。因此使用包括上述3 個中心性在內的4 個中心性指標來評估各個算法所識別的意見領袖的重要度，4 個中心性指標在2.3 節中有詳細介紹。在評估用戶重要度時，4 個中心性指標都是中心性越大，用戶重要度越大。本文選擇在數據集1上對CandidateRank、PageRank、DegreeRank 和ELKSS 4 個算法所識別的前15 位意見領袖進行用戶中心性計算，結果如圖7 所示，4 個子圖的橫軸是4 種算法選出的Top-15 意見領袖排名，縱軸分別為4 個中心性值。

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

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

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

在特征向量中心性和Katz 中心性中，4 種算法所識別的意見領袖的兩種中心性均相似，隨著排名數的增大，兩種中心性波動頻繁，PageRank、DegreeRank 2 種算法沒有明顯的隨著排名而下降的趨勢，而CandidateRank 和ELKSS 算法的中心性變化相對比較明顯。對比CandidateRank 算法在特征向量中心性和Katz 中心性上的不同表現，可以發現CandidateRank 算法對意見領袖候選集中用戶的排序更接近Katz 中心性對用戶的排序。這是因為在計算用戶的Katz 中心性時，與用戶直接連接和間接連接的鄰居被分配不同的權重，在CandidateRank 算法中，根據用戶追隨者身份的不同（是否屬于意見領袖候選集），對追隨者分配不同的權重。相較于特征向量中心性，CandidateRank 算法在Katz 中心性指標上表現更優，表明CandidateRank 算法在計算不同鄰居對用戶貢獻的影響力時具有較高的準確性。從圖7 中還可以看到，在用戶中心性指標上，CandidateRank 算法的性能優于PageRank 算法和DegreeRank 算法，和ELKSS 算法的性能較為接近；但是在基于獨立級聯模型預測的用戶影響力上，CandidateRank 算法在整體上優于ELKSS 算法。因此認為CandidateRank 算法在識別社交網絡中的意見領袖時是可行的，且有效的。

4.3 相關性

4.1、4.2 節的實驗反映了4 種算法識別出的最重要的意見領袖前15 位的實際影響力和中心性的情況，但是沒有反映出這些節點的排序和該網絡中真實傳播能力較強的前15位排序的相關性，并且所對比的4 種算法中只有ELKSS 是與K 核相關的方法，因此本節僅針對與K 核相關的方法引入肯德爾相關性系數來評估算法效果，真實節點影響力還是IC模型的仿真結果。4 種算法分別是相關工作中提到的混合度分解法（MDD）、擴展近鄰核，以及之前的對比方法ELKSS。表3 中列出了包括CandidateRank 方法在內的4 種意見領袖識別算法前15 位與這些節點真實傳播影響力的排序之間的相關性，可以看出在2 個數據集上CandidateRank 算法的相關性都優于其他3 種算法，只有在Facebook 數據集上略低于MDD 方法，總體來看結果較優。

表3 四種算法計算出的意見領袖排序與真實節點影響力排序的相關性Tab.3 Correlation between ranking of opinion leaders calculated by four algorithms and ranking of influence of real nodes

5 結語

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