基于亲属关系网络的特定家庭结构匹配方法研究

张　霞，郭瑞强,2，高静伟，王国强，薛少彤

(1. 河北师范大学 数学与信息科学学院 石家庄　050024；2. 河北省计算数学与应用重点实验室（河北师范大学）石家庄　050024)

基于亲属关系网络的特定家庭结构匹配方法研究

张霞1，郭瑞强1,2，高静伟1，王国强1，薛少彤1

(1. 河北师范大学 数学与信息科学学院 石家庄050024；2. 河北省计算数学与应用重点实验室（河北师范大学）石家庄050024)

随着数据规模的增大以及人与人之间关系复杂性的提高，在亲属关系网络中查询特定的家庭结构已经成为研究的难点之一。传统的关系型数据库并不擅长处理关系复杂、结构多变的数据。因此，本文基于图数据库构造了H省的亲属关系网络。针对亲属关系网络中数据庞大、结构复杂、难以批量匹配数据中的特定结构等问题，本文提出了基于亲属关系网络的特定家庭结构匹配方法。此外，本文还根据人口学中家庭结构的分类标准，对不同类型的家庭进行查询；实验结果表明，该方法简化了复杂数据的查询工作，提高了查询正确率，实现用户查询友好性提升。

亲属关系网络；图数据库；特定结构；特定家庭结构匹配

本文著录格式：张霞，郭瑞强，高静伟，等. 基于亲属关系网络的特定家庭结构匹配方法研究[J]. 软件，2016，37（9）：34-38

0　引言

自然界中，很多系统都可以用网络的形式加以描述。然而，以复杂网络[1]和大数据[2]为视角，对亲属关系网络的研究还是很少见。亲属关系网络是由人与人之间的基本亲属关系构成的拓扑结构，其中，亲属关系是由血缘关系、婚姻关系和抱养关系组成[3]。当今社会多元异构数据呈爆炸式增长，传统的关系型数据库[4]并不擅长处理关系复杂、结构多变的数据，图数据库[5]使用节点、边及其属性来描述和存储数据。理论上来讲，它可以完整的描述任何类型的数据及其之间的联系。

传统的亲属关系网络的展示方式，包括ore graph、P—graph、bipartite P—graph 三种形式[6]，此外，刘军丹提出的基于亲属数据的元图表示方法[7]。Charles Kemp和Terry Regier提出了跨语言的亲属关系分类反映了一般的准则[8]，并指出了任何一种复杂的亲属关系都可以表示成五种基本的亲属关系的传递闭包。亲属关系网络[9]是复杂网络在社会领域的实例化。

近年来，快速的回答用户的查询是大数据背景下研究的核心问题[10]，现阶段这个问题可以分为两类：匹配查询[11-12]和基于路径的可达性查询[13]。其中，匹配查询是通过分析节点和边的属性以及节点和边所形成的不同子结构，对数据图中的节点和边依次进行匹配，从而在数据图中找到与查询条件匹配的数据。基于路径的可达性查询是给定一个节点查找该节点到另一个节点之间是否存在路径。目前，针对亲属关系网络的研究主要有，闫绍惠提出的亲属关系网络关系追溯算法，该算法中提出半径搜索和定向搜索算法。该算法实现了特定人节点的社会关系搜索，但需要明确搜索的出发点，对于未明确出发节点的结构查询，搜索和批量查询方面难度较大。此外，传统的子图同构算法在批量匹配时，在描述搜索条件的模式图上，并不含有限制语义，因此，该算法并没有实现对特定类型的家庭结构的查询。

针对以上不足本文提出了基于亲属关系网络的特定家庭结构匹配的方法，并且对限制模式图[14]的定义进行了改进。

本文使用Neo4j[15]软件进行实验分析，Neo4j是一款高性能的No-SQL型图数据库，它可以将关系复杂、结构多变的数据以图的形式存储在网络上，可以分析过亿的节点、边和属性图。

1　基于图数据库构建亲属关系网络

本节构造亲属关系网络所需要的数据源于真实的人口，亲属关系网络的图模式存储是将现实世界中的人对应于亲属关系网络中的节点，人与人之间的基本亲属关系对应于亲属关系网络中的边。本文抽取H省某市的亲属数据，构造了包含1260万人节点和近1490万条边的亲属关系网络。

