何賢芒　陳銀冬　李　東　郝艷妮

1(寧波大學(xué)信息科學(xué)與工程學(xué)院　浙江寧波　315211)2(汕頭大學(xué)工學(xué)院　廣東汕頭　515063)3(國家自然科學(xué)基金委員會信息中心　北京　100085)4(復(fù)旦大學(xué)計算機科學(xué)技術(shù)學(xué)院　上?！?00433)(hexianmang@nbu.edu.cn)

基于項目合作的社會關(guān)系網(wǎng)絡(luò)構(gòu)建

何賢芒1,4陳銀冬2李東3郝艷妮3

1(寧波大學(xué)信息科學(xué)與工程學(xué)院浙江寧波315211)2(汕頭大學(xué)工學(xué)院廣東汕頭515063)3(國家自然科學(xué)基金委員會信息中心北京100085)4(復(fù)旦大學(xué)計算機科學(xué)技術(shù)學(xué)院上海200433)(hexianmang@nbu.edu.cn)

摘要目前，基于論文合作關(guān)系的科學(xué)研究人員社會關(guān)系網(wǎng)絡(luò)得到了極大的關(guān)注，但是存在實體識別不準確、數(shù)據(jù)更新不及時等數(shù)據(jù)質(zhì)量問題.有鑒于此，提出利用歷年項目申請書的合作關(guān)系，同時將實體識別問題歸結(jié)為一個聚類問題，證明該問題的計算復(fù)雜度，然后提出了算法來解決該問題，最后在真實數(shù)據(jù)上驗證算法的效率.

關(guān)鍵詞項目合作；社會關(guān)系網(wǎng)絡(luò)；實體識別；聚類；計算幾何問題

由于社交網(wǎng)絡(luò)的繁榮發(fā)展和廣泛應(yīng)用, 越來越多的研究者將其科學(xué)研究和應(yīng)用開發(fā)的注意力集中到社會網(wǎng)絡(luò)這種虛擬世界當(dāng)中.社會網(wǎng)絡(luò)分析已然成為社會學(xué)、地理學(xué)、經(jīng)濟學(xué)、信息科學(xué)等諸多學(xué)科的重要研究內(nèi)容, 其研究涉及了數(shù)據(jù)挖掘、知識管理、 數(shù)據(jù)可視化、統(tǒng)計分析、社會資本、小世界理論、信息傳播等多個學(xué)科.基于社會關(guān)系網(wǎng)絡(luò)數(shù)據(jù)進行數(shù)據(jù)挖掘和潛在模式分析比傳統(tǒng)數(shù)據(jù)統(tǒng)計分析更加科學(xué)、效果更好、應(yīng)用前景更突出，通過對社會網(wǎng)絡(luò)進行挖掘可以獲得比簡單實體數(shù)據(jù)更詳實(如實體在社會網(wǎng)絡(luò)中的關(guān)系)、更準確(如挖掘?qū)嶓w間的關(guān)系)的信息.

目前國內(nèi)已有的基礎(chǔ)研究人員社會關(guān)系網(wǎng)絡(luò)主要是基于論文合作關(guān)系的信息服務(wù)平臺，具有代表性的工作有深圳愛瑞斯公司研發(fā)的科研之友[1]、清華大學(xué)知識工程庫開發(fā)的ArnetMiner[2]、CCF學(xué)術(shù)空間(僅限計算機領(lǐng)域的合作關(guān)系)[3]、中國人民大學(xué)研發(fā)的學(xué)術(shù)空間ScholarSpace[4]等.這些平臺共同的特點是提供了針對網(wǎng)絡(luò)中海量文獻檢索服務(wù)，同時從作者、期刊會議、工作單位、學(xué)科領(lǐng)域、合作者關(guān)系等多個角度進行統(tǒng)計與分析，還挖掘出基于論文合作的合作關(guān)系.但是上述平臺的數(shù)據(jù)主要抽取網(wǎng)絡(luò)中的不確定性數(shù)據(jù)，存在數(shù)據(jù)來源多樣化、格式不一致、數(shù)據(jù)不準確、更新不及時等數(shù)據(jù)質(zhì)量問題，導(dǎo)致實體識別不準確.本文的研究動機有如下2個：

1) 張冠李戴

在實踐中，作者中文姓名重復(fù)的現(xiàn)象非常普遍.比如中文名“張偉”，我們對CNKI數(shù)據(jù)庫經(jīng)過專門的實體識別后發(fā)現(xiàn)，存在460多個張偉.對這眾多似是而非模棱兩可的“張偉”，哪怕采用人工尚有不小難度，更何況是計算機呢？“張偉現(xiàn)象”的根本原因在于從論文中提取的信息太少，只包括姓名、單位、郵箱、期刊名、論文共同作者等有限信息，而且在關(guān)于郵箱信息上往往也只有通信作者的郵箱(如果考慮到格式問題，很多作者的郵箱也不完整).因此,基于論文合作的社會關(guān)系網(wǎng)絡(luò)的構(gòu)建，即使考慮領(lǐng)域信息和共同合作關(guān)系,也無法做到準確的識別.

“張偉現(xiàn)象”僅僅是以論文合作社會關(guān)系網(wǎng)絡(luò)的構(gòu)建中的一個普通案例.事實上，我們在嘗試構(gòu)建3 000多位國家杰出青年基金獲得者的社會關(guān)系網(wǎng)絡(luò)時，依然存在識別準確性不高的現(xiàn)象，特別是論文與作者間張冠李戴的現(xiàn)象相當(dāng)突出.因此，基于論文合作的社會關(guān)系網(wǎng)絡(luò)難以做到對實體的準確識別.

