Web社会网络的粗糙属性图模型及应用

张春英,郭景峰

(1.燕山大学信息学院，河北 秦皇岛 066004;2.河北联合大学理学院，河北 唐山 063009)

Web社会网络的粗糙属性图模型及应用

张春英1,2,郭景峰1

(1.燕山大学信息学院，河北 秦皇岛 066004;2.河北联合大学理学院，河北 唐山 063009)

针对Web环境下的社会网络具有信息粗糙性的特征，即Web数据中有大量垃圾内容和垃圾链接，同时很多信息是不完整的、缺失的,且信息有重复现象存在等，在已提出的属性图模型基础上，结合粗糙集理论解决不完备信息的优势，首先提出粗糙顶点属性图和粗糙边属性图，进而给出粗糙属性图的概念，以对Web社会网络结构进行分析，使其能够描述复杂Web社会网络中的不完整信息以及动态变化的链接。其次对粗糙属性图的粗糙特性进行分析，给出粗糙顶点精度、粗糙边精度和粗糙图精度等概念，得出粗糙属性图的精度与顶点和边集属性划分程度有关的结论，即人们对图的认知程度与图的精度密切相关。最后，在中国知网上通过对论文作者进行查询得到粗糙图，并通过不断添加顶点属性，将图顶点划分得越来越精细，挖掘出要查询的作者合作关系图，从而说明粗糙属性图在社会网络分析中符合人们的认知过程。

Web社会网络；属性图；粗糙顶点属性图；粗糙属性图；图精度

1 引言

社会网络是以社会生活中人类或组织的行为活动为研究对象，将其抽象为相互作用的个体组成的网络。这样的网络无处不在，并且与我们的生活密切相关，如演员合作网络、科学家合作网络、恐怖分子网络、疾病传染网络以及虚拟社会网络等等。社会网络研究[1]是理解社会现象、预测人类行为、分析社会结构的重要工具。通过研究社会网络的结构和性质，可以帮助我们更深刻地理解社会现象，对现实中的决策、管理、优化问题都有极其重要的意义。

社会网络研究是以传统图论为工具进行的研究，将网络中的对象描述为结点，对象之间的关系用线表示[1,2]。图在社交网络中有着重要的应用，如近邻查询、图压缩、图匹配、图搜索等[3～6]。然而这种传统图只能描述结点与结点的关系，无法了解结点本身信息，也无从知晓更多关系信息，所以作者在传统图论的基础上，结合数据库中的属性依赖理论，提出属性图概念，以对Web社会网络结构进行分析[7,8]。属性图是考虑了结点和连接属性以及属性之间关系的图结构，是传统图的扩展；而在不考虑属性的情况下，属性图退化为传统图，所以传统图是属性图的特例。对属性图结构及其各种特性、操作的研究则是对传统图理论的补充和创新。

然而，Web环境下的社会网络具有信息粗糙性的特征，即Web数据中有大量垃圾内容和垃圾链接，同时很多信息是不完整的、缺失的[8～11]。如在微博上，用户在填写个人信息时，有的信息不填写，有的信息填写的是虚假信息；又如在论文网络中，有的作者未填写研究方向，有的作者单位信息发生了变化。而属性图在描述社会网络中的结点时则是在信息完整的假设下建立的，如何改进属性图，使其能够描述复杂Web社会网络中的不完整信息以及动态变化的链接是本文要解决的问题。为此在属性图基础上，融合粗糙集理论[12～16]，提出粗糙属性图，并研究其性质特征。粗糙属性图是对属性图的拓展，考虑了边和结点属性的粗糙性。

本文结构如下：

第2节对属性图基本概念进行描述；第3节提出粗糙属性图概念及相关定理；第4节分析了粗糙属性图的粗糙特性；第5节是一个应用实例；最后给出结论及下一步的研究方向。

2 属性图及其结构

定义2 在属性图GA=(V(VA,LV),E(EA,LE))中，VA={va1,va2,…，va|VA|} 为V上的属性集合，除了顶点标识属性外，能唯一区分一个顶点的属性称为顶点的关键属性。

定义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-粗糙属性图。

在两个属性图是否相等的问题上，粗糙属性图和传统意义上的属性图有一个重要的区别：传统意义上的属性图，必须两个属性图的顶点和边完全相等，且对应顶点和边具有相同属性，才认为两个属性图相等。两个在传统意义上不相等的属性图，在粗糙属性图中却可能是相等的，因为在粗糙属性图中，两个属性图是否相等是根据人们得到的知识判断的，当两个属性图的Ra-上、下近似属性图都相等时，由于知识的粗糙性，此时，认为两个属性图是相等的。

下面给出粗糙属性图相等的概念。

定义13 给定粗糙属性图集M、属性集R，则K=(M,R)是一个属性图知识系统，H、J⊆M。

4 粗糙属性图的粗糙特性

粗糙属性图的不确定性类似于粗糙集，是由其边界域的存在而引起的，边界域越大，其精确性越低。粗糙属性图的边界域包括顶点集边界域和边集边界域。为了更准确地表达粗糙属性图的精确性，引入粗糙属性图精度的概念。

这里,W⊆V≠Ø，|A|表示集合A的基数。

顶点精度αvRva(RA)用来反映人们对于粗糙属性图RA顶点集合W知识了解的完全程度。

这里,Y⊆E≠Ø，|A|表示集合A的基数。

边精度α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 应用实例

