Web社會網(wǎng)絡的粗糙屬性圖模型及應用

張春英,郭景峰

(1.燕山大學信息學院，河北 秦皇島 066004;2.河北聯(lián)合大學理學院，河北 唐山 063009)

Web社會網(wǎng)絡的粗糙屬性圖模型及應用

張春英1,2,郭景峰1

(1.燕山大學信息學院，河北 秦皇島 066004;2.河北聯(lián)合大學理學院，河北 唐山 063009)

針對Web環(huán)境下的社會網(wǎng)絡具有信息粗糙性的特征，即Web數(shù)據(jù)中有大量垃圾內(nèi)容和垃圾鏈接，同時很多信息是不完整的、缺失的,且信息有重復現(xiàn)象存在等，在已提出的屬性圖模型基礎上，結合粗糙集理論解決不完備信息的優(yōu)勢，首先提出粗糙頂點屬性圖和粗糙邊屬性圖，進而給出粗糙屬性圖的概念，以對Web社會網(wǎng)絡結構進行分析，使其能夠描述復雜Web社會網(wǎng)絡中的不完整信息以及動態(tài)變化的鏈接。其次對粗糙屬性圖的粗糙特性進行分析，給出粗糙頂點精度、粗糙邊精度和粗糙圖精度等概念，得出粗糙屬性圖的精度與頂點和邊集屬性劃分程度有關的結論，即人們對圖的認知程度與圖的精度密切相關。最后，在中國知網(wǎng)上通過對論文作者進行查詢得到粗糙圖，并通過不斷添加頂點屬性，將圖頂點劃分得越來越精細，挖掘出要查詢的作者合作關系圖，從而說明粗糙屬性圖在社會網(wǎng)絡分析中符合人們的認知過程。

Web社會網(wǎng)絡；屬性圖；粗糙頂點屬性圖；粗糙屬性圖；圖精度

1 引言

社會網(wǎng)絡是以社會生活中人類或組織的行為活動為研究對象，將其抽象為相互作用的個體組成的網(wǎng)絡。這樣的網(wǎng)絡無處不在，并且與我們的生活密切相關，如演員合作網(wǎng)絡、科學家合作網(wǎng)絡、恐怖分子網(wǎng)絡、疾病傳染網(wǎng)絡以及虛擬社會網(wǎng)絡等等。社會網(wǎng)絡研究[1]是理解社會現(xiàn)象、預測人類行為、分析社會結構的重要工具。通過研究社會網(wǎng)絡的結構和性質，可以幫助我們更深刻地理解社會現(xiàn)象，對現(xiàn)實中的決策、管理、優(yōu)化問題都有極其重要的意義。

社會網(wǎng)絡研究是以傳統(tǒng)圖論為工具進行的研究，將網(wǎng)絡中的對象描述為結點，對象之間的關系用線表示[1,2]。圖在社交網(wǎng)絡中有著重要的應用，如近鄰查詢、圖壓縮、圖匹配、圖搜索等[3～6]。然而這種傳統(tǒng)圖只能描述結點與結點的關系，無法了解結點本身信息，也無從知曉更多關系信息，所以作者在傳統(tǒng)圖論的基礎上，結合數(shù)據(jù)庫中的屬性依賴理論，提出屬性圖概念，以對Web社會網(wǎng)絡結構進行分析[7,8]。屬性圖是考慮了結點和連接屬性以及屬性之間關系的圖結構，是傳統(tǒng)圖的擴展；而在不考慮屬性的情況下，屬性圖退化為傳統(tǒng)圖，所以傳統(tǒng)圖是屬性圖的特例。對屬性圖結構及其各種特性、操作的研究則是對傳統(tǒng)圖理論的補充和創(chuàng)新。