定义1基本亲属关系类型集（Rmb）。基本亲属关系表示婚姻关系与亲子关系的并集。即（Rmb）=其中Rm表示婚姻关系，Rb表示亲子关系。婚姻关系表示人与人之间由婚姻产生的婚配关系集合，Rm={CC}，其中CC是couple-couple的简称，表示的是人与人之间的婚姻关系。亲子关系表示人与人由生育和抱养产生的生育关系集和抱养关系集，Rb={FS，MS，FD，MD}其中FS代表Father-Son的简称，表示人与人之间的父子关系，其中MS代表了Mother-Son的简称，表示人与人之间的母子关系，其中FD代表Father-Daughter的简称，表示人与人之间的父女关系，其中MD代表Mother-Daughter的简称，表示人与人之间的母女关系。

定义2人节点集合（Vp）。将每个人作为节点，（Vp）表示所有人节点构成的节点集，Vp={所有人}。

定义3亲属关系网络（Gk）。亲属关系网络是一个由人员节点和人与人之间的亲属关系构成的有向图，即Gk=（Vp，E，L），其中，Vp表示亲属关系网络中的节点集合，E表示亲属关系网络中的边集合，对于任意一条关系边由有序节点对（Vpi，Vpj）构成，其中Vpi，Vpj∈Vp。L表示属性映射函数，将人节点和关系边的属性映射到相应的属性上。

完成某地区的亲属数据的抽取后，对数据进行预处理，形成了如图1所示的亲属关系网络。图1展示的是以图模型为基础来描述和存储亲属关系网络中的一个三口之家，其中，人节点的标签为person，节点101，102为双亲，103为101，102的孩子。图中的每个节点都抽取了name, sex, IDCard等属性，三个节点的变量名分别为101, 102, 103。

图1　图模式存储亲属数据举例

随着互联网计算的发展，数据之间呈现联系紧密的特征，数据规模不断提高，数据的更新速度迅速提升，导致关系模型难以满足现实需求，图模型的出现弥补了关系模型的某些不足。

2　限制图模式匹配方法

一般三口之家在人口学上是指一户家庭中只有三人，双亲只养育一个孩子。为了说明问题，将上述条件具体化，将一般三口之家的孩子定为男性。图2中P1描述的是传统子图同构算法的模式图，表达的是查询条件。图2中的G描述的是被查询的数据对象。

图2　子图同构算法举例

在数据图G中满足查询条件P1的结果集是R1,如图3所示，其中，有两个满足条件的连通子结构。很明显子图同构算法是将一个大连通图拆成两个满足搜索条件的子结构。然而，这是将一个不满足条件的大连通结构拆分成满足条件的两个子分量。本质上并没有实现特定结构的匹配，即在一般三口之家的查询中返回了错误的结果集。

图3　子图同构算法举例

针对上述问题，本文提出了限制模式图匹配方法。将限制语义加到模式图上，在以上实例中体现为：限制查找的家庭结构中孩子节点的个数为1，即Num(child)=1，本文将限制模式图表示为图4所示的P2。

图4　限制模式图匹配举例

在相同的数据图G中利用限制模式图匹配的方法对P2进行查询，查询的结果集为NULL。综上所述，本文提出的限制模式图匹配方法，具体定义如下：

定义4数据图：数据图G=(V,E,L)是一个三元组，其中V代表节点集，E代表边集，L代表节点和边分别对应的属性对照映射函数。

定义5限制模式图：限制模式图P=(VY,VN, EY,EN,L)，其中VY代表匹配节点集合，VN代表节点集合，EY代表匹配边集合，EN代表限制边集合，L代表节点和边各自的属性映射函数，L可以存放限制所有节点和边数目的属性。

定义6限制模式图匹配：已知一个数据图G=(V,E,L)和一个限制模式图P=(VY,VN,EY,EN,L),限制子图匹配问题要求在限制模式图P和数据子图Gsub=(Vsub,Esub,Lsub)，(Gsub⊆G)满足一个双射函数

然而该方法要求，在匹配过程中，满足搜索条件的节点集为YV，满足限制条件的节点集为NV，满足搜索条件的边集为YE，满足限制条件的边集为NE，这个方法可以准确的描述出一部分特定结构的数据，但无法描述如图5所示的连通子结构。

图5　限制模式图缺陷举例

这是限制图模式匹配的缺陷，所以本文对这一方法中的模式图的定义进行了改进。