在论文合作网络中，作者重名现象很严重。如果按作者姓名查找某人的合作关系，是不能完全精确得到的，这时只能得到一个粗糙顶点关系图。另外，在合作网络中，作者与作者的关系除了具有论文合作关系外，实际上还会拥有师生关系、同事关系、朋友关系等。在无法确认其实际关系时，则作者之间的边也是粗糙的。由此得到的论文作者合作关系图即为粗糙图。

在本实例中，假设有某人要查看作者本人在中国知网上的论文合作关系情况，由于只知道本人的名字，其他信息暂不了解。所以，他在中国知网上按条件作者=“张春英”进行查询，共搜出842篇文献。如果不考虑第几作者都算是有合作关系的话，就有1 863个作者与“张春英”有过合作。根据这个合作关系可以构建以“张春英”为核心的一个关系图。很显然，这个图是不准确的，因为在查到的记录中，“张春英”这个顶点代表的是很多个作者的综合体，他们同属于在“张春英”这个属性下划分的同一个等价类，是无法区别的。同样，在与“张春英”合作过的作者中，再去查找他们的合作作者，这些作者也不是唯一的。如在合作作者中有“刘凤春”，但他仍然是一个综合体。由此可知，在只知道作者姓名时构建的论文合作网络是粗糙的、不精确的。每个顶点都是由多个潜在的实体构成，不能唯一地代表某个确定的作者。图1即为在中国知网中按照作者分别查询“张春英”、“刘凤春”、“刘保相”、“阎红灿”和“陈丽芳”的合作作者得到的合作关系图。

在图1中，每个作者构成的顶点都是由多个来自不同单位不同研究方向的作者(来自于288个单位)构成的，所以顶点是粗糙的。在此基础上，以“研究方向”划分等价类，共有“计算机”、“教育”、“化工”、“医学”、“生物”等类别。为了进一步缩小范围，经过分析得知，该作者可能是河北的，故选取单位为“河北*”的作者子集，此时找到65篇论文，分为“计算机”、“教育”、“医学”和“经济”四类。这样在找合作关系时，作者“张春英”这个顶点包含四类人物，每类人物与其他作者合作的论文数量分别是：32、6、21、6。而在所有“张春英”这个作者中，与其他作者在这四类中合作的论文数量分别是：44、37、308、41。继续按作者单位进行分类，可得到16个单位，如果认为同一单位的“张春英”只有1人，则在“张春英”这个顶点的下近似顶点中包含16个作者，而其上近似顶点中包含288个来自不同单位的作者，则该顶点的精度为16/288=0.05。若只选取“计算机”、“教育”、“医学”和“经济”这四个研究方向的作者，则有222个来自不同单位的作者，则该顶点的精度为16/222=0.07。这个精度仍然很低，为了进一步发掘作者信息，后来明确该作者的主要研究方向为“计算机”和“教育”且为河北的，则其上近似作者有5个，下近似作者有16个，则其精度为5/16=0.3。其合作作者来自不同单位不同行业，显然这有些不太合理。

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

再进一步考证该作者的单位，发现其来自于“河北联合大学理学院”，同时该单位原名称为“河北理工大学理学院”，故可精确挖掘到该作者，其上、下近似作者均为1个，则其精度达到100%。如此，该作者的真实合作关系网络才真正被挖掘出来，是通过逐步增加属性，去粗求精得出来的，如图2所示。

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

可在此基础上，进一步研究其主要合作作者如“刘保相”、“刘凤春”、“郭景峰”等与其他作者的合作关系图，从而挖掘其更大的关系社区，探究该作者可能拓展的合作关系。

另外需要说明的是，该实例只从顶点属性角度考虑了图的粗糙性，其实随着顶点划分不断细化，其边属性也逐渐明了，从而边的精度也在逐渐增强，整个图的精度也就越来越高。

6 结束语

考虑社会网络中顶点和链接属性的不完备性，将粗糙集理论引入到属性图中，用以描述Web社会网络中不完备、不确定的属性顶点和链接，从而解决社会网络中不确定信息的表示问题；给出了粗糙顶点属性图、粗糙边属性图以及粗糙属性图的定义，并给出了相关定理；进一步分析了粗糙属性图的粗糙特性，得出粗糙属性图的精度与顶点和边集属性划分程度有关，即划分越细，所得的图精度越高，人们对粗糙属性图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环境下社会网络挖掘研究[D]. 上海：复旦大学,2009.

[4] 段晓东,王存睿,刘向东,等. 基于粒子群算法的Web社区发现[J].计算机科学,2008,35(3):18-21.

[10] 马帅,李佳,刘旭东,等.图查询:社会计算时代的新型搜索[J].中国计算机学会通讯,2012,8(11):26-33.

[11] 祝园园,秦璐,于旭.图匹配问题的应用和研究[J].中国计算机学会通讯,2012,8(11):21-27.

[13] 崔玉泉,张丽,史开泉.粗糙集的动态特性研究[J].山东大学学报：理学版,2010,45(6):8-13.

[14] 何童,卢昌荆,史开泉.粗糙图与它的结构[J].山东大学学报：理学版,2006,41(6):46-50.

[16] 周爱武，周闪闪，邹武，等.一种基于变精度粗糙集理论的属性约简算法[J].计算机技术与发展，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),研究方向为数据库理论和数据挖掘。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)，研究方向为数据挖掘和社会网络分析。E-mail:zchunying@heuu.edu.cn

通信地址：063009 河北省唐山市新华西道46号河北联合大学理学院

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