2) 項目合作

論文和項目都是科研工作者最主要的科研成果形式，也自然是科研合作最常見的表現(xiàn)形式.既然基于論文合作構(gòu)建社會關(guān)系網(wǎng)絡(luò)比較困難，那么是否可以基于項目合作來構(gòu)建社會關(guān)系網(wǎng)絡(luò)呢？通過項目共同參與申請，將實體聯(lián)系成一個復(fù)雜的社會關(guān)系網(wǎng)絡(luò).在社會關(guān)系網(wǎng)絡(luò)中，每一個實體都是一個頂點，同一申請書中的申請人A與參與者B之間存在有向邊：B→A，其他參與者之間沒有邊關(guān)聯(lián).由于申請人也往往是其他項目中的參與者，如此便構(gòu)成了一個復(fù)雜的社會關(guān)系網(wǎng)絡(luò).

以國家自然科學(xué)基金委員會(簡稱基金委) 每年接收的申請書為例，目前已累積1000多萬條申請人與參與人的信息，這些申請者的信息包括姓名、性別、單位、郵箱、身份證號、出生日期、職稱、申請人參與者等.通過對真實數(shù)據(jù)分析發(fā)現(xiàn)，絕大多數(shù)信息都是完整準確的.需要強調(diào)的是：同一實體在不同申請書中的信息有可能并非完全一致.比如由于工作調(diào)動而導(dǎo)致單位、郵箱等信息的變化.而更加特別的現(xiàn)象是，部分實體基于某些原因(比如規(guī)避基金委的申請限項規(guī)定)而故意錯誤填寫某些關(guān)鍵信息(比如身份證號碼).表1給出了項目申請書合作關(guān)系的一個示例.其中，id,prp_code,name,sex,org_name,birthday,email,is_pc,card_code等字段分別表示元組序號、項目受理號、姓名、性別、單位、出生日期、郵箱、是否項目負責(zé)人、身份證號等.基于隱私保護考慮，已對身份證號進行了替換處理.在通過手工整理與實體識別處理后發(fā)現(xiàn)：基于項目合作的社會關(guān)系網(wǎng)絡(luò)關(guān)系準確、可靠性高， 為科學(xué)基金項目管理提供輔助檢索與查詢，保證科學(xué)基金的公正與公平，具有重要的研究價值和現(xiàn)實需求.

Table 1　An Example of Cooperation in Project Application

本文的主要工作包括3個方面:

1) 提出了一個基于項目合作的社會關(guān)系網(wǎng)絡(luò)的構(gòu)建設(shè)想，并從中發(fā)現(xiàn)一個重要現(xiàn)象：3個屬性值相同的元組可以認定為同一實體，從而引出本文討論的主要問題.

2) 研究求解該問題的計算復(fù)雜度.通過證明該問題等價于計算幾何中的USEC問題，說明該問題的計算復(fù)雜度的下界滿足Ω(n),除非USEC問題和Hopcroft問題在算法理論上有重大突破.

3) 利用數(shù)據(jù)聚類方法構(gòu)建一個基于項目合作的社會關(guān)系網(wǎng)絡(luò),并提出高效的解決算法，同時基于真實數(shù)據(jù)對算法運行效率進行了驗證.

1基本概念與問題定義

給定一個數(shù)據(jù)集T(A1,A2,…,Ad),假定T共有d個屬性，用t[Ai] 表示其屬性值,數(shù)據(jù)集中的一個點稱為對象.

定義1.ε-鄰域B(p,ε).給定對象p，其半徑ε內(nèi)的區(qū)域稱為該對象的ε-鄰域.

定義2. 核心對象(core point).如果給定對象ε-鄰域B(p,ε)內(nèi)的樣本點數(shù)大于等于MinPts，則稱該對象為核心對象,其中參數(shù)MinPts是一個預(yù)先給定的正整數(shù).

定義3. 密度可達.對于數(shù)據(jù)集T，如果存在一個對象鏈p1=q,p2,p3,…,pk-1,pk=p,其中p1,p2,…,pk-1是核心對象，且pi+1∈B(pi,ε),i=1,2,…,k-1,則稱q密度可達p.

例1. 圖1給出一個密度可達的示例.此時MinPts=3，P7密度可達P5,對象鏈是P7,P6,P5，但P5并非核心對象.

Fig. 1　An example for MinPts=3.圖1　MinPts=3的示例圖

在數(shù)據(jù)整理的實踐過程中，我們發(fā)現(xiàn)了重要現(xiàn)象(以下統(tǒng)稱為“三屬性現(xiàn)象”)：

觀察1. 申請人數(shù)據(jù)庫中,在性別相同的情況下，任何2條元組只要在姓名、單位、郵箱、身份證、出生日期等5個主要屬性上有3個以上的值相同，可認定為同一實體.根據(jù)“三屬性現(xiàn)象”， 在表1中，元組t1,t5,t8,t4可認定為同一實體，元組t2,t3,t6也可認定為同一實體，而對元組t7則無法確定其是否與元組t2,t3,t6為同一實體.

此外，對于一些明顯錯誤的證件號碼比如123456,2222222,00000000等進行去除操作，同時注意到2個不同的申請人偽造了相同的證件號碼可能性是很低的,比如表1中的證件號碼000000123456789012，盡管是錯誤的，但仍然有參考價值.

