基于權鄰域的代表性用戶抽樣算法

何水苗，班志杰

內蒙古大學 計算機學院 內蒙古自治區社會計算與數據處理重點實驗室，呼和浩特 010020

社交網絡是指用戶以及用戶之間交互所組成的一個復雜網絡。它在信息傳播、想法分享和相互影響方面發揮著至關重要的作用。其中的一部分用戶在社會網絡影響中扮演著重要的角色[1-4]。例如產品推薦，一些用戶的關注點可以反映出整體用戶的興趣愛好，這對于市場營銷[5]是有幫助的。那么代表性用戶抽樣問題就是在大規模社交網絡中抽取一個用戶子集，使其可以統計代表整個網絡中所有用戶的特點。

目前，一些學者對于用戶抽樣問題進行相關研究，但不同任務下的用戶抽樣有著不同的定義。影響力最大化[6]是指利用一部分用戶子集來擴大影響力的傳播范圍。尋找意見領袖[7]是指社交網絡中一部分用戶發表的觀點能夠影響其他人做決定。代表性用戶抽樣[8]是指要尋找一些用戶，他們可以統計代表網絡中所有用戶的特點。當前對于代表性用戶抽樣問題的研究工作比較少。文獻[9]首次提出抽取代表性子集的問題，探究如何在一個復雜網絡中抽取代表性樣本。文獻[10]提出了一種基于擴展圖的網絡社區抽樣方法，該方法通過定義目標函數來表征代表性子集在拓撲結構的覆蓋范圍。文獻[11]又進一步提出在網絡中抽取一些帶有偏見節點的必要性。文獻[12]提出了一個通用框架來抽取代表性子圖，并使用隨機游走算法進行代表性子圖抽樣。文獻[13]提出一種基于K-NN圖的代表性子集抽取方法。但這些研究都是基于靜態網路的，文獻[14]重點研究了在動態社交網絡中抽取代表性子集問題，利用用戶鄰域收集的信息來探索社交網絡的結構。然而這些抽樣方法在抽取代表性子集時都只考慮了網絡的拓撲結構[15]，忽視了用戶屬性所包含的信息。文獻[16]提出的骨架學習方法是從信息傳播的角度進行代表性用戶抽取，它主要是通過貝葉斯推斷將每個節點連接到一個代表性節點。文獻[17]正式定義了代表性用戶抽樣問題，并且證明了該問題屬于NP-hard問題。他們提出的統計分層抽樣模型，雖然考慮了用戶之間的關系，但沒有充分研究的網絡拓撲結構。

由于在網絡的拓撲結構中也蘊含著用戶大量有價值的信息，所以為了從拓撲結構中獲取用戶包含的豐富內容，采用權鄰域對網絡的拓撲結構進行描述，并利用拓撲結構和用戶屬性進行代表性用戶的抽取，最后通過實驗進一步檢驗了所提出算法的有效性。

1 基于權鄰域的代表用戶抽樣算法

1.1 問題描述

G(V,E)表示社交網絡，其中V表示用戶集合，E表示用戶之間邊的集合， ||V=N表示圖上共有N個用戶，T?V表示抽取的代表性用戶集合， ||T=K表示抽取的代表性用戶個數。本文的工作就是對于給定的社會網絡G(V,E)，抽取一個用戶子集T(T?V, ||T=K)，使得提取的用戶子集盡可能地統計代表整個網絡中所有用戶。他們并不僅僅限制于具有較強影響力的個體或者是對于觀點傳播具有很強領導力的用戶。這里所說的代表性用戶，從屬性特征角度而言，他們能夠很好地代表原數據集用戶的屬性特征。從分布特征角度而言，代表性子集應盡可能擬合原數據集的樣本分布，即與原數據集具有較少的分布損耗，代表性子集能夠擬合原數據集每個領域的人物分布。