然而，Web環(huán)境下的社會網(wǎng)絡具有信息粗糙性的特征，即Web數(shù)據(jù)中有大量垃圾內(nèi)容和垃圾鏈接，同時很多信息是不完整的、缺失的[8～11]。如在微博上，用戶在填寫個人信息時，有的信息不填寫，有的信息填寫的是虛假信息；又如在論文網(wǎng)絡中，有的作者未填寫研究方向，有的作者單位信息發(fā)生了變化。而屬性圖在描述社會網(wǎng)絡中的結點時則是在信息完整的假設下建立的，如何改進屬性圖，使其能夠描述復雜Web社會網(wǎng)絡中的不完整信息以及動態(tài)變化的鏈接是本文要解決的問題。為此在屬性圖基礎上，融合粗糙集理論[12～16]，提出粗糙屬性圖，并研究其性質特征。粗糙屬性圖是對屬性圖的拓展，考慮了邊和結點屬性的粗糙性。

本文結構如下：

第2節(jié)對屬性圖基本概念進行描述；第3節(jié)提出粗糙屬性圖概念及相關定理；第4節(jié)分析了粗糙屬性圖的粗糙特性；第5節(jié)是一個應用實例；最后給出結論及下一步的研究方向。

2 屬性圖及其結構

定義2 在屬性圖GA=(V(VA,LV),E(EA,LE))中，VA={va1,va2,…，va|VA|} 為V上的屬性集合，除了頂點標識屬性外，能唯一區(qū)分一個頂點的屬性稱為頂點的關鍵屬性。

定義3 在屬性圖GA=(V(VA,LV),E(EA,LE))中，在邊集E上有屬性集合EA={ea1,ea2,…,ea|EA|}，除了頂點屬性外，唯一能標識一條邊的屬性為邊的關鍵屬性。

在此，pk表示eij上的第k個屬性值，而此屬性值又會是另外一些屬性值的集合，k=1,2,…,p;i,j=1,2,…,|V|。

3 粗糙屬性圖結構

對于屬性圖來說，描述其屬性的既有頂點屬性又有鏈接屬性，而二者都可能是不完備的、粗糙的。故在此首先給出粗糙頂點屬性圖和粗糙邊屬性圖的概念，繼而給出粗糙屬性圖的定義。

3.1 粗糙頂點屬性圖

定義7 設U={e1,e2,…,e|U|}為論域，R={r1,r2,…,r|R|}為U上的屬性集合，并且R=VA∪EA，且EA中包含頂點屬性(vi,vj)，vi∈V(VA,LV)，vj∈V(VA,LV)，VA={va1,va2,…,va|VA|}為V上的屬性集合。設E(EA,LE)=∪ek(ea1,ea2,…,eam,(vi,vj))是U上的邊集，稱屬性圖GA= (V(VA,LV),E(EA,LE))為論域圖。

定義8 在論域圖GA=(V(VA,LV),E(EA,LE))中，對于任意V上的屬性集Rva?VA?R，V上的元素按Rva劃分為不同的等價類[v]Rva。任取屬性子圖TA=(W(WA,LW),X(XA,LX))，其中：

W(WA,LW)?V(VA,LV)，X(XA,LX)?E(EA,LE)

X′={ek|ek∈E,vi∈W,vj∈W,(vi,vj)是ek的頂點屬性}

由定義8，定理1顯然成立。

結論1 精確頂點屬性圖是一類特殊的粗糙頂點屬性圖。

3.2 粗糙屬性圖

在前面的粗糙頂點屬性圖中，只考慮頂點屬性是粗糙的，實際上，在屬性圖中，邊或者鏈接也是有屬性的，且這些屬性也有可能是未知的、不完整的，且邊或鏈接的屬性中包含頂點屬性(vi,vj)，一個圖只有頂點不能稱之為圖，只有頂點由邊連接起來才會成為圖。為此，首先定義粗糙邊屬性圖，再進一步給出粗糙屬性圖的定義。

定義9 在論域圖GA=(V(VA,LV),E(EA,LE))中，對于任意E上的屬性集Rea?EA?R，且頂點屬性(vi,vj)∈Rea。E上的元素按Rea劃分為不同的等價類[e]Rea。任取屬性子圖PA=(Q(QA,LQ),Y(YA,LY))，其中：