定義4. 3-屬性值相同(3-attribute value same).任取數(shù)據(jù)集T中2條元組t1,t2∈T， 如果存在至少3個屬性值相同，便認定為同一實體.

定義5. 距離.2個元組t1,t2的距離dist(t1,t2)定義如下：

即若元組間取值相等的屬性數(shù)量大于等于3，則距離為1，否則距離為0.

定義6. 類(cluster).類(cluster)C是數(shù)據(jù)集T的非空子集，且滿足條件：

1) 3-屬性相同.任取元組t1,t2∈C，一定存在對象鏈p1,p2,…,pk-1，pk∈C，其中p1=t1,pk=t2，滿足距離dist(pi,pi+1)=1，i=1,2,…,k-1.

2) 極大性.任取t3∈T-C和t1∈C,則dist(t3,t1)=0.

例2. 表1中dist(t1,t5)=1,dist(t5,t8)=1,雖然dist(t1,t4)=0,但由于dist(t8,t4)=1,因此C1={t1,t4,t8,t5}構(gòu)成一個類,表1最終分成3個類C1={t1,t4,t8,t5},C2={t2,t3,t6},C3={t7}.

在完成聚類與類的定義之后，現(xiàn)在給出本文要解決的主要問題.

定義7. 問題1.給定一個數(shù)據(jù)集T和d個屬性T(A1,A2,…,Ad)，d>3,按照上述類和距離的定義，將數(shù)據(jù)集T分成不同的類.

2聚類問題的計算復(fù)雜度

首先給出2個計算幾何問題和若干已經(jīng)證明的相關(guān)結(jié)論.

2.12個計算幾何問題

定義8. USEC問題.給定一些半徑r相同的球集合SBall和點集Spt,判斷是否存在某個點p∈Spt,p在某個球內(nèi).其中，點和球均為d維數(shù)據(jù),d是常數(shù).

定義9. Hopcroft問題.給定2-D空間上的點集Spt和一些線SLine,判斷是否存在某些點p∈Spt，p在SLine的某些線上.

定義10. Hopcroft困難問題[5].如果問題X可以在O(n)內(nèi)解決,表明存在算法在O(n)內(nèi)解決Hopcroft問題， 那么問題X是Hopcroft困難問題.換句話說，如果Hopcroft問題能在Ω(n)時間內(nèi)解決，那么問題X也存在同樣時間復(fù)雜度的算法.

設(shè)n=|Spt|+|SBall|,當(dāng)d=3時，USEC問題可以在O((nlogn))內(nèi)解決， 而尋找時間復(fù)雜度O(n)的算法依然是公開難問題.類似地，設(shè)n=|Spt|+|SLine|,研究認為Hopcroft問題的時間復(fù)雜度是Ω(n),而對于USEC問題則有結(jié)果：

引理1[6]. 當(dāng)d≥5時,USEC問題是Hopcroft難問題.

2個計算幾何問題的示意圖如圖2所示：

Fig. 2　Two computational geometry problems.圖2　2個計算幾何問題

2.2計算復(fù)雜度

下面證明問題1與USEC問題等價，進而說明其與DBSCAN問題等價.

定理1. 當(dāng)d≥4時,問題1與USEC問題等價.

證明. 對于任意維數(shù)d≥4,如果我們能在f(n)時間內(nèi)解決問題1，那么就可以在f(n)+O(n)時間內(nèi)解決USEC問題.考慮到USEC問題是定義d空間上的Spt點集和半徑相同的SBall球集合.設(shè)算法A能在f(n)內(nèi)完成問題1.我們設(shè)計一個算法1在f(n)+O(n)時間內(nèi)回答USEC問題，n=|Spt|+|SBall|.

證畢.

算法1. USEC問題回答算法.

① 記SBall的球心集合為Scenter,設(shè)數(shù)據(jù)集P=Spt∪Scenter,球半徑ε=1;

② 在數(shù)據(jù)集上運行算法A；

③ 如果存在某個點p∈Spt和p′∈Scenter在同一個類中，那么回答Yes;

④ 否則回答No.

顯然，算法1的執(zhí)行時間不超過f(n)+O(n),下面分2種情形證明其正確性.

情形1. 回答Yes情形.

首先注意到如果把一個類里面的點作為頂點，若頂點間距離為1則用邊連接,那么在同一個類中的點便構(gòu)成一個連通圖.若p,p′處于同一個類中，則存在一個對象鏈:p1=p,p2,p3,…,pk-1,pk=p′,從而,一定存在pi,pi+1使得pi∈Spt,pi+1∈Scenter.考慮到pi∈B(pi+1,ε),從而球覆蓋了點pi.

情形2. 回答No情形.

相反地， 如果p和p′并非處于同一類中，那么二者之間的距離為0，故不存在某個pi屬于p′的ε-鄰域B(p,ε),因此回答是No.

定理2. 當(dāng)d≥4時,問題1與BSCAN問題等價.

Tao等人[7]證明了DBSCAN算法與USEC問題定價.結(jié)合定理1，定理2的結(jié)論不言而喻.事實上，問題1與DBSCAN問題的等價性是明顯的，只需巧妙設(shè)置DBSCAN問題中的2個參數(shù)(Minpts=1,ε=1)即可.此時，Minpts=1意味著DBSCAN里面所有點都是核心對象.