為了更好地闡述代表性用戶抽樣這個問題，通過一個例子來說明。如圖1，這是一個基于人工智能和云計算的合著網絡。從圖中可以看到每個學者對于不同研究領域的感興趣程度，其中左邊表示研究者對人工智能研究領域的感興趣程度，右邊表示研究者對云計算研究領域的感興趣程度，二者之和為1，學者之間的邊權重表示學者之間合著的論文數目。例如，從圖中可以看出學者B相比于對人工智能研究領域的感興趣程度（0.1），他在云計算研究領域的興趣程度比較高（0.9），由此看出他在人工智能研究領域具有更高的代表性；而學者H相比于云計算研究領域的感興趣程度（0.1），他在人工智能研究領域更感興趣（0.9），說明學者H在人工智能研究領域更具有代表性。由此可見，在不同的研究領域中，抽取的代表性用戶是不同的，所以研究的目標是抽取一個代表性用戶子集，使得它能夠統計代表整個網絡中所有用戶的屬性特征。

圖1 多屬性合著網絡Fig.1 Multi-attribute coauthor network

文獻[17]提出的統計分層抽樣模型，首先將所有用戶根據屬性值分成不同的屬性組；接著在每一個屬性組中，通過計算用戶的代表度之和得到屬性組代表度；最后將用戶的所有屬性組代表度累加起來，利用質量函數進行數值化評估，每次選取增量值最大的用戶作為代表性用戶。由于該模型在計算用戶代表度的過程中，對網絡的拓撲結構沒有進行更深入的研究，從而忽略了在拓撲結構中蘊含的用戶有用信息，所以本文對統計分層抽樣模型進行改進。通過利用權鄰域對圖的拓撲結構進行充分描述，從而獲得用戶包含的更多有價值信息，將權鄰域和用戶屬性結合起來抽取代表性用戶。

1.2 權鄰域

在衡量一個節點重要性時，不僅考慮節點本身的度，而且聯合它與鄰居的權重以及鄰居節點的度。假設兩個節點具有相同的度，若其中一個節點的鄰居節點影響力比較大，那么該節點也將具有更高的影響力。另外，在大多數的加權網絡中，每條邊在網絡結構和功能中具有不同的意義。例如，在合著網絡中，一個作者權鄰域值越大，表明該作者和鄰居合著的論文比較多，那么成為代表性用戶的可能性越大，權鄰域的計算公式如下：

其中，di表示節點i的度，wij表示節點i和節點j之間的權，dj表示節點j的度，Γ(i)表示節點i的所有鄰居。

為了選取不同規模社交網絡中的代表用戶，需要進行歸一化處理。通過將所有邊兩端節點度的乘積相加之和與所有邊所占的比重進行歸一化，用φi＇表示，如下式所示：

其中，di和dj表示節點i和節點j的度，w表示節點之間構成的邊。由于數據集的大小以及數據集不同的取值等因素，所以設置一個阻尼系數η來增加算法的可靠性，它的取值范圍為（0，1]。

如圖2所示。如果單純從節點連接的度數角度來識別有代表性的用戶，那么有些隱藏的重要節點就無法識別。例如節點1的度數為3，而節點2和節點3的度數均為5，這樣看起來好像節點1沒有節點2和節點3重要，但是節點1處于圖中的關鍵位置，它是節點2和節點3的溝通橋梁。這里的節點1就是隱藏的重要節點。那么，通過采用權鄰域計算方法，可以得到每個節點的權鄰域值，這里給出前三個節點的權鄰域值排名，即節點1為3.68、節點2為2.5、節點3為2.21。由此可以看出節點1最重要，因為節點1所處的位置比較核心，雖然它的度數不是最大的，但是它周圍的鄰居節點比較重要。在現實生活中，一個比較有影響的用戶，一般他周圍的朋友大多數都比較重要的。例如在一個研究鄰域中，比較有權威性的專家一般和影響力比較大的學者合著文章。同樣，僅從度數角度識別節點的代表性，有些度數相同節點的重要性便無法識別，如圖中節點2和節點3的度數一樣。但是采用提出的權鄰域計算方法可以發現，節點2的代表性高于節點3，因為節點2的鄰居節點相比較于節點3的鄰居節點更重要一些，所以節點2比節點3更具有代表性。

圖2 權鄰域舉例Fig.2 Example of weighted neighborhood

1.3 相關定義

為了研究方便，給出與本文算法相關的公式定義。定義1用戶代表度

用戶vi在屬性值ajl上對vi＇的代表度，稱之為用戶代表度，用B(vi,vi＇,ajl)表示。它的計算公式為用戶vi在屬性aj上的屬性值ajl占該用戶所有屬性和∑asl的比重與其權鄰域φi＇的乘積，公式如下：