Q(QA,LQ)?V(VA,LV)，Y(YA,LY)?E(EA,LE)

定義10 在論域圖GA=(V(VA,LV),E(EA,LE))中， 對于任意V上的屬性集Rva?VA?R，V上的元素按Rva劃分為不同的等價類[v]Rva；對于任意E上的屬性集Rea?EA?R，且頂點屬性(vi,vj)∈Rea，E上的元素按Rea劃分為不同的等價類[e]Rea。

設Ra=Rva∪Rea,任取屬性子圖RA=(W(WA,LW),Y(YA,LY))，其中：

W(WA,LW)?V(VA,LV)，Y(YA,LY)?E(EA,LE)

當W(WA,LW)能表示成某些[v]Rva的并，且Y(YA,LY)能表示成某些[e]Rea的并時，則稱屬性圖RA為Ra-可定義屬性圖或Ra-精確屬性圖；否則稱屬性圖RA為Ra-不可定義屬性圖或Ra-粗糙屬性圖。

在兩個屬性圖是否相等的問題上，粗糙屬性圖和傳統(tǒng)意義上的屬性圖有一個重要的區(qū)別：傳統(tǒng)意義上的屬性圖，必須兩個屬性圖的頂點和邊完全相等，且對應頂點和邊具有相同屬性，才認為兩個屬性圖相等。兩個在傳統(tǒng)意義上不相等的屬性圖，在粗糙屬性圖中卻可能是相等的，因為在粗糙屬性圖中，兩個屬性圖是否相等是根據(jù)人們得到的知識判斷的，當兩個屬性圖的Ra-上、下近似屬性圖都相等時，由于知識的粗糙性，此時，認為兩個屬性圖是相等的。

下面給出粗糙屬性圖相等的概念。

定義13 給定粗糙屬性圖集M、屬性集R，則K=(M,R)是一個屬性圖知識系統(tǒng)，H、J?M。

4 粗糙屬性圖的粗糙特性

粗糙屬性圖的不確定性類似于粗糙集，是由其邊界域的存在而引起的，邊界域越大，其精確性越低。粗糙屬性圖的邊界域包括頂點集邊界域和邊集邊界域。為了更準確地表達粗糙屬性圖的精確性，引入粗糙屬性圖精度的概念。

這里,W?V≠?，|A|表示集合A的基數(shù)。

頂點精度αvRva(RA)用來反映人們對于粗糙屬性圖RA頂點集合W知識了解的完全程度。

這里,Y?E≠?，|A|表示集合A的基數(shù)。

邊精度αeRea(RA)用來反映人們對于粗糙屬性圖RA邊集合Y知識了解的完全程度。

αRa(RA)=αvRva(RA)×αeRea(RA)

定理4 (1)給定粗糙屬性圖集M，對任意頂點屬性集Rva，TA?M，都有0≤αvRva(TA)≤1;

□

由定義14和定理4可知，由于人們對于粗糙屬性圖TA頂點集W的知識了解完全程度的不同，反映在圖中即為頂點屬性集的豐富程度的不同，則頂點精度也會不同。因此，有以下定理：

定理5 給定粗糙屬性圖集M，?TA?M，若頂點屬性集Sva、Rva滿足Sva?Rva，則：

αvSva(TA)≤αvRva(TA)

□

定理5說明，頂點集按不同的屬性劃分越細，所得的頂點精度越高，即人們對粗糙屬性圖TA頂點集的知識了解越完全。

定理6 (1)給定粗糙屬性圖集M，對任意邊屬性集Rea，TA?M，都有0≤αeRea(TA)≤1;

定理7 (1)給定粗糙屬性圖集M，對任意屬性集Ra=Rva∪Rea，TA?M，都有0≤αRa(TA)≤1;

定理8 給定粗糙屬性圖集M，?TA?M，若邊屬性集Sea、Rea滿足Sea?Rea，則：

αeSea(TA)≤αeRea(TA)

定理8說明，邊集按不同的屬性劃分越細，所得的邊精度越高，即人們對粗糙屬性圖TA邊集的知識了解越完全。

