王其冬 李 東 周艷春 何賢芒

1(寧波大學(xué)商學(xué)院 浙江 寧波 315200)2(國家自然科學(xué)基金委員會信息中心 北京 100085)3(遼寧大學(xué)商學(xué)院 遼寧 沈陽 110036)4(東莞理工學(xué)院網(wǎng)絡(luò)空間安全學(xué)院 廣東 東莞 523808)

0 引 言

近年來，社會關(guān)系網(wǎng)絡(luò)的研究逐漸成為學(xué)術(shù)界研究的熱點。由于社交網(wǎng)絡(luò)的繁榮發(fā)展和廣泛應(yīng)用,越來越多的研究者將其科學(xué)研究和應(yīng)用開發(fā)的注意力集中到社會關(guān)系網(wǎng)絡(luò)這種虛擬世界中。社會關(guān)系網(wǎng)絡(luò)分析已然成為社會學(xué)、地理學(xué)、經(jīng)濟(jì)學(xué)、信息科學(xué)等諸多學(xué)科的重要研究內(nèi)容?；谏鐣P(guān)系網(wǎng)絡(luò)結(jié)構(gòu)進(jìn)行數(shù)據(jù)挖掘和潛在模式分析比傳統(tǒng)數(shù)據(jù)統(tǒng)計分析更加科學(xué)、效果更好、應(yīng)用前景更突出。隨著研究的深入，人們發(fā)現(xiàn)許多實際關(guān)系網(wǎng)絡(luò)具有一定的社團(tuán)結(jié)構(gòu)，也就是說，整個社會關(guān)系網(wǎng)絡(luò)是由很多個社團(tuán)組成，社團(tuán)之間的連接比較稀疏但社團(tuán)內(nèi)部相對稠密。社團(tuán)發(fā)現(xiàn)是利用社會關(guān)系網(wǎng)絡(luò)本身結(jié)構(gòu)挖掘出模塊化的社團(tuán)結(jié)構(gòu)。社團(tuán)發(fā)現(xiàn)有利于人們更加深入去理解整個網(wǎng)絡(luò)的結(jié)構(gòu)、功能，而且基于社會網(wǎng)絡(luò)的其他技術(shù)研究往往以社團(tuán)發(fā)現(xiàn)的結(jié)果作為依據(jù)。

帕累托法則(Pareto’s Principle)[1],又稱二八定律，不僅體現(xiàn)在經(jīng)濟(jì)學(xué)領(lǐng)域中的財富分布，也同樣適用于社會關(guān)系網(wǎng)絡(luò)中。這種現(xiàn)象在互聯(lián)網(wǎng)社交平臺得到了量化的數(shù)據(jù)支持。比如在Twitter[2]里，1%的人貢獻(xiàn)了超過50%原創(chuàng)內(nèi)容，而其他99%的人是轉(zhuǎn)發(fā)其他人的內(nèi)容為主。在微博上，流量明星擁有眾多的粉絲和粉絲群，而普通的使用者則只有幾十幾百的粉絲，這二類不同的網(wǎng)絡(luò)社交用戶是如何互動的呢？有其潛在的內(nèi)部結(jié)構(gòu)嗎？在社會關(guān)系網(wǎng)絡(luò)中，社團(tuán)發(fā)現(xiàn)已經(jīng)被廣泛研究。目前，學(xué)者們已經(jīng)提出了很多算法，比如譜聚類算法[3]、(α,β)-聚類[4]、基于傳導(dǎo)方法[5]、主題建模方法[6]、貪心算法[7]等，這些方法都有一個共同的特點，沒有考慮社會關(guān)系網(wǎng)絡(luò)中內(nèi)部的結(jié)構(gòu)。

從事自然科學(xué)基礎(chǔ)研究的群體，即通常所說的科學(xué)共同體，存在一種天然的社團(tuán)結(jié)構(gòu)和關(guān)系，而且是顯而易見的，這就是一個課題的負(fù)責(zé)人和參加者。我們利用國家自然科學(xué)基金申請者和參加者的數(shù)據(jù)，構(gòu)建圖結(jié)構(gòu)做此方面的研究，得到非常有趣的結(jié)果，這個結(jié)果對基金管理者或許有一定的啟示。