綜上，本文得到問題1的計算復(fù)雜度的結(jié)論如下：

① 當(dāng)d≥4時，問題1與USEC問題和DBSCAN算法均等價.

② 當(dāng)d=4時,問題1需要在Ω(n)時間內(nèi)解決，除非USEC問題可以在O(n)解決.

③ 當(dāng)d≥5時， 問題1是Hopcroft難問題,亦即問題1需要在Ω(n)時間內(nèi)解決，除非USEC問題可以在O(n)內(nèi)解決.

3相關(guān)工作

目前社會關(guān)系網(wǎng)絡(luò)研究中最受關(guān)注的是，除了基于論文合作的社會關(guān)系網(wǎng)絡(luò)外，還有基于論文引用的社會關(guān)系網(wǎng)絡(luò)[8]、基于電話的社會關(guān)系網(wǎng)絡(luò)[9]、基于關(guān)注的社會關(guān)系網(wǎng)絡(luò)(比如Twitter、微博)[10]、基于專利合作的社會關(guān)系網(wǎng)絡(luò)[11]等.同時，也有一些相應(yīng)研究與具體應(yīng)用.現(xiàn)在，已有超過20多個社會關(guān)系數(shù)據(jù)集發(fā)布于網(wǎng)上供公眾研究與測試.

對于社會關(guān)系網(wǎng)絡(luò)的研究分析主要包括3個方面：

1) 社會影響分析與行為分析.主要包括網(wǎng)絡(luò)上節(jié)點與邊的影響力分析、節(jié)點與邊的度量、節(jié)點介數(shù)等[12]；Kumar[13]研究了網(wǎng)站上博客信息動態(tài)傳遞行為、應(yīng)用傳染病機制來對主題傳播行為進行建模.Gruhl等人[14]探索了社會網(wǎng)絡(luò)會話結(jié)構(gòu)的形成，并用一種數(shù)學(xué)模型來刻畫用戶對話行為.文獻[15]研究了社會關(guān)系網(wǎng)絡(luò)中強連接節(jié)點問題.Liben-Nowell和Kleinberg[16]探討了人與人之間信息傳播過程來重構(gòu)大規(guī)模分發(fā)互聯(lián)網(wǎng)連鎖信的傳播機制，他們發(fā)現(xiàn)連鎖信通過一種很窄且很深像樹一樣的模式傳播.Yang 等人[17]分析了Twitter上用戶轉(zhuǎn)發(fā)行為,并提出了一個半監(jiān)督的框架來預(yù)測用戶的行為; Myers等人[18]研究了消息的擴散過程是如何受外來消息源的影響；文獻[19]提出了一個SPIKEM模型來表示消息傳遞的上升與下降模式.Huang[20]研究了社會關(guān)系網(wǎng)絡(luò)中的群體形成問題尤其是triad形成問題,并建立一個模型來在線預(yù)測動態(tài)社會關(guān)系網(wǎng)絡(luò)中closed triad的形成.

2) 社會關(guān)系分析.Tang等人[21]研究了異構(gòu)網(wǎng)絡(luò)環(huán)境下如何區(qū)分不同類型的社會關(guān)系,提出了一個整合了社會關(guān)系理論框架,可以有效地提升社會關(guān)系類型的區(qū)分.Wang等人[22]提出了一種挖掘?qū)熍c學(xué)生關(guān)系的TPFG模型，該模型以論文合作的社會關(guān)系作為研究對象.文獻[23]提出了一個監(jiān)督隨機游走算法來估計關(guān)系中的強度,Diehl等人[24]提出了一個排名函數(shù)來區(qū)別上下級關(guān)系.文獻[25]提出了移動通話數(shù)據(jù)中的幾種關(guān)系模式，并利用這些模式來推斷朋友關(guān)系網(wǎng)絡(luò).Sun等人[26]研究了多個類型動態(tài)網(wǎng)絡(luò)中社區(qū)演化．

3) 社會網(wǎng)絡(luò)結(jié)構(gòu)分析.Yang等人[17]研究了社會關(guān)系網(wǎng)絡(luò)的用戶轉(zhuǎn)發(fā)行為；Zhang等人[27]發(fā)現(xiàn)社會關(guān)系網(wǎng)絡(luò)的局部性，也就是一個人容易受到其最親密的朋友影響，形式化表述了這個現(xiàn)象并建立數(shù)學(xué)模型來預(yù)測用戶的轉(zhuǎn)發(fā)行為．結(jié)構(gòu)洞(structural holes)理論[28]也在社會關(guān)系網(wǎng)絡(luò)結(jié)構(gòu)分析中得到了應(yīng)用，文獻[29]研究了社會關(guān)系網(wǎng)絡(luò)的結(jié)構(gòu)洞形成問題,Lou等人[30]描述了如何挖掘大型社會關(guān)系網(wǎng)絡(luò)的結(jié)構(gòu)洞中top-k問題,并證明了該問題是NP-hard.

