何水苗，班志杰

內(nèi)蒙古大學(xué) 計算機學(xué)院 內(nèi)蒙古自治區(qū)社會計算與數(shù)據(jù)處理重點實驗室，呼和浩特 010020

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

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

由于在網(wǎng)絡(luò)的拓撲結(jié)構(gòu)中也蘊含著用戶大量有價值的信息，所以為了從拓撲結(jié)構(gòu)中獲取用戶包含的豐富內(nèi)容，采用權(quán)鄰域?qū)W(wǎng)絡(luò)的拓撲結(jié)構(gòu)進行描述，并利用拓撲結(jié)構(gòu)和用戶屬性進行代表性用戶的抽取，最后通過實驗進一步檢驗了所提出算法的有效性。

1 基于權(quán)鄰域的代表用戶抽樣算法

1.1 問題描述

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

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

圖1 多屬性合著網(wǎng)絡(luò)Fig.1 Multi-attribute coauthor network

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

1.2 權(quán)鄰域

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

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

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

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

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

圖2 權(quán)鄰域舉例Fig.2 Example of weighted neighborhood

1.3 相關(guān)定義

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

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

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

定義2屬性組

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

定義3屬性組代表度

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

定義4質(zhì)量函數(shù)

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

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

1.4 算法描述

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

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

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

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

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

2 實驗

2.1 實驗環(huán)境

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

2.2 數(shù)據(jù)集

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

表1 各數(shù)據(jù)集統(tǒng)計Table 1 Statistics of each data set

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

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

2.3 對比算法

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

度排序[18]（Degree）算法。該算法是根據(jù)節(jié)點度的大小進行排序。

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

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

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

2.4 評價指標

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

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

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

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

2.5 實驗與分析

2.5.1 計算復(fù)雜性

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

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

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

2.5.2 參數(shù)影響

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

圖3 Database數(shù)據(jù)集下參數(shù)的影響Fig.3 Influence of parameters on Database dataset

圖6 WSDM數(shù)據(jù)集下參數(shù)的影響Fig.6 Influence of parameters on WSDM dataset

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

圖4 Datamining數(shù)據(jù)集下參數(shù)的影響Fig.4 Influence of parameters on Datamining dataset

圖5 ICWSM數(shù)據(jù)集下參數(shù)的影響Fig.5 Influence of parameters on ICWSM dataset

2.5.3 實驗對比

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

表3 在Database數(shù)據(jù)集上的實驗結(jié)果Table 3 Experimental results on database dataset%

表6 在WSDM數(shù)據(jù)集上的實驗結(jié)果Table 6 Experimental results on WSDM dataset %

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

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

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

表4 在Datamining數(shù)據(jù)集上的實驗結(jié)果Table 4 Experimental results on Datamining dataset%

由于在Datamining數(shù)據(jù)集有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數(shù)據(jù)集上運行的實驗結(jié)果如表5所示，在抽取前10個用戶中，本文算法在精確率、召回率評價指標上和S3算法持平，但優(yōu)于其他算法，在精確率方面有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數(shù)據(jù)集上的實驗結(jié)果Table 5 Experimental results on ICWSM dataset %

在WSDM數(shù)據(jù)集上運行的實驗結(jié)果如表6所示，在抽取前10個用戶中，本文算法優(yōu)于其他所有算法，在精確率上提高了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 運行效率

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

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

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

3 結(jié)束語

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