在國家自然科學(xué)基金委員會歷年申請人與參與人構(gòu)成的網(wǎng)絡(luò)中，由于學(xué)科代碼的不同，將申請人與參與人分成8個學(xué)部，45個科學(xué)處，科學(xué)處之間有交叉學(xué)科，也有不交叉學(xué)科。簡單地看，似乎申請人就是有影響力的人，然而并不是所有申請人都是影響力顯著的人。本文即是以項目合作關(guān)系網(wǎng)絡(luò)為基礎(chǔ)，根據(jù)這種關(guān)系網(wǎng)絡(luò)的結(jié)構(gòu)去設(shè)計特定的算法，在此基礎(chǔ)上進(jìn)行核心社團(tuán)發(fā)現(xiàn)，就是尋找真正影響力的基礎(chǔ)研究人員，而這些人才是基礎(chǔ)研究的中堅力量，我們可稱這些基礎(chǔ)研究人員為“核心科學(xué)家”。

1 相關(guān)工作

目前社會關(guān)系網(wǎng)絡(luò)研究中最受關(guān)注的，除了基于論文合作的社會關(guān)系網(wǎng)絡(luò)外，國外的主要有基于關(guān)注關(guān)系的Twitter,類似于國內(nèi)的微博。國內(nèi)已有的基礎(chǔ)研究人員社會關(guān)系網(wǎng)絡(luò)主要基于論文合作關(guān)系的信息服務(wù)平臺，具有代表性系統(tǒng)包括深圳愛瑞斯公司研發(fā)的科研之友、清華大學(xué)知識工程庫研發(fā)的ArnetMiner[9]系統(tǒng)、僅限于計算機領(lǐng)域合作關(guān)系的CCF學(xué)術(shù)空間[10]、中國人民大學(xué)數(shù)據(jù)庫組研發(fā)的學(xué)術(shù)空間[11]、基于論文引用的社會關(guān)系網(wǎng)絡(luò)[12]，此外，還有基于電話的社會關(guān)系網(wǎng)絡(luò)[8]。文獻(xiàn)[31]提出了基于項目合作社會關(guān)系網(wǎng)絡(luò)的構(gòu)建問題，并對這個問題進(jìn)行了研究，提出了實體識別算法等。目前對于社會關(guān)系網(wǎng)絡(luò)的研究大概可以分成以下三個方面：

1) 社會影響分析與行為分析。Sun等[13]探討網(wǎng)絡(luò)上頂點與邊的影響力分析、節(jié)點與邊的度量關(guān)系。文獻(xiàn)[14]討論大規(guī)模網(wǎng)絡(luò)上的合群性問題,提出了一個分布式機器學(xué)習(xí)算法構(gòu)建概論模型來預(yù)測用戶的行為。文獻(xiàn)[15]研究了社會關(guān)系網(wǎng)絡(luò)中強連接頂點問題。文獻(xiàn)[16]重構(gòu)人與人之間信息傳播途徑來模擬大規(guī)?；ヂ?lián)網(wǎng)分發(fā)連鎖信的傳播機制，發(fā)現(xiàn)連鎖信通過一種像樹一樣的很窄很深模式傳播途徑。Myers等[17]研究了消息的擴散過程是如何受外來消息源的影響。文獻(xiàn)[18]提出了一個半監(jiān)督(semi-supervise)學(xué)習(xí)框架來預(yù)測用戶轉(zhuǎn)發(fā)行為(Twitter)。文獻(xiàn)[26]研究了社會關(guān)系網(wǎng)絡(luò)的用戶轉(zhuǎn)發(fā)行為(weibo)。文獻(xiàn)[19]提出了一種按照主題分類的作者影響力分析方法。

2) 社會關(guān)系分析。文獻(xiàn)[21]研究了異構(gòu)網(wǎng)絡(luò)環(huán)境下如何區(qū)分不同類型的社會關(guān)系。文獻(xiàn)[22]以論文合作的社會關(guān)系為基礎(chǔ)，能夠從論文合作關(guān)系中挖掘出導(dǎo)師與學(xué)生關(guān)系。文獻(xiàn)[23]提出了監(jiān)督隨機游走(random walk)算法來評估頂點間的強度。文獻(xiàn)[24]提出了移動通話數(shù)據(jù)中的幾種關(guān)系模式，并利用這些模式來推斷朋友關(guān)系網(wǎng)絡(luò)。文獻(xiàn)[25]研究了多個類型動態(tài)網(wǎng)絡(luò)中社區(qū)演化。