其中，對于任意一個用戶vi,ajl表示用戶vi在屬性aj上的屬性值，∑asl表示用戶vi在所有屬性上的屬性值之和，vi＇表示用戶vi的鄰居，φi＇表示用戶vi的權鄰域值。

定義2屬性組

分層抽樣是將總體按照規定的比例從不同層中隨機抽取個體，由于這種方法抽到的樣本代表性比較好，抽樣誤差比較小，所以基于這個想法，將用戶按照屬性值劃分成不同的屬性組。通過定義一組個體Vl?V，其對應的屬性值為ajl，將這樣的一組個體與相應的屬性作為一個屬性組，用A表示所有組的集合，公式如下。其中，s表示屬性組的數目。

定義3屬性組代表度

對于一個屬性組(Vl,ajl)(1≤l≤s)，屬性組代表度表示子集T在屬性ajl上代表Vl中的所有人。通過計算用戶vi在該屬性組下用戶代表度的和，得到該屬性組的代表度，用P(T,l,ajl)表示，公式如下。其中，T表示對于該屬性組具有代表性的用戶子集。

定義4質量函數

目標是找到一個代表性集合，使得它對于所有屬性都具有最高的屬性組代表度，所以通過將用戶vi的所有屬性組代表度P(T,l,ajl)加起來，利用質量函數Q(G,X,A,T)對其進行數值化評估，公式如下：

其中，質量函數Q(G,X,A,T)中的G表示輸入的社交網絡，X表示屬性矩陣，A表示屬性組，T表示抽取的代表性用戶集合。參數ml表示每個屬性組(Vl,ajl)∈A的重要程度，取值為Vl的平方根。若它的取值較高，則表示該屬性組具有較好的代表性。參數β表示一種偏差，這種偏差是指通常會選擇一些不太具有代表性的用戶來增加全局代表性，它的取值范圍在（0，1]。

1.4 算法描述

目標是抽取一個代表性用戶子集，它能夠代表整個網絡中所有用戶的特點。因此，為了使得抽取的用戶更具有代表性，在統計分層抽樣模型基礎上對其進行改進。首先為了從網絡的拓撲結構中獲取用戶更多有用的信息，利用權鄰域對其進行描述；之后在計算用戶代表度的時候，采用將權鄰域與用戶屬性值相結合的方式進行用戶代表度的計算；然后根據屬性值將用戶分成不同的屬性組，計算用戶的屬性組代表度；接著把用戶所有屬性組代表度的增量累加起來，通過質量函數對其進行數值化評估；最后采用啟發式貪婪算法進行代表性用戶的抽取。按照上述方法以此類推，每次抽取增量值最大的用戶作為代表性用戶，直到選取足夠數量的代表性用戶為止，算法結束。代碼如下所示：

輸入：用戶集合V，屬性集合M，屬性個數X，用戶代表度B，抽取代表性用戶集合個數K。

輸出：代表性用戶集合T。

接下來，對本文提出的算法進行復雜性分析。每次遍歷所有的用戶并找到使得質量函數Q增量值最大的用戶作為代表性用戶，直到選取K個代表性用戶為止。在抽取代表性用戶的過程中，首先判斷代表性用戶集合中用戶個數是否小于K，如果滿足條件，則為變量賦初值；接著遍歷所有用戶來尋找使得質量函數Q增量值最大的用戶，并計算該用戶的屬性組代表度。其中，屬性組數量最大為t。然后在每個屬性組中，計算該用戶的用戶代表度。因此該算法整個過程所需要的時間復雜度為O(t×K× ||E)，空間復雜度為O(1)。這里的K表示抽取的代表性用戶數量，t表示屬性組的數量， ||E表示節點之間邊的數量。

其中，代碼第6～10行計算用戶在任意一個屬性組中的用戶代表度之和；代碼第5～12行計算用戶的所有屬性組代表度增量；代碼第13行計算通過增加用戶之后的質量函數的增量；代碼第14～17行判斷用戶的增量是否大于當前最大值增量，若大于當前最大值增量，就將用戶放入索引中，并更新相關參數；接著繼續遍歷下一個用戶，直到遍歷足夠數量的代表用戶，算法結束。

2 實驗

2.1 實驗環境