定义7改进的限制模式图：改进的限制模式图Q=(VQ,EQ,fv,fe,fp,VC,EC,Qλ)。其中，VQ是一个有限节点集；EQ是亲属关系网络中的有向的边的集合；fv(.)在模式图的节点集VQ上指定的搜索条件。fe(.)定义在模式图EQ上的形如 r1 operator r2的搜索条件。fp定义了模式图Q上指定的搜索节点u和u’之间的路径的长度。Qλ是限制模式图深度的阈值；VC限制模式图中最少节点数。EC限制模式图中的最少边数。改进的限制模式图匹配的匹配规则如下：

Qλ是模式图深度的限定阈值。例如：Qλ≥3代表我们所搜索的网络的深度不小于3；

3　实验

本文采用Neo4j数据库和 Cypher 查询语言，基于村一级亲属关系网络，该地区的亲属数据包含了 3092 个人节点，11838 条边，本文基于该地区的人口数据分别对一般三口之家、核心三口之家展开了查询对比实验，从而对限制模式图匹配的方法进行实验分析，以展示限制模式图匹配方法的正确性与有效性。

实验1，利用子图同构的方法，查询一般三口之家。图6中的p1所示，为一般三口之家的查询模式图。然而，子图同构中不包含限制语义的查询，实验得到了615个匹配结果，如图5中的Result1所示，其中，子图同构算法将数据图中的一个五口之家当作3个三口之家返回。所以，返回了错误的查询结果。

图6　子图同构实验结果举例

实验2，根据上述实验的不足，在传统的模式图上添加限制语义，来查询一般的三口之家。将模式图所描述的搜索条件表述为查找孩子节点数为1的家庭，即Num(child)=1，如图7中的P2所示。这样就排除了有两个及两个以上孩子个数的家庭，匹配结果如图7的Result2所示，其中，返回查询结果数目为24。由此发现，与子图同构的查询结果不同，限制图匹配的查询结果比子图同构的查询结果少了591个家庭。

图7　限制孩子节点数为1

实验3，在一般三口之家的基础上继续添加语义限制，即，不仅限制了孩子节点的数目是1，而且限制该类家庭的一个孩子是未婚。根据人口学上的定义，我们将这一类家庭称为标准核心三口之家。将查询标准核心三口之家的问题转化为一般的查询条件，即在上述实验中的一般三口家庭的基础上添加该类家庭的唯一孩子是未婚的限制条件，如图8中的P3所示。实验发现，仅有22条查询结果。如图8的Result3所示。

图8　限制孩子节点个数为1且未婚

实验4，采用改进的限制图模式匹配方法，查询一个复杂而又特殊的家庭结构，我们要查询一个特殊的家庭。这个家庭是与一般三口之家在同一户编号内的残缺家庭，正如下图9-a所示，匹配结果如图9-b中的R所示，其中，返回1个查询结果集。

图9　(a)改进限制图匹配的模式图举例

图9　(b)改进限制图匹配查询结果举例

通过以上三个实验，我们可以得到两个结论：

第一，限制语义的有效性。通过实验1和实验2的结果，可以明显的看出，限制条件可以弥补子图同构算法在语义上的缺陷，灵活的使用基于限制语义的图匹配方法，可以完成对特定结构的网络数据的查询以满足现实需求。又由实验4可得，改进后的限制模式图匹配方法描述的查询模式图突破了原本限制模式图的描述范围有限的缺陷，它不仅可以描述满足搜索条件的YV,YE以及满足限制条件的还可以描述任一特定结构的连通子图。

第二，限制语义的正确性。通过实验2，3的对比，可以发现实验2的结果集有24个，实验3的结果集有22个并且这两个结果集是包含关系，实验2中的24个结果集可以分成实验3的22个结果集和剩余2个结果组成的集合。观察数据可知，这两个集合是不相交的，由此可得，实验2和3的查询结果在逻辑上是一致的，这就反映了限制语义查询的正确性。

4　结语

本文以H省全员人口数据为基础，以图结构为模型对亲属数据构造亲属关系网络。针对亲属关系网络中特定家庭结构查询的问题结合实际需求，提出了限制图模式匹配的方法。实验发现限制图模式匹配方法中的限制模式图的定义不能描述一些本文提出的图模式匹配方法不仅可以达到个性化匹配，实现用户友好性查询，而且简化了家庭结构的查询，提高了查询正确率，为亲属数据的研究提供了新的方法。