3) 社會網(wǎng)絡(luò)結(jié)構(gòu)分析。文獻(xiàn)[27]等發(fā)現(xiàn)社會關(guān)系網(wǎng)絡(luò)的局部性，即個體容易受到其周圍朋友影響，利用這個局部性來預(yù)測用戶的轉(zhuǎn)發(fā)行為。文獻(xiàn)[20]研究了社會關(guān)系網(wǎng)絡(luò)中Triad形成,并討論其在信息傳播過程中的作用。文獻(xiàn)[28]提出的結(jié)構(gòu)洞(structuralholes)理論在社會系網(wǎng)絡(luò)結(jié)構(gòu)分析得到了實踐與應(yīng)用。文獻(xiàn)[29]研究了社會關(guān)系網(wǎng)絡(luò)的結(jié)構(gòu)洞形成問題。文獻(xiàn)[30]等形式化描述了大型社會關(guān)系網(wǎng)絡(luò)的結(jié)構(gòu)洞問題，利用網(wǎng)絡(luò)最大流最小割來挖掘結(jié)構(gòu)洞令人印象深刻。與本文關(guān)系最密切的是文獻(xiàn)[7],作者分別提出了貪心算法與weba算法，其貪心算法不斷從全局中選取度數(shù)最大的頂點直到滿足條件為止,weba算法是在貪心算法的基礎(chǔ)上做的改進(jìn)。

2 問題定義

先給出一些基本的定義：一個社會關(guān)系網(wǎng)絡(luò)可以用一個圖G(V,E)來表示,V表示頂點集合,E?V×V是邊的集合,|E|=m表示邊的數(shù)量，|V|=n表示頂點的數(shù)量。同時給出如下的重要定義：

定義1[核心社團(tuán)]給定一個圖G(V,E),e個互不相交的子集合{K1，K2,…,Ke}是核心社團(tuán)，如果滿足以下條件：

1) |E(u,Ki)|≥|E(v,Ki)|;

2) |E(Ki,u)|≥|E(Ki,v)|,這里的E(A,B)={(u,v)|u∈A,v∈B},A,B?V。

其中：?i,?u∈Ki,?v?Ki。

核心社團(tuán)在圖上表現(xiàn)出來的特點就是社團(tuán)內(nèi)部關(guān)系比較緊密，而社團(tuán)外的頂點與社團(tuán)關(guān)系比較稀疏，這種稀疏關(guān)系從二個方向進(jìn)或者出核心社團(tuán)都是如此。

定義2[輔助社團(tuán)]給定一個圖G(V,E),e個子集合{AK1，AK2,…,AKe}是輔助社團(tuán)，如果滿足以下條件：

1) ?i∈{1,2,…,e},AKi∩Ki=?

2) ?i,?j≠i,u∈AKi,|E(u,Ki)|≥|E(u,Kj)|

3) ?i∈{1,2,…,e},|E(AKi,Ki)|≥|E(Ki,Ki)|

這里的Ki是核心社團(tuán)。

一個核心社團(tuán)與輔助社團(tuán)是不相交的，輔助社團(tuán)與其對應(yīng)的核心社團(tuán)之間關(guān)系比較緊致，而且輔助社團(tuán)之間的關(guān)系不如其與核心社團(tuán)緊致。在項目合作的社會關(guān)系網(wǎng)絡(luò)中,核心社團(tuán)里的科學(xué)家互相之間關(guān)系是最緊的，輔助社團(tuán)里科學(xué)家與其核心社團(tuán)關(guān)系要比輔助社團(tuán)之間緊致，一般而言，核心社團(tuán)里面科學(xué)家大多是資深科學(xué)家，而輔助社團(tuán)里面則是一些同課題組的年輕科學(xué)家?？紤]到可能“核心科學(xué)家”同時出現(xiàn)在二個核心社團(tuán)中，這里的核心社團(tuán)Ki與Kj可以有相交的，不要求Ki∩Kj=?,i≠j。輔助社團(tuán)AKi與AKj也可以有相交的，不要求AKi∩AKj=?,i≠j。

基于以上這些定義與觀察，我們可以給出本文的問題定義。