定理9 給定粗糙屬性圖集M，?TA?M，若屬性集Sa、Ra滿足Sa?Ra，則：

αSa(TA)≤αRa(TA)

定理9說明，頂點和邊集按不同的屬性劃分越細，所得的圖精度越高，即人們對粗糙屬性圖TA的知識了解越完全。

5 應用實例

在論文合作網(wǎng)絡中，作者重名現(xiàn)象很嚴重。如果按作者姓名查找某人的合作關系，是不能完全精確得到的，這時只能得到一個粗糙頂點關系圖。另外，在合作網(wǎng)絡中，作者與作者的關系除了具有論文合作關系外，實際上還會擁有師生關系、同事關系、朋友關系等。在無法確認其實際關系時，則作者之間的邊也是粗糙的。由此得到的論文作者合作關系圖即為粗糙圖。

在本實例中，假設有某人要查看作者本人在中國知網(wǎng)上的論文合作關系情況，由于只知道本人的名字，其他信息暫不了解。所以，他在中國知網(wǎng)上按條件作者=“張春英”進行查詢，共搜出842篇文獻。如果不考慮第幾作者都算是有合作關系的話，就有1 863個作者與“張春英”有過合作。根據(jù)這個合作關系可以構建以“張春英”為核心的一個關系圖。很顯然，這個圖是不準確的，因為在查到的記錄中，“張春英”這個頂點代表的是很多個作者的綜合體，他們同屬于在“張春英”這個屬性下劃分的同一個等價類，是無法區(qū)別的。同樣，在與“張春英”合作過的作者中，再去查找他們的合作作者，這些作者也不是唯一的。如在合作作者中有“劉鳳春”，但他仍然是一個綜合體。由此可知，在只知道作者姓名時構建的論文合作網(wǎng)絡是粗糙的、不精確的。每個頂點都是由多個潛在的實體構成，不能唯一地代表某個確定的作者。圖1即為在中國知網(wǎng)中按照作者分別查詢“張春英”、“劉鳳春”、“劉保相”、“閻紅燦”和“陳麗芳”的合作作者得到的合作關系圖。

在圖1中，每個作者構成的頂點都是由多個來自不同單位不同研究方向的作者(來自于288個單位)構成的，所以頂點是粗糙的。在此基礎上，以“研究方向”劃分等價類，共有“計算機”、“教育”、“化工”、“醫(yī)學”、“生物”等類別。為了進一步縮小范圍，經(jīng)過分析得知，該作者可能是河北的，故選取單位為“河北*”的作者子集，此時找到65篇論文，分為“計算機”、“教育”、“醫(yī)學”和“經(jīng)濟”四類。這樣在找合作關系時，作者“張春英”這個頂點包含四類人物，每類人物與其他作者合作的論文數(shù)量分別是：32、6、21、6。而在所有“張春英”這個作者中，與其他作者在這四類中合作的論文數(shù)量分別是：44、37、308、41。繼續(xù)按作者單位進行分類，可得到16個單位，如果認為同一單位的“張春英”只有1人，則在“張春英”這個頂點的下近似頂點中包含16個作者，而其上近似頂點中包含288個來自不同單位的作者，則該頂點的精度為16/288=0.05。若只選取“計算機”、“教育”、“醫(yī)學”和“經(jīng)濟”這四個研究方向的作者，則有222個來自不同單位的作者，則該頂點的精度為16/222=0.07。這個精度仍然很低，為了進一步發(fā)掘作者信息，后來明確該作者的主要研究方向為“計算機”和“教育”且為河北的，則其上近似作者有5個，下近似作者有16個，則其精度為5/16=0.3。其合作作者來自不同單位不同行業(yè)，顯然這有些不太合理。

Figure 1 Cooperative relations figure that in accordance with the inquiry of the author’s name圖1 按作者姓名查詢得到的合作關系圖