本文實驗所使用的計算機基本配置為Intel?Celeron?CPU N2930@1.83 GHz，4.00 GB內存，操作系統為Windows7，開發工具為CodeBlocks 17.12，使用C++語言進行編程。

2.2 數據集

本文一共選擇了四個數據集進行驗證，分別是ICWSM數據集、WSDM數據集、Database數據集[17]和Datamining數據集[17]。各個數據集如表1所示。

表1 各數據集統計Table 1 Statistics of each data set

ICWSM數據集和WSDM數據集分別收集了2015—2017年期間會議上發表的論文。對于作者屬性的提取，一共收集了50個作者發表論文的關鍵字作為作者屬性，同時將作者使用關鍵字的次數作為屬性值。其中，ICWSM數據集包含972個用戶和1 827個用戶之間的合著關系；WSDM數據集包含了692個用戶和1 340個用戶之間的合著關系。另外，由于一個會議的程序委員會一般是該領域的專家，所以通過將程序委員會中沒有合著關系的作者刪除，最終在這兩個數據集上分別選取2015—2017年間的111個和118個程序委員會成員作為標準代表性用戶集合。

為了驗證本文提出算法的有效性，又在兩個公開的數據集上進一步驗證。其中，Database數據集和Datamining數據集分別收集了2007—2009年發表在（SIGMOD、VLDB、ICDE）和（SIGKDD、ICDM、CIKM）上的論文。Database數據集包含8 027個用戶和23 770個用戶之間的合著關系；Datamining數據集包含了6 394個用戶和12 454個用戶之間的合著關系。在這兩個數據集上選取了在2007—2009年間的程序委員會作為標準代表性用戶集合，分別收集了291個和373個代表性用戶。

2.3 對比算法

使用度排序算法、PageRank算法、HITS算法、SSD算法和S3算法作為基線算法。

度排序[18]（Degree）算法。該算法是根據節點度的大小進行排序。

PageRank[19]算法。該算法的核心思想：若一個網頁被很多網頁鏈接，那么說明該網頁相對較重要，它的PageRank值也會相對較高；若一個PageRank值很高的網頁鏈接到其他的一個網頁，那么這個網頁的PageRank值也會相對比較高。其中，PR表示PageRank算法。

HITS[20]算法。該算法將網頁分為兩種，包括Hub頁面和Authority頁面。其中，Hub頁面是指包含了很多指向高質量Authority頁面鏈接的網頁；Authority頁面是指某個領域中網頁內容的質量比較高，由很多高質量的Hub頁面所指。其中，HITS_a和HITS_h分別表示HITS算法中以Authority和Hub為排序指標。

SSD和S3算法。它們分別表示文獻[17]中的多策略抽樣模型和統計分層抽樣模型。其中，SSD模型是將所選代表性用戶的多樣性最大化，這里的多樣性是指抽取的代表性用戶盡可能覆蓋多的屬性組。S3模型在前文已詳細闡述。按照原文獻中設置的參數?=0.6對其進行實驗。

2.4 評價指標

采用精確率、召回率和F1-Measure來評價每個算法的性能。

精確率主要用來評價算法的查準率，本文抽取結果列表中排名前M個用戶與標準代表用戶集進行對比，若其中有S個用戶位于標準代表用戶集中，則準確率如下式所示：

召回率主要用來評價算法的查全率，本文抽取結果列表中前K個用戶與標準代表用戶集進行對比，若其中有S個用戶位于標準代表用戶集N中，則召回率如下式所示：

由于準確率與召回率兩者存在一種互補關系，需要一個綜合指標涵蓋這兩個指標，于是引出了F-Measure。它是準確率和召回率的加權調和平均，本實驗采用F1-Measure作為評價指標，如下式所示：

2.5 實驗與分析

2.5.1 計算復雜性

在一般情況下，一個網絡中通常擁有成千上萬個節點，希望最終抽取的代表性節點是高效且合理的。接下來對7種算法的計算復雜性進行分析，如表2所示。這里n表示所有用戶，K表示抽取的代表性用戶，t表示屬性組數量， ||E表示節點之間邊的數量，t(ε)表示迭代次數，ε表示閾值。

表2 不同算法的計算復雜性Table 2 Computational complexity of different algorithms