定義3[問題定義]給定一個圖G(V,E)，問題是如何在可以接受的時間內(nèi)找出核心社團(tuán)與輔助社團(tuán)。

定義3中給出問題已經(jīng)被證明是NP-hard問題[32]。

3 基于貪心的挖掘算法

3.1 評價指標(biāo)

提出評價發(fā)現(xiàn)的社團(tuán)好壞的指標(biāo)，主要是考察其致密程度的四個指標(biāo):s0、s1、s2、s3，其定義分別如下：

定義4[緊致匹配]設(shè)頂點a在結(jié)果集Ci中，如果其鄰居節(jié)點b也在Ci中,邊(a,b)稱為一個緊致匹配。

s0是c2與c1的比值。c1是Ci中所有緊致匹配的數(shù)量，(a,b)同時有可能同樣地出現(xiàn)在測試數(shù)據(jù)集Bi中，其緊致匹配的數(shù)量記為c2。

s1與s0正好是反向計算，設(shè)頂點a在結(jié)果集Bi中，如果其臨接節(jié)點b也在Bi中，n1是Bi中所有緊致匹配的數(shù)量，(a,b)同時有可能同樣地出現(xiàn)在測試數(shù)據(jù)集Ci中，其緊致匹配的數(shù)量記為n2。

指標(biāo)s2是衡量二分類模型精確度的一種指標(biāo)：

指標(biāo)s3為計算結(jié)果集合Ci與測試基準(zhǔn)數(shù)據(jù)Bi的交集與并集的比值，表示結(jié)果集覆蓋了測試基準(zhǔn)集的比例：

本文采用s0、s1、s2、s3這四個指標(biāo)來評價社團(tuán)發(fā)現(xiàn)結(jié)果的好壞。

3.2 主要算法

算法的總框架如下所示。輸入圖G(V,E)和社團(tuán)大小k,輸出e個核心社團(tuán)。算法開始設(shè)置社團(tuán)為空，參數(shù)fmax是最小的整數(shù)。整個過程需要多次迭代，每次迭代都選擇一個頂點v加入S,v的度數(shù)需要滿足一定要求。當(dāng)S小于k時，調(diào)用貪心算法使得S中的元素數(shù)量等于k,然后計算本輪迭代的效果。如果比前面的結(jié)果好，那么更新這個結(jié)果，本輪的迭代結(jié)果以前沒有過，加入到最后的結(jié)果集中。

Input:G(V,E)， 社團(tuán)大小k

Output: 核心社團(tuán)K={K1,K2,…,Ke}

1.K←?,fmax=-INT_MAX

2. For step=0 to maxstep

3. S←chooseυ∈V

4. while |S|

5. call greedy _algorithm(v,k,V)

6. calculate its evaluationf

7. if (f>fmax) then

8.fmax=f

9.Smax=S

10. if (S?K) thenK={K,Smax}

11. return K

影響算法結(jié)果的關(guān)鍵步驟是第3步與第5步。選擇第一個頂點v加入到S與本次迭代的結(jié)果有重要的影響，考慮到本文的圖結(jié)構(gòu)存在孤立點(度數(shù)是0)，如果第一個頂點v是孤立的點，則本次的循環(huán)不起作用，因此第一個選入的頂點不能是孤立的頂點，而且要保證每次選擇的點不同。

貪心算法的啟發(fā)式策略是根據(jù)s0與s1的定義：頂點a如果加入到結(jié)果集,最好將其鄰居頂點中度數(shù)最大的頂點b也加入結(jié)果集,如此可以增加緊致匹配c2(n1)的數(shù)量,從而提高社團(tuán)的緊密度。根據(jù)此策略：第一步把節(jié)點v的所有鄰居節(jié)點N(v)都加入候選集合CS中，只要S小于k個節(jié)點，從CS集合中挑出度數(shù)最大的節(jié)點vv加入S，接著把vv的鄰居節(jié)點加入CS集，一直循環(huán)直到S滿足條件為止。

greedy_algorithm

Input:G(V,E) 社團(tuán)大小k，ν

Output:S

1. addN(v) toCS

2. while |S|

3. pick the max degree nodevvtoSfromCS

4. Add theN(vv) adjacent node to candidat setCS

5. returnS