再進一步考證該作者的單位，發(fā)現(xiàn)其來自于“河北聯(lián)合大學理學院”，同時該單位原名稱為“河北理工大學理學院”，故可精確挖掘到該作者，其上、下近似作者均為1個，則其精度達到100%。如此，該作者的真實合作關系網(wǎng)絡才真正被挖掘出來，是通過逐步增加屬性，去粗求精得出來的，如圖2所示。

Figure 2 Authors’ cooperation relations figure, after the research direction of the author are explicit圖2 在明確作者研究方向后作者的合作關系圖

可在此基礎上，進一步研究其主要合作作者如“劉保相”、“劉鳳春”、“郭景峰”等與其他作者的合作關系圖，從而挖掘其更大的關系社區(qū)，探究該作者可能拓展的合作關系。

另外需要說明的是，該實例只從頂點屬性角度考慮了圖的粗糙性，其實隨著頂點劃分不斷細化，其邊屬性也逐漸明了，從而邊的精度也在逐漸增強，整個圖的精度也就越來越高。

6 結束語

考慮社會網(wǎng)絡中頂點和鏈接屬性的不完備性，將粗糙集理論引入到屬性圖中，用以描述Web社會網(wǎng)絡中不完備、不確定的屬性頂點和鏈接，從而解決社會網(wǎng)絡中不確定信息的表示問題；給出了粗糙頂點屬性圖、粗糙邊屬性圖以及粗糙屬性圖的定義，并給出了相關定理；進一步分析了粗糙屬性圖的粗糙特性，得出粗糙屬性圖的精度與頂點和邊集屬性劃分程度有關，即劃分越細，所得的圖精度越高，人們對粗糙屬性圖TA的知識了解越完全。如何增強粗糙屬性圖的計算能力以及更好地進行應用推廣是下一步要深入研究的工作。

[1] Scott J．Social network analysis：A handbook[M]．London：Sage Publications，2000．

[2] Newman M. Finding community structure in networks using the eigenvectors of matrices[J]. Physical Review E, 2006, 74(3):036104.

[3] Chen Lin. Mining web social network[D]. Shanghai:Fudan University,2009.(in Chinese)

[4] Duan Xiao-dong, Wang Cun-rui, Liu Xiang-dong, et al. Web community detection model using particle swarm optimization[J]. Computer Science, 2008,35(3):18-21.(in Chinese)

[5] Wen Fei, LI Jian-zhong,Ma Shuai, et al. Graph homomorphism revisited for graph matching[J]. Proc of the VLDB Endowment,2010,3(1-2):1161-1172.

[6] Ma Shuai, Cao Yang, Fan Wen-fei, et al. Capturing topology in graph pattern matching[J]. Proc of VLDB Endowment,2012,5(4):310-321.

[7] Guo Jing-feng,Zhang Chun-ying,Chen Xiao. Attribute graph and its structure[J]. ICIC Express Letters,2011,5(8):2611-2616.

[8] http : //www.digitalbuzzblog.com/facebook-statistics-stats-facts-2011/.

[9] http://en.wikipedia.org/wiki/facebook.

[10] Ma Shuai, Li Jia, Liu Xu-dong, et al. Graph search:A new searching approach to the social computing era[J]. Communications of the CCF, 2012,8(11):26-33.(in Chinese)

[11] Zhu Yuan-yuan, Qin Lu, Yu Xu. Research on problem of image matching[J]. Communications of the CCF, 2012,8(11):21-27.(in Chinese)

[12] Guo Jing-feng, Hao dan-dan, Zheng Chao. An algorithm based on attributed relational graph for name disambiguation[J]. ICIC Express Letters, 2010,5(1):113-118.

[13] Cui Yu-quan, Zhang Li, Shi Kai-quan. Study of the dynamic characteristics of Rough sets[J].Shandong University,2010,45(6):8-13.(in Chinese)

[14] He Tong, Lu Chang-jing, Shi Kai-quan. Rough graph and its structure[J]. Shandong University,2006,41(6):46-50.(in Chinese)

[15] Pawlak Z. Rough sets[J]. International Journal of Computer and Information Sciences,1982(11):341-356.