從表2中可以看到，不同的算法具有不同的計算復雜性。其中，Degree算法的計算復雜性最低。PR算法的計算復雜度為O(t(ε)n2)。這里的迭代次數t(ε)與收斂的閾值有關，對于大型網絡，這個迭代次數t(ε)與邊的關系是接近線性的logn，所以最終PR算法的復雜性為O(n2logn)。HITS_a算法和HITS_h算法的計算復雜性均為O(t(ε)n2)，它與迭代次數有關。本文算法與S3算法和SSD算法的計算復雜性一樣，均為O(t×K× ||E)。S3算法在抽取代表性用戶的過程中，需要考慮該用戶與其鄰居能夠為屬性組做多少貢獻，直到抽取K個代表性用戶為止。對于SSD模型，每次選擇最貧窮的屬性組，并選擇一個用戶來增加該屬性組的代表程度，使得最終抽取的代表性用戶盡可能覆蓋多的屬性組。雖然本文算法的計算復雜性不是最低的，但本文算法在與S3算法和SSD算法計算復雜性相等的情況下，抽取到的代表性用戶更加準確。

2.5.2 參數影響

通過測試阻尼系數η和β的變化，分析其對本文算法的影響。其中，X軸表示參數β的取值，Y軸表示阻尼系數η的取值，Z軸是通過在Top10、Top35和Top75上抽取代表用戶之后，采用平均值來衡量不同阻尼系數η和參數β下抽取代表用戶的整體水平。各個數據集的參數影響如圖3～圖6所示。

圖3 Database數據集下參數的影響Fig.3 Influence of parameters on Database dataset

圖6 WSDM數據集下參數的影響Fig.6 Influence of parameters on WSDM dataset

為了在不同采樣率下都能夠抽取到更具代表性的用戶，通過反復實驗，在不同的數據集上取得最終參數結果。從圖3可以看出，在Database數據集上，參數β的取值范圍為（0，1]；阻尼系數η的取值范圍為（0，1]；Z軸的取值范圍為（19，24）。最終通過反復實驗，在Database數據集上參數β選取0.3，阻尼系數η選取0.5；從圖4可以看出，在Datamining數據集上，參數β的取值范圍為（0，1]；阻尼系數η的取值范圍為（0，10]；Z軸取值范圍為（22，27）。最終在Datamining數據集上參數β選取0.7，阻尼系數η選取3。從圖5可以看出，在ICWSM數據集上，參數β的取值范圍為（0，1]；阻尼系數η的取值范圍為（0，1]；Z軸取值范圍為（6.5，9）。最終在ICWSM數據集上參數β選取0.2，阻尼系數η選取0.5。從圖6可以看出，在WSDM數據集上，參數β的取值范圍為（0，1]；阻尼系數η的取值范圍為（0，10]；Z軸取值范圍為（14，18）。最終在WSDM數據集上參數β選取0.3，阻尼系數η選取2。接下來，通過在不同的數據集上按照上述選取的參數對本文的算法進行實驗。

圖4 Datamining數據集下參數的影響Fig.4 Influence of parameters on Datamining dataset

圖5 ICWSM數據集下參數的影響Fig.5 Influence of parameters on ICWSM dataset

2.5.3 實驗對比

本文通過在四個數據集上與Degree排序算法、PageRank算法、HITS_a算法、HITS_h算法、SSD算法和S3算法進行對比實驗，本文算法在各種評價指標方面都有提升，表3～表6給出各個數據集的實驗結果。

表3 在Database數據集上的實驗結果Table 3 Experimental results on database dataset%

表6 在WSDM數據集上的實驗結果Table 6 Experimental results on WSDM dataset %

在Database數據集上運行的實驗結果如表3所示，雖然在抽取前10個用戶中，本文算法與S3算法在精確率方面表現持平，但與其他算法相比有較大的提升，提升了30個百分點，提升率達到75%；在抽取前35個用戶中，與所有算法相比，本文算法在精確率方面有2.8個百分點的提升，提升率達到了5.2%；在抽取前75個用戶中，本文算法與所有算法相比，精確率有2.7個百分點的提升，提升率達到了5.1%。