此外,關(guān)于DBSCAN算法的研究，最早是由Ester，Kriegel,Sander和Xu在KDD1996會議[31]上提出，一經(jīng)提出就受到了極大的關(guān)注.值得一提的是，DBSCAN算法的提出者一直誤以為其時間復(fù)雜度為O(nlogn),直到2013年才由Gunawan[32]指出其實際時間復(fù)雜度是O(n2),陶宇飛等人[7]在2015年SIGMOD會議上證明了DBSCAN算法的時間復(fù)雜度：當(dāng)數(shù)據(jù)維度是d=3或d=4時，DBSCAN算法與USEC問題等價；當(dāng)d≥5時，是Hopcroft難問題；同時，他們還提出了一個時間復(fù)雜度為O(n)的近似算法.特別地，對于2維數(shù)據(jù)，Han等人[33]提出了時間復(fù)雜度為O(nlogn)的算法，同時證明了類的數(shù)量正好等于圖的連通分量的數(shù)量.此外,對于Hopcroft問題，目前最好算法的時間復(fù)雜度大致比O(n) 稍大，具體可參閱文獻[34].

4實體識別算法

在本節(jié)，我們將提出實體識別算法，即問題1的求解算法.由第2節(jié)的討論可知，問題1的計算復(fù)雜度下界是Ω(n)，除非USEC問題與Hopcroft問題有了重大的理論突破,因此直接設(shè)計時間復(fù)雜度為O(nlogn)不太現(xiàn)實．此外，注意到近似算法對問題1沒有特別的意義，因此本節(jié)算法的設(shè)計是精確(exact)算法.

根據(jù)觀察得出的結(jié)論，對數(shù)據(jù)集T采用交叉比對的方法進行實體識別.算法2給出了一個初等的Na?ve算法，該算法的時間復(fù)雜度O(n2),n為數(shù)據(jù)集T的大小.4.2節(jié)將提出一個改進算法.

4.1基于規(guī)則的Na?ve算法

算法2. 基于規(guī)則的Na?ve交叉比對算法.

輸入：數(shù)據(jù)集T;

輸出：類C1,C2,…,Cm.

① fori=1 to |T|

② forj=i+1 to |T|

③ if (dist(ti,tj)=1)*如果3個屬性值相同*

④ 將ti和tj標記為同一個類;

⑤ end if

⑥ end for

⑦ end for

⑧ 按順序輸出每個類及其所包含的元組.

算法2的直接想法是檢查每對元組是否滿足3-屬性值相同，若相同就標記為同一實體，并放入同一類中．算法2雖然復(fù)雜度較高，但算法簡單，可作為基準算法和檢驗后續(xù)算法的準確性.

4.2基于分組的改進識別算法

對于大數(shù)據(jù)集，時間復(fù)雜度為O(n2)的算法2幾乎是不可接受的， 因此需要改進算法.問題1的本質(zhì)是找出所有至少3個屬性值相同的類{C1,C2,…,Cm}.我們可以先找出某一個屬性值相同的集合{T1,T2,…,Tk},然后對每個Ti進行交叉比對，從中找出并確定類{C11,C12,…,C1s}.以上便是算法3的基本思想.

為了解決問題1， 算法3至多運行d-2次,記錄每次算法的結(jié)果{Ci1,Ci2,…,Ci s},設(shè)元組t每次落在不同的類C1i,C2j,…,C(d-2)k,將這些類合并為一個類,當(dāng)所有的元組都完成合并時，算法便終止.

算法3. 基于分組的識別算法.

輸入：數(shù)據(jù)集T、T的某屬性Attr;

輸出：類C11,C12,…,C1m.

① 以屬性Attr為主進行排序;

② 將T劃分為T1,T2,…,Tk,使得T=T1∪T2∪…∪Tk,Ti∩Tj=?;

③ 對每個Ti進行交叉比對;

④ fori=1 to |Ti|

⑤ forj=i+1 to |Ti|

⑥ if (dist(ti,tj)=1)

⑦ 將ti和tj標記為同一個類;

⑧ end if

⑨ end for

⑩ end for

算法4是針對上述“合并”操作的算法，其基本思想是對于每個元組t,找出其落在2次不同分組的類C1,C2,計算差集C2-C1.如果差集C1-C2是空集，說明元組t前后2次不同的聚類后的結(jié)果相同，此時不需要進行合并； 如果差集C1-C2非空，那么說明元組t前后2次不同的聚類分在不同的類中，因此需要將類C1,C2合并.

算法4. 合并算法.

輸入：2個聚類結(jié)果l1和l2;

輸出：分組集合l1.

① fori=1 to |T|

② 設(shè)ti在2次聚類l1和l2的分組分別是C1和C2；

③Ci=C2-C1;*2個分組的集合差集*

④ ifCi=?*前后2次聚類結(jié)果相同*

⑤ continue;

⑦ 對Ci中的每個元組t

⑧merge(C1，Cj)*Cj是t在l1中所在的類*

⑨ end if

⑩ end for

5數(shù)據(jù)實驗報告

5.1數(shù)據(jù)預(yù)處理

在申請人的數(shù)據(jù)庫中，發(fā)現(xiàn)有些申請書的某些數(shù)據(jù)是故意填寫錯誤，比如不存在的證件號碼、依托單位信息變更、不符合規(guī)則的電子郵件等.預(yù)處理主要任務(wù)是去除這些不規(guī)范(甚至錯誤)的申請人數(shù)據(jù).具體做法是人工篩選出明確錯誤的數(shù)據(jù)共30 621條，直接將其從數(shù)據(jù)測試集中去掉.