[1] 乔少杰, 郭俊, 韩楠, 张小松, 元吕安, 唐常杰. 大规模复杂网络社区并行发现算法. 计算机学报. 2015.38

[2] 王元卓, 靳小龙, 程学旗. 网络大数据的现代与展望. 计算机学报. 2016. 06. 1126-1138.

[3] 李钊, 基于复杂网络的复杂信息系统网络脱皮结构安全性研究. 北京. 北京邮电大学. 2014

[4] Wenfei Fan, Jin-Peng Huai.Querying Big Data: Bridging Theory and Practice. JOURNAL OF COMPUTER SCIENCE AND TECH-NOLOGY 29(5): 849-869 Sept. 2014.

[5] 郭瑞强, 闫绍惠, 赵书良, 申玉凤. 亲属关系网络的关系追溯算法. 计算机应用. 2014. 34. 1988-1991.

[6] BATAGELJ V, MRVAR A． Analysis of kinship relations with Pajek[J]. Social Science Computer Review, 2007, 26(2): 224-246．

[7] Warchał Ł. Using Neo4j graph database in social network analysis[J]. Studia Informatica, 2012, 33(2A): 271-279.

[8] Batagelj V Mrvar A. Analysis of kinship relations with Pajek[J]. Social Science Computer Review, 2008, 26(2): 224-246．

[9] 刘丹军, 赵书良, 赵娇娇, 郭晓波, 陈敏, 柳萌萌. 家谱关系的原图表示. 计算机应用. 2013. 33(7): 2037-2040.

[10] Charles Kemp, Terry Regier.Kinship Categories Across Languages Reflect General Communicative Principles. SCIENCE VOL 336. 2012. 1049-1055.

[11] 郭瑞强, 周 萌, 魏连秋, 郭阿为, 闫绍惠. 亲属关系网络统计特性研究. 计算机应用与软件. 2015. 32. 84-89.

[12] Wenfei Fan. Floris Geerts. Leonid Libkin.On Scale Independence for Querying Big Data PODS’14, June 22-27, 2014, Snowbird, UT, USA. VLDB Endowment, Vol. 7, No. 7.

[13] Wenfei Fan. Graph Pattern Matching Revised for Social Network Analysis.wenfei.fan ICDT 2012, March 26-30, 2012, Berlin, Germany.

[14] Shuai Ma, Yang Cao, WenFei Fan, JinPeng Huai, Tianyu Wo.Capturing Topology in graph pattern matching. VLDB Endowment, Vol. 5, No. 4. 310-321.

[15] Ruoming Jin, Hui Hong, HaiXun Wang, Ning Ruan, Yang Xiang. Computing Label Constraint Reachability in Graph Databases. SIGMOD. June 6-11, 2010. USA.

[16] Miller J J. Graph database applications and concepts with Neo4j[C]. Proceedings of the Southern Association for Information Systems Conference, Atlanta, GA, USA. 2013- 2324.

[17] 张浩, 基于亲属关系网络的图匹配查询方法研究. 河北师范大学. 2016.

The Research on the Method of Specific Family Structure Matching Based on the Kinship Network

ZHANG Xia1, GUO Rui-qiang1,2, GAO Jing-wei1, WANG Guo-qiang1, XUE Shao-tong1
(1. Hebei Normal University, Shijiazhuang Hebei 050024, China; 2. Key Laboratory of Computational Mathematics and application (Hebei Normal University), Hebei Province, Shijiazhuang 050024)

With the increase of the data scale and the complexity of the relationship between people and people gradually enhanced, Searching for a specific structure has become one the most difficult problems in the kinship network.traditional relational databases are not good at dealing with such data, which their relationships is complicated and structure is changeable. therefore, we construct the kinship network of H province based on the graph database. Due to there are some problems in the kinship network, such as large amount of data, complex structure and it is difficult to batch matching the specific structure and so on, so in this paper, we put forward the specific family sturcture matching method based on the kinship network. According to the classification criteria of family structure in the larithmics, query the different types of family structure. Our experiment shows that this method can simplify the query of the large scale complex data, improve the accuracy of the query in kinship network, realize the promotion of user friendliness on query.

Kinship network; Graph database; Specific structure; Specific family structure matching

TP3

A

10.3969/j.issn.1003-6970.2016.09.008

国家自然科学基金资助项目(61573127)；河北省教育厅自然科学研究项目(QN20131141)；校级研究生创新资助项目(xj2016038)。

通讯联系人: 郭瑞强。