[16] Zhou Ai-wu,Zhou Shan-shan,Zou Wu,et al.An algorithm of attribution reduction of variable precision rough sets theory[J]. Computer Technology and Development, 2009,19(7):35-37.(in Chinese)

附中文參考文獻：

[3] 林琛.Web環(huán)境下社會網(wǎng)絡挖掘研究[D]. 上海：復旦大學,2009.

[4] 段曉東,王存睿,劉向東,等. 基于粒子群算法的Web社區(qū)發(fā)現(xiàn)[J].計算機科學,2008,35(3):18-21.

[10] 馬帥,李佳,劉旭東,等.圖查詢:社會計算時代的新型搜索[J].中國計算機學會通訊,2012,8(11):26-33.

[11] 祝園園,秦璐,于旭.圖匹配問題的應用和研究[J].中國計算機學會通訊,2012,8(11):21-27.

[13] 崔玉泉,張麗,史開泉.粗糙集的動態(tài)特性研究[J].山東大學學報：理學版,2010,45(6):8-13.

[14] 何童,盧昌荊,史開泉.粗糙圖與它的結構[J].山東大學學報：理學版,2006,41(6):46-50.

[16] 周愛武，周閃閃，鄒武，等.一種基于變精度粗糙集理論的屬性約簡算法[J].計算機技術與發(fā)展，2009,19(7):35-37.

ZHANG Chun-ying,born in 1969,PhD,professor,CCF senior member(E200013476M)，her research interests include data mining, and social networks analysis.

郭景峰(1962-),男,黑龍江哈爾濱人，博士后,教授,CCF高級會員(E200005284S),研究方向為數(shù)據(jù)庫理論和數(shù)據(jù)挖掘。E-mail:jfguo@ysu.edu.cn

GUO Jing-feng,born in 1962,post doctor,professor,CCF senior member(E200005284S),his research interests include database theory, and data mining.

The rough attribute graph model of Web social network and its application

ZHANG Chun-ying1,2,GUO Jing-feng1
(1.College of Information Science and Engineering,Yanshan University,Qinhuangdao 066004;2.College of Science,Hebei United University,Tangshan 063009,China)

The paper targets the rough information feature of the social network in Web environment, which is that the Web data has a tremendous amount of junk content and garbage link and lots of information is incomplete, missed and repeatable. Firstly, based on the proposed the attribute graph model and combing the advantages of rough set theory solving incomplete information, the rough vertex attribute graph and the rough edges graph are proposed. Furthermore, the rough attribute graph that can describe the complex Web of incomplete social network information and the dynamic changes of links is given so that the Web social network structure is analyzed in an even better fashion. Secondly, the rough characteristics of the rough attributes graph is analyzed in order to give the concepts of rough vertex accuracy, rough edge accuracy, and rough graph accuracy and obtain the conclusion that the accuracy of rough attributes graph is related to the division level of vertex and edge set property. In other word, people's cognition of graph is closely related to the accuracy of graph. Finally, the paper authors are queried to get the rough graph in Chinese HowNet. By constantly adding the vertex attributes and dividing the graph vertex, the author's cooperation relations figure is excavated, thus demonstrating that the rough attribute graph in social network analysis is in line with the cognitive processes of people.

web social network;attributes graph;rough attribute graph;graph precision

2012-08-13;

2012-12-27

國家自然科學基金資助項目(61370168)；河北省自然基金資助項目(F2012209019)

1007-130X(2014)03-0517-07

TP391.3

A

10.3969/j.issn.1007-130X.2014.03.025

張春英(1969-),女,河北唐山人，博士，教授，CCF高級會員(E200013476M)，研究方向為數(shù)據(jù)挖掘和社會網(wǎng)絡分析。E-mail:zchunying@heuu.edu.cn

通信地址：063009 河北省唐山市新華西道46號河北聯(lián)合大學理學院

Address:College of Science,Hebei United University,46 Xinhua Avenue West,Tangshan 063009,Hebei,P.R.China