用于測試的數(shù)據(jù)集是從國家基金委1986—2014年的申請書中提取的合作關(guān)系，共計9840477條數(shù)據(jù)，其中性別為男和女的2個數(shù)據(jù)集各有6 092 060條和3 748 417條.每條元組含8個屬性(項目編號、姓名、單位、郵箱、性別、是否主持人、證件號碼、出生日期).為了防止信息的泄露，所有的數(shù)據(jù)通過AES加密，相同的數(shù)據(jù)加密后依然相同，因此加密后的數(shù)據(jù)對算法沒有影響.為了測試算法的可擴展性，又分別從男與女2個數(shù)據(jù)集中隨機選取了1萬、5萬、10萬、20萬、50萬、100萬、200萬和全部的數(shù)據(jù)作為數(shù)據(jù)集分別測試,分別標記M1w,M5w,M10w,M20w,M50w,M100w,M200w,MTotal和F1w,F5w,F10w,F20w,F50w,F100w,F200w,FTotal.

下面將Na?ve算法(標記為NA)與改進算法(標記為PB，包括算法3和算法4)進行比較，2個算法均在相同的數(shù)據(jù)集上進行以保證算法的可比性.實驗主要目的是驗證算法的正確性與算法的效率.算法正確性通過比較2個算法識別出來的實體結(jié)果來驗證，算法效率通過比較算法的運行時間來驗證.本文的實驗環(huán)境為Intel?Xeon?CPU 2.4 GHz和RAM 8 GB,所有的算法和評估程序均采用C++實現(xiàn).

5.2算法結(jié)果

表2和表3分別給出了實體識別后的實體數(shù)量，實驗結(jié)果表明2個算法出來的結(jié)果是完全一致的.從表2和表3可以看出，從1986年至今我國從事自然科學(xué)研究的學(xué)者共有2 862 749人，其中女性與男性分別有1 171 655和1 690 394位，包括了各種行業(yè)各個級別的自然科學(xué)研究者，比如教授、副教授、教授級高級工程師等高級職稱研究者和博士生、研究生等各個層次.

Table 2　Number of Entities (Female)

Table 3　Number of Entities (Male)

5.3運行時間

表4比較Na?ve算法(NA)與改進算法(PB)的運行時間.從運行時間上看，NA算法的運行時間明顯比PB算法要短，而且NA算法的運行時間特征明顯：運行時間與數(shù)據(jù)集大小的平方成正比，比如當(dāng)數(shù)據(jù)集大小為50萬，運行時間是7 776 s左右，從而可以得出在100萬數(shù)據(jù)集上的運行時間大概是7 776 s的4倍，與實際運行時間相處無幾.PB算法共需要進行3次數(shù)據(jù)集的劃分，分別基于姓名、出生日期與證件號碼進行劃分后合并.從時間上來看，2個算法時間差別比較顯著，尤其是當(dāng)算法在女研究者數(shù)據(jù)全集上進行時NA算法執(zhí)行112 h，如果在男研究者數(shù)據(jù)全集上運行預(yù)計需要300 h，因此不在男研究者全集中執(zhí)行Na?ve算法.

Table 4　Running Time

從PB算法來看，基于不同的屬性劃分會產(chǎn)生不同的計算代價，其主要原因跟屬性值的分布密切相關(guān)，如果某個屬性在某個值上的重復(fù)值較多，那么交叉驗證時間比較多.表5中PB-1是算法3選擇姓名、出生日期與證件號碼進行了3次劃分，而PB-2 選擇姓名、郵件和證件號碼進行了3次劃分，二者時間差別很大，這是由于Email屬性值上重復(fù)值不多，而出生日期重復(fù)的情況比較多.表6比較2個算法在男研究者數(shù)據(jù)集上的運行時間，結(jié)果是完全類似的.

Table 5　Running Time of Different Attributes (Female)

Table 6　Running Time of Different Attributes (Male)

表7給出了PB-1選擇姓名、出生日期與證件號碼作為分組的屬性，而PB-2選擇姓名、郵件和證件號碼作為分組的屬性，算法的主要時間是3次分組和2次合并(表7中分別記為PAR1,PAR2,PAR3,MER1和MER2).從表7可以看出，算法的主要運行時間在第2次分組上，而選擇郵件作為分組的依據(jù)比選擇出生日期節(jié)省較多的時間，這是由于郵件重復(fù)的情形比出生日期要少很多.

Table 7　Composition of Running Time

6總結(jié)

如何從海量數(shù)據(jù)中發(fā)現(xiàn)基礎(chǔ)研究人員的合作關(guān)系，對于科學(xué)基金項目的全過程管理，為科學(xué)基金項目管理提供輔助檢索與查詢，保證科學(xué)基金的公正與公平，具有重要的研究價值和現(xiàn)實需求.針對歷年累積的申請書中的合作關(guān)系，本文提出了基于項目合作關(guān)系的基礎(chǔ)研究人員社會網(wǎng)絡(luò)關(guān)系的構(gòu)建.從實驗結(jié)果來看，1986—2014年我國從事自然科學(xué)研究的工作者大概有280多萬，其中男女比例大概是1.44∶1.針對項目合作社會關(guān)系網(wǎng)絡(luò)研究，我們將在社會網(wǎng)絡(luò)結(jié)構(gòu)分析、社會關(guān)系分析、社會影響分析與行為分析等方面開展工作，具體而言，包括基于項目合作網(wǎng)絡(luò)的結(jié)構(gòu)特征，從項目合作中挖掘出導(dǎo)師與學(xué)生關(guān)系、3人組(triad)形成等，這些工作的開展將會從另一視覺去審視基礎(chǔ)研究人員的社會關(guān)系網(wǎng)絡(luò).