由于在Database數據集中的標準代表用戶數為291個，而抽取的代表用戶僅為10～75個，故召回率相對較低。與所有算法相比，在抽取前35個用戶和75個用戶時，本文算法在召回率方面分別提高了0.4個百分點和0.7個百分點，提升率分別達到了6.2%和5.1%；雖然在抽取前10個用戶中，本文算法與S3算法表現持平，但與其他算法相比有較大的提升，提升了1個百分點，提升率達到71.4%；與所有算法相比，本文算法在F1-Measure有1.7百分點的提升，提升率達到了4.6%。

在Datamining數據集上運行的實驗結果如表4所示，當抽取前10個用戶時，本文算法優于其他所有算法，在精確率方面有10個百分點的提升，提升率達到了12.5%。尤其在抽取前35個用戶上，本文算法與S3算法相比有較高的提升，在精確率方面提高了8.5個百分點，提升率達到了13.5%；在抽取前75個用戶上，與所有算法相比，本文算法在精確率方面提高了4個百分點，提升率達到了6.7%。

表4 在Datamining數據集上的實驗結果Table 4 Experimental results on Datamining dataset%

由于在Datamining數據集有373個代表性用戶，而抽取的用戶僅為10～75個，所以召回率相對比較低。在抽取前10個用戶中，與所有算法相比，本文算法有0.3個百分點的提升，提升率達到了14.3%；在抽取前35個用戶中，與S3算法相比，本文算法提升了0.8個百分點，提升率達到了13.6%；在抽取75個用戶中，本文算法與所有算法相比，提升了0.8個百分點，提升率達到了6.6%。在F1-Measure評價指標上，與所有算法相比，本文算法提升了4個百分點，提升率達到了11.8%。

在ICWSM數據集上運行的實驗結果如表5所示，在抽取前10個用戶中，本文算法在精確率、召回率評價指標上和S3算法持平，但優于其他算法，在精確率方面有10個百分點的提升，提升率達到了50%；與S3算法相比，本文算法在Top35上的精確率提高了2.9個百分點，提升率達到了14.5%，召回率提高了0.9個百分點，提升率達到了14.3%；尤其在Top75上，本文算法在精確率方面提高了5.3個百分點，提升率達到了33.1%，召回率提高了3.6%，提升率達到了33.3%；與所有算法相比，本文算法在F1-Measure提高了1.8個百分點，提升率達到了10%。

表5 在ICWSM數據集上的實驗結果Table 5 Experimental results on ICWSM dataset %

在WSDM數據集上運行的實驗結果如表6所示，在抽取前10個用戶中，本文算法優于其他所有算法，在精確率上提高了10個百分點，提升率達到了16.7%，在召回率上提高了0.8個百分點，提升率達到了15.7%；在Top35上，與所有算法相比，本文算法在精確率方面提高了2.8個百分點，提升率達到了6.5%，召回率提高了0.9個百分點，提升率達到了7.1%；在Top75上，本文算法在精確率方面提高了4個百分點，提升率達到了13%，召回率提高了2.5個百分點，提升率達到了12.8%；與所有算法相比，本文算法在F1-Measure評價指標上提高了4.2個百分點，提升率達到了16%。

2.5.4 運行效率

本文通過計算算法的運行時間來評價算法效率，在實驗中通過記錄算法開始前的系統時間和算法結束后的系統時間，二者差值為算法的運行時間，算法的運行時間如表7所示。

表7 不同算法的運行時間Table 7 Running time of different algorithms s

在Database數據集上，本文算法比S3算法用時長0.22 s，在Datamining數據集上本文算法比S3算法用時長0.1 s。在ICWSM數據集和WSDM數據集上本文算法比S3算法用時均長0.02 s；雖然本文算法除了比PageRank算法耗時少之外，相比于其他算法耗時都比較多，但在精確率、召回率和F1-Measure方面均有提升，從而使得抽取的代表性用戶更加準確。

3 結束語

本文提出了基于權鄰域的抽樣算法來解決代表性用戶抽樣問題。為了使抽取的用戶更具有代表性，本文在計算用戶代表度時，不僅考慮了用戶的屬性，還融合了權鄰域方法來提取拓撲結構中用戶的豐富內容，最后采用啟發式貪婪算法對代表性用戶進行抽取。實驗結果表明該算法的性能在不同的數據集上均有提升。下一步的工作將會在本文的基礎上，對綜合考慮拓撲結構的局部和全局來抽取代表性用戶。