一次迭代算法運行時間不超過O(n+m)，因此整個算法過程時間復(fù)雜度依然是O(n+m)。本算法與文獻(xiàn)[7]中提出貪心算法是有區(qū)別的，文獻(xiàn)[7]一直在選取全圖中最大度數(shù)的頂點加入到結(jié)果集中，實驗結(jié)果表明其貪心策略導(dǎo)致結(jié)果不一定最優(yōu)?？紤]到其致密指標(biāo)的定義，上述算法要求加入的頂點必須出現(xiàn)在已有結(jié)果集的鄰居頂點上，不一定是全圖最大度數(shù)頂點。

4 實 驗

用于測試的數(shù)據(jù)集是國家基金委每年申請書中提取的合作關(guān)系的9 840 477條數(shù)據(jù)，其中含有男性和女性數(shù)據(jù)各有6 092 060和3 748 417條。每條元組7個屬性(項目編號，姓名，單位，郵箱，性別，是否主持人，唯一身份標(biāo)記碼)，相同的申請人賦予一個相同的ID號，同時去除所有的學(xué)生，最后整理出來一個基于項目合作社會關(guān)系網(wǎng)絡(luò)，有1 173 788個頂點，每個頂點代表了一個科學(xué)家，4 627 413條邊，每條邊表示一種合作關(guān)系[31]。根據(jù)項目的受理編號，將所有的申請人與參與人分到8個學(xué)部。這些數(shù)據(jù)作為測試算法準(zhǔn)確性的測試基準(zhǔn)數(shù)據(jù)B={B1,B2,…,B8}，算法計算出的結(jié)果集記為C={C1,C2,…,C8}。

所有程序用C++實現(xiàn)，在IntelCore(TM) i7-6500CPU 2.5 GHz,8 GB內(nèi)存上運行，將本文算法(標(biāo)記為mygreedy)與隨機算法(標(biāo)記為random)、Weba算法(標(biāo)記為weba[7])、greedy算法(標(biāo)記為greedy[7])等相比較,結(jié)果如表1所示。迭代次數(shù)maxstep設(shè)為1 000次。

表1 四種算法對比結(jié)果

從計算結(jié)果上看，本文方法在主要指標(biāo)s2與s3上比其他幾種算法略勝一籌，random算法在大部分情況下是最差的，其次是greedy算法和weba算法。weba是在greedy算法基礎(chǔ)上做的改進(jìn)，從實驗結(jié)果來看，改進(jìn)效果并不明顯，相反在某些情況反而降低了其結(jié)果。從學(xué)部來看，數(shù)理學(xué)部的結(jié)果是最好的，這是由于數(shù)理學(xué)部成立時間最久，申請人與參與人的信息最完備，關(guān)系網(wǎng)絡(luò)較完整，聯(lián)系較強，而醫(yī)學(xué)部則是在2009年成立的，數(shù)據(jù)截止到2014年，數(shù)據(jù)量明顯偏少，而且社會關(guān)系網(wǎng)絡(luò)結(jié)構(gòu)較弱。

從計算指標(biāo)上看，所有的算法都突出s2，而s2是由s0與s1加權(quán)結(jié)果，結(jié)果中出現(xiàn)s0表現(xiàn)較好，s2反而不好的現(xiàn)象，這是由于算法迭代更新的時候只比較了s2。在管理學(xué)部，weba算法在指標(biāo)s2上表現(xiàn)得比mygreedy算法好，其余都不如mygreedy算法，且在信息學(xué)部與管理學(xué)部,weba算法不如greedy算法。當(dāng)合作關(guān)系比較密，本文算法效果較好(數(shù)理學(xué)部)，當(dāng)關(guān)系比較稀疏，本文算法效果與文獻(xiàn)[7]不相上下。

從運行時間來看，random算法用時超過48個小時，其余算法用時都在6個小時內(nèi)，沒有太多的比較意義，故省略。

5 結(jié) 語

本文通過將基金項目申請合作關(guān)系作為一種特定結(jié)構(gòu)的社會關(guān)系網(wǎng)絡(luò)，并有針對性地設(shè)計算法，為發(fā)現(xiàn)基礎(chǔ)研究中的核心社團(tuán)-核心科學(xué)家提供一種新的方法。該方法和結(jié)果對制定基金資助戰(zhàn)略布局和引導(dǎo)政策有一定的參考意義。