參考文獻

[1]Liu X, Guo Z, Lin Z. A local social network approach for research management[J]. Decision Support Systems, 2013, 56(12): 427-438

[2]Tang J, Zhang J, Yao L, et al. ArnetMiner: Extraction and mining of academic social networks[C] //Proc of the 14th ACM SIGKDD Int Conf on Knowledge Discovery and Data Mining. New York: ACM, 2008: 990-998

[3]China Computer Federation. CCF Scholar[EB/OL]. [2015-12-02]. http://www.ccf.org.cn/sites/ccf/ccfscholar.jsp (in Chinese)(計算機學(xué)會. CCF學(xué)術(shù)空間[EB/OL]. [2015-12-02]. http://www.ccf.org.cn/sites/ccf/ccfscholar.jsp)

[4]Chen Wei, Wang Zhongyuan, Yang Sen, et al. ScholarSpace: An academic space for computer science researchers[J]. Journal of Computer Research and Development, 2011, 48(S3): 395-399 (in Chinese)(陳威, 王仲遠, 楊森, 等. ScholarSpace:面向計算機領(lǐng)域的學(xué)術(shù)空間[J]. 計算機研究與發(fā)展, 2011, 48(S3): 395-399)

[5]Erickson J. On the relative complexities of some geometric problems[C/OL] //Proc of Canad Conf Computer Geometry. 2010: 85-90. [2015-12-01]. http://cs.uiuc.edu/～jeffe/pubs/pdf/relative.pdf

[6]Erickson J. New lower bounds for Hopcroft’s problem[J]. Discrete & Computational Geometry, 1996, 16(4):389-418

[7]Gan Junhao, Tao Yufei. DBSCAN revisited: Mis-Claim, un-Fixability, and approximation[C] //Proc of the 2015 ACM SIGMOD Int Conf on Management of Data. New York: ACM, 2015:519-530

[8]Shi L, Tong H, Tang J, et al. VEGAS: Visual influence graph summarization on citation networks[J]. IEEE Trans on Knowledge & Data Engineering, 2015, 27(12): 1-15

[9]Ao Wenjing. Study of mining social network based on call records[D]. Guangzhou: South China University of Technology, 2013 (in Chinese)(敖文井. 基于通話記錄的社會關(guān)系網(wǎng)絡(luò)挖掘[D]. 廣州: 華南理工大學(xué), 2013)

[10]Zhang J, Fang Z, Chen W, et al. Diffusion of “Following” links in microblogging networks[J]. IEEE Trans on Knowledge & Data Engineering, 2015, 27(8): 2093-2106

[11]Tang J, Wang B, Yang Y, et al. PatentMiner: Topic-driven patent analysis and mining[C] //Proc of the 18th ACM SIGKDD Int Conf on Knowledge Discovery and Data Mining. New York: ACM, 2012: 1366-1375

[12]Sun J, Tang J. A Survey of Models and Algorithms for Social Influence Analysis[M] //Social Network Data Analytics. Berlin: Springer, 2011:177-214

[13]Kumar R, Mahdian M, McGlohon M. Dynamics of conversations[C] //Proc of the 16th ACM SIGKDD Int Conf on Knowledge Discovery and Data Mining. New York: ACM, 2010: 553-562

[14]Gruhl D, Guha R, Liben-Nowell D, et al. Information diffusion through blogspace[C] //Proc of the 13th Int Conf on World Wide Web. New York: ACM, 2004: 491-501

[15]Mishra N, Schreiber R, Stanton I, et al. Finding strongly knit clusters in social networks[J]. Internet Mathematics, 2008, 5(1):155-174

[16]Liben-Nowell D, Kleinberg J. Tracing information flow on a global scale using Internet chain-letter data[J]. Proceedings of the National Academy of Sciences of the United States of America, 2008, 105(12): 4633-4638

[17]Yang Z, Guo J, Cai K, et al. Understanding retweeting behaviors in social networks[C] //Proc of ACM Conf on Information & Knowledge Management. New York: ACM, 2010:1633-1636

[18]Myers S A, Zhu C, Leskovec J. Information diffusion and external influence in networks[C] //Proc of the 18th ACM SIGKDD Int Conf on Knowledge Discovery and Data Mining. New York: ACM, 2012:33-41

[19]Matsubara Y, Sakurai Y, Prakash B A, et al. Rise and fall patterns of information diffusion: Model and implications[C] //Proc of the 18th ACM SIGKDD Int Conf on Knowledge Discovery and Data Mining. New York: ACM, 2012:6-14

[20]Huang H, Tang J, Liu L, et al. Triadic closure pattern analysis and prediction in social networks[J]. IEEE Trans on Knowledge & Data Engineering, 2015, 27(12): 3374-3389

[21]Tang J, Lou T, Kleinberg J. Inferring social ties across heterogeneous networks[C] //Proc of the 6th ACM Int Conf on Web Search & Data Mining. New York: ACM, 2012: 743-752

[22]Wang C, Han J, Jia Y, et al. Mining advisor-advisee relationships from research publication networks[C] //Proc of the 16th ACM SIGKDD Int Conf on Knowledge Discovery and Data Mining. New York: ACM, 2010: 203-212

[23]Backstrom L, Leskovec J. Supervised random walks: Predicting and recommending links in social networks[C] //Proc of the 4th ACM Int Conf on Web Search & Data Mining. New York: ACM, 2010: 635-644

[24]Diehl C P, Namata G, Getoor L. Relationship identification for social network discovery[C] //Proc of the 22nd National Conf on Artificial Intelligence. Menlo Park, CA: AAAI, 2007: 546-552

[25]Eagle N, Lazer D. Inferring Social Network Structure Using Mobile Phone Data[M]. Berlin: Springer, 2008

[26]Sun Y, Tang J, Han J, et al. Co-evolution of multi-typed objects in dynamic star networks[J]. IEEE Trans on Knowledge & Data Engineering, 2014, 26(12):2942-2955

[27]Zhang J, Liu B, Tang J, et al. Social influence locality for modeling retweeting behaviors[C] //Proc of the 23rd Int Joint Conf on Artificial Intelligence. New York: ACM, 2013: 2761-2767

[28]Burt R S. Structural Holes: The Social Structure of Competition[M]. Cambridge, MA: Harvard University Press, 1992

[29]Goyal S, Vega-Redondo F. Structural holes in social networks[J]. Journal of Economic Theory, 2007, 137(1): 460-492

[30]Lou T, Tang J. Mining structural hole spanners through information diffusion in social networks[C] //Proc of the 22nd Int Conf on World Wide Web. New York: ACM, 2013: 825-836

[31]Ester M, Kriegel H, Sander J, et al. A density-based algorithm for discovering clusters in large spatial databases with noise[C] //Proc of the 3rd ACM SIGKDD Int Conf on Knowledge Discovery and Data Mining. New York: ACM, 1996: 226-231

[32]Gunawan A. A faster algorithm for DBSCAN[D]. Eindhoven, the Netherlands: Technische University Eindhoven, 2013

[33]Han J, Kamber M, Pei J. Data Mining: Concepts and Techniques[M]. San Francisco, CA: Morgan Kaufmann, 2012

[34]Hjaltason G R, Samet H. Index-driven similarity search in metric spaces[J]. ACM Trans on Database Systems, 2003, 28(4): 517-580

He Xianmang, born in 1981. Received his PhD degree from the School of Computer Science, Fudan University. Lecturer in the Faculty of Information Science and Engineering of Ningbo University. His main research interests include database, coding and cryptography.

Chen Yindong, born in 1983. Received his PhD degree from the School of Computer Science, Fudan University. Associate professor in the College of Engineering, Shantou University. His main research interests include information security and cryptology.

Li Dong, born in 1970. Received her master degree from the Department of Computer Science and Technology, Tsinghua University. Senior engineer in National Natural Science Foundation of China. Her main research interests include database technology and information system management.

Hao Yanni, born in 1978. Received her master degree from the School of Computer Science and Engineering, Beihang University. Engineer in National Natural Science Foundation of China. Her main research interests include database technology and information system management.

A Construction for Social Network on the Basis of Project Cooperation

He Xianmang1,4, Chen Yindong2, Li Dong3, and Hao Yanni3

1(FacultyofInformationScienceandEngineering,NingboUniversity,Ningbo,Zhejiang315211)2(CollegeofEngineering,ShantouUniversity,Shantou,Guangdong515063)3(InformationCenter,NationalNaturalScienceFoundationofChina,Beijing100085)4(SchoolofComputerScience,FudanUniversity,Shanghai200433)

AbstractFor the time being, the social network based on paper cooperation has gained a great deal of attention, but there exists inaccurate entity recognition, failing to update data in time, and uncertain data quality etc. In view of this, this paper puts forward the cooperation on the basis of the history project application, and the problem of the entity recognition attributes to a clustering problem. The computational complexity of the problem is proved. Then the algorithm is proposed to settle the problem. Finally, the efficiency of the algorithm is verified by the experiments on real data.

Key wordsproject cooperation; social network; entity recognition; clustering; computational geometry problems

收稿日期：2015-12-21；修回日期：2016-03-11

基金項目：國家自然科學(xué)基金項目(61103244，U1509213)；廣東省自然科學(xué)基金項目(2015A030313433)；廣東省高等學(xué)校優(yōu)秀青年教師培養(yǎng)計劃項目(Yq2013074)；廣東省普通高校特色創(chuàng)新項目(2015KTSCX036)；廣東省高校工程技術(shù)研究中心建設(shè)項目(GCZX-A1306)；信息與通信工程浙江省重中之重學(xué)科開放基金項目；中國博士后科學(xué)基金項目(2013M540323)；教育部人文社會科學(xué)研究項目(15YJA630069)；汕頭市科技計劃項目(98)

通信作者：陳銀冬(ydchen@stu.edu.cn)

中圖法分類號TP311.131

DOI:計算機研究與發(fā)展10.7544?issn1000-1239.2016.20151134 Journal of Computer Research and Development53(4): 785-797， 2016

This work was supported by the National Natural Science Foundation of China (61103244,U1509213), the Natural Science Foundation of Guangdong Province of China (2015A030313433), the Foundation for Distinguished Young Talents in Higher Education of Guangdong (Yq2013074), the Characteristic Innovation Project in Higher Education of Guangdong (2015KTSCX036), the Engineering and Technology Research Center of Guangdong Higher Education Institutes(GCZX-A1306), the Top Priority of the Discipline (Information and Communication Engineering) Open Foundation of Zhejiang, the China Postdoctoral Science Foundation (2013M540323), the Humanity and Social Science Foundation of Ministry of Education of China(15YJA630069), and the Shantou Science and Technology Foundation (98).