張　霞，郭瑞強,2，高靜偉，王國強，薛少彤

(1. 河北師范大學 數(shù)學與信息科學學院 石家莊　050024；2. 河北省計算數(shù)學與應用重點實驗室（河北師范大學）石家莊　050024)

基于親屬關系網(wǎng)絡的特定家庭結構匹配方法研究

張霞1，郭瑞強1,2，高靜偉1，王國強1，薛少彤1

(1. 河北師范大學 數(shù)學與信息科學學院 石家莊050024；2. 河北省計算數(shù)學與應用重點實驗室（河北師范大學）石家莊050024)

隨著數(shù)據(jù)規(guī)模的增大以及人與人之間關系復雜性的提高，在親屬關系網(wǎng)絡中查詢特定的家庭結構已經(jīng)成為研究的難點之一。傳統(tǒng)的關系型數(shù)據(jù)庫并不擅長處理關系復雜、結構多變的數(shù)據(jù)。因此，本文基于圖數(shù)據(jù)庫構造了H省的親屬關系網(wǎng)絡。針對親屬關系網(wǎng)絡中數(shù)據(jù)龐大、結構復雜、難以批量匹配數(shù)據(jù)中的特定結構等問題，本文提出了基于親屬關系網(wǎng)絡的特定家庭結構匹配方法。此外，本文還根據(jù)人口學中家庭結構的分類標準，對不同類型的家庭進行查詢；實驗結果表明，該方法簡化了復雜數(shù)據(jù)的查詢工作，提高了查詢正確率，實現(xiàn)用戶查詢友好性提升。

親屬關系網(wǎng)絡；圖數(shù)據(jù)庫；特定結構；特定家庭結構匹配

本文著錄格式：張霞，郭瑞強，高靜偉，等. 基于親屬關系網(wǎng)絡的特定家庭結構匹配方法研究[J]. 軟件，2016，37（9）：34-38

0　引言

自然界中，很多系統(tǒng)都可以用網(wǎng)絡的形式加以描述。然而，以復雜網(wǎng)絡[1]和大數(shù)據(jù)[2]為視角，對親屬關系網(wǎng)絡的研究還是很少見。親屬關系網(wǎng)絡是由人與人之間的基本親屬關系構成的拓撲結構，其中，親屬關系是由血緣關系、婚姻關系和抱養(yǎng)關系組成[3]。當今社會多元異構數(shù)據(jù)呈爆炸式增長，傳統(tǒng)的關系型數(shù)據(jù)庫[4]并不擅長處理關系復雜、結構多變的數(shù)據(jù)，圖數(shù)據(jù)庫[5]使用節(jié)點、邊及其屬性來描述和存儲數(shù)據(jù)。理論上來講，它可以完整的描述任何類型的數(shù)據(jù)及其之間的聯(lián)系。

傳統(tǒng)的親屬關系網(wǎng)絡的展示方式，包括ore graph、P—graph、bipartite P—graph 三種形式[6]，此外，劉軍丹提出的基于親屬數(shù)據(jù)的元圖表示方法[7]。Charles Kemp和Terry Regier提出了跨語言的親屬關系分類反映了一般的準則[8]，并指出了任何一種復雜的親屬關系都可以表示成五種基本的親屬關系的傳遞閉包。親屬關系網(wǎng)絡[9]是復雜網(wǎng)絡在社會領域的實例化。

近年來，快速的回答用戶的查詢是大數(shù)據(jù)背景下研究的核心問題[10]，現(xiàn)階段這個問題可以分為兩類：匹配查詢[11-12]和基于路徑的可達性查詢[13]。其中，匹配查詢是通過分析節(jié)點和邊的屬性以及節(jié)點和邊所形成的不同子結構，對數(shù)據(jù)圖中的節(jié)點和邊依次進行匹配，從而在數(shù)據(jù)圖中找到與查詢條件匹配的數(shù)據(jù)。基于路徑的可達性查詢是給定一個節(jié)點查找該節(jié)點到另一個節(jié)點之間是否存在路徑。目前，針對親屬關系網(wǎng)絡的研究主要有，閆紹惠提出的親屬關系網(wǎng)絡關系追溯算法，該算法中提出半徑搜索和定向搜索算法。該算法實現(xiàn)了特定人節(jié)點的社會關系搜索，但需要明確搜索的出發(fā)點，對于未明確出發(fā)節(jié)點的結構查詢，搜索和批量查詢方面難度較大。此外，傳統(tǒng)的子圖同構算法在批量匹配時，在描述搜索條件的模式圖上，并不含有限制語義，因此，該算法并沒有實現(xiàn)對特定類型的家庭結構的查詢。

針對以上不足本文提出了基于親屬關系網(wǎng)絡的特定家庭結構匹配的方法，并且對限制模式圖[14]的定義進行了改進。

本文使用Neo4j[15]軟件進行實驗分析，Neo4j是一款高性能的No-SQL型圖數(shù)據(jù)庫，它可以將關系復雜、結構多變的數(shù)據(jù)以圖的形式存儲在網(wǎng)絡上，可以分析過億的節(jié)點、邊和屬性圖。

1　基于圖數(shù)據(jù)庫構建親屬關系網(wǎng)絡

本節(jié)構造親屬關系網(wǎng)絡所需要的數(shù)據(jù)源于真實的人口，親屬關系網(wǎng)絡的圖模式存儲是將現(xiàn)實世界中的人對應于親屬關系網(wǎng)絡中的節(jié)點，人與人之間的基本親屬關系對應于親屬關系網(wǎng)絡中的邊。本文抽取H省某市的親屬數(shù)據(jù)，構造了包含1260萬人節(jié)點和近1490萬條邊的親屬關系網(wǎng)絡。

定義1基本親屬關系類型集（Rmb）?；居H屬關系表示婚姻關系與親子關系的并集。即（Rmb）=其中Rm表示婚姻關系，Rb表示親子關系。婚姻關系表示人與人之間由婚姻產(chǎn)生的婚配關系集合，Rm={CC}，其中CC是couple-couple的簡稱，表示的是人與人之間的婚姻關系。親子關系表示人與人由生育和抱養(yǎng)產(chǎn)生的生育關系集和抱養(yǎng)關系集，Rb={FS，MS，F(xiàn)D，MD}其中FS代表Father-Son的簡稱，表示人與人之間的父子關系，其中MS代表了Mother-Son的簡稱，表示人與人之間的母子關系，其中FD代表Father-Daughter的簡稱，表示人與人之間的父女關系，其中MD代表Mother-Daughter的簡稱，表示人與人之間的母女關系。

定義2人節(jié)點集合（Vp）。將每個人作為節(jié)點，（Vp）表示所有人節(jié)點構成的節(jié)點集，Vp={所有人}。

定義3親屬關系網(wǎng)絡（Gk）。親屬關系網(wǎng)絡是一個由人員節(jié)點和人與人之間的親屬關系構成的有向圖，即Gk=（Vp，E，L），其中，Vp表示親屬關系網(wǎng)絡中的節(jié)點集合，E表示親屬關系網(wǎng)絡中的邊集合，對于任意一條關系邊由有序節(jié)點對（Vpi，Vpj）構成，其中Vpi，Vpj∈Vp。L表示屬性映射函數(shù)，將人節(jié)點和關系邊的屬性映射到相應的屬性上。

完成某地區(qū)的親屬數(shù)據(jù)的抽取后，對數(shù)據(jù)進行預處理，形成了如圖1所示的親屬關系網(wǎng)絡。圖1展示的是以圖模型為基礎來描述和存儲親屬關系網(wǎng)絡中的一個三口之家，其中，人節(jié)點的標簽為person，節(jié)點101，102為雙親，103為101，102的孩子。圖中的每個節(jié)點都抽取了name, sex, IDCard等屬性，三個節(jié)點的變量名分別為101, 102, 103。

圖1　圖模式存儲親屬數(shù)據(jù)舉例

隨著互聯(lián)網(wǎng)計算的發(fā)展，數(shù)據(jù)之間呈現(xiàn)聯(lián)系緊密的特征，數(shù)據(jù)規(guī)模不斷提高，數(shù)據(jù)的更新速度迅速提升，導致關系模型難以滿足現(xiàn)實需求，圖模型的出現(xiàn)彌補了關系模型的某些不足。

2　限制圖模式匹配方法

一般三口之家在人口學上是指一戶家庭中只有三人，雙親只養(yǎng)育一個孩子。為了說明問題，將上述條件具體化，將一般三口之家的孩子定為男性。圖2中P1描述的是傳統(tǒng)子圖同構算法的模式圖，表達的是查詢條件。圖2中的G描述的是被查詢的數(shù)據(jù)對象。

圖2　子圖同構算法舉例

在數(shù)據(jù)圖G中滿足查詢條件P1的結果集是R1,如圖3所示，其中，有兩個滿足條件的連通子結構。很明顯子圖同構算法是將一個大連通圖拆成兩個滿足搜索條件的子結構。然而，這是將一個不滿足條件的大連通結構拆分成滿足條件的兩個子分量。本質上并沒有實現(xiàn)特定結構的匹配，即在一般三口之家的查詢中返回了錯誤的結果集。

圖3　子圖同構算法舉例

針對上述問題，本文提出了限制模式圖匹配方法。將限制語義加到模式圖上，在以上實例中體現(xiàn)為：限制查找的家庭結構中孩子節(jié)點的個數(shù)為1，即Num(child)=1，本文將限制模式圖表示為圖4所示的P2。

圖4　限制模式圖匹配舉例

在相同的數(shù)據(jù)圖G中利用限制模式圖匹配的方法對P2進行查詢，查詢的結果集為NULL。綜上所述，本文提出的限制模式圖匹配方法，具體定義如下：

定義4數(shù)據(jù)圖：數(shù)據(jù)圖G=(V,E,L)是一個三元組，其中V代表節(jié)點集，E代表邊集，L代表節(jié)點和邊分別對應的屬性對照映射函數(shù)。

定義5限制模式圖：限制模式圖P=(VY,VN, EY,EN,L)，其中VY代表匹配節(jié)點集合，VN代表節(jié)點集合，EY代表匹配邊集合，EN代表限制邊集合，L代表節(jié)點和邊各自的屬性映射函數(shù)，L可以存放限制所有節(jié)點和邊數(shù)目的屬性。

定義6限制模式圖匹配：已知一個數(shù)據(jù)圖G=(V,E,L)和一個限制模式圖P=(VY,VN,EY,EN,L),限制子圖匹配問題要求在限制模式圖P和數(shù)據(jù)子圖Gsub=(Vsub,Esub,Lsub)，(Gsub?G)滿足一個雙射函數(shù)

然而該方法要求，在匹配過程中，滿足搜索條件的節(jié)點集為YV，滿足限制條件的節(jié)點集為NV，滿足搜索條件的邊集為YE，滿足限制條件的邊集為NE，這個方法可以準確的描述出一部分特定結構的數(shù)據(jù)，但無法描述如圖5所示的連通子結構。

圖5　限制模式圖缺陷舉例

這是限制圖模式匹配的缺陷，所以本文對這一方法中的模式圖的定義進行了改進。

定義7改進的限制模式圖：改進的限制模式圖Q=(VQ,EQ,fv,fe,fp,VC,EC,Qλ)。其中，VQ是一個有限節(jié)點集；EQ是親屬關系網(wǎng)絡中的有向的邊的集合；fv(.)在模式圖的節(jié)點集VQ上指定的搜索條件。fe(.)定義在模式圖EQ上的形如 r1 operator r2的搜索條件。fp定義了模式圖Q上指定的搜索節(jié)點u和u’之間的路徑的長度。Qλ是限制模式圖深度的閾值；VC限制模式圖中最少節(jié)點數(shù)。EC限制模式圖中的最少邊數(shù)。改進的限制模式圖匹配的匹配規(guī)則如下：

Qλ是模式圖深度的限定閾值。例如：Qλ≥3代表我們所搜索的網(wǎng)絡的深度不小于3；

3　實驗

本文采用Neo4j數(shù)據(jù)庫和 Cypher 查詢語言，基于村一級親屬關系網(wǎng)絡，該地區(qū)的親屬數(shù)據(jù)包含了 3092 個人節(jié)點，11838 條邊，本文基于該地區(qū)的人口數(shù)據(jù)分別對一般三口之家、核心三口之家展開了查詢對比實驗，從而對限制模式圖匹配的方法進行實驗分析，以展示限制模式圖匹配方法的正確性與有效性。

實驗1，利用子圖同構的方法，查詢一般三口之家。圖6中的p1所示，為一般三口之家的查詢模式圖。然而，子圖同構中不包含限制語義的查詢，實驗得到了615個匹配結果，如圖5中的Result1所示，其中，子圖同構算法將數(shù)據(jù)圖中的一個五口之家當作3個三口之家返回。所以，返回了錯誤的查詢結果。

圖6　子圖同構實驗結果舉例

實驗2，根據(jù)上述實驗的不足，在傳統(tǒng)的模式圖上添加限制語義，來查詢一般的三口之家。將模式圖所描述的搜索條件表述為查找孩子節(jié)點數(shù)為1的家庭，即Num(child)=1，如圖7中的P2所示。這樣就排除了有兩個及兩個以上孩子個數(shù)的家庭，匹配結果如圖7的Result2所示，其中，返回查詢結果數(shù)目為24。由此發(fā)現(xiàn)，與子圖同構的查詢結果不同，限制圖匹配的查詢結果比子圖同構的查詢結果少了591個家庭。

圖7　限制孩子節(jié)點數(shù)為1

實驗3，在一般三口之家的基礎上繼續(xù)添加語義限制，即，不僅限制了孩子節(jié)點的數(shù)目是1，而且限制該類家庭的一個孩子是未婚。根據(jù)人口學上的定義，我們將這一類家庭稱為標準核心三口之家。將查詢標準核心三口之家的問題轉化為一般的查詢條件，即在上述實驗中的一般三口家庭的基礎上添加該類家庭的唯一孩子是未婚的限制條件，如圖8中的P3所示。實驗發(fā)現(xiàn)，僅有22條查詢結果。如圖8的Result3所示。

圖8　限制孩子節(jié)點個數(shù)為1且未婚

實驗4，采用改進的限制圖模式匹配方法，查詢一個復雜而又特殊的家庭結構，我們要查詢一個特殊的家庭。這個家庭是與一般三口之家在同一戶編號內的殘缺家庭，正如下圖9-a所示，匹配結果如圖9-b中的R所示，其中，返回1個查詢結果集。

圖9　(a)改進限制圖匹配的模式圖舉例

圖9　(b)改進限制圖匹配查詢結果舉例

通過以上三個實驗，我們可以得到兩個結論：

第一，限制語義的有效性。通過實驗1和實驗2的結果，可以明顯的看出，限制條件可以彌補子圖同構算法在語義上的缺陷，靈活的使用基于限制語義的圖匹配方法，可以完成對特定結構的網(wǎng)絡數(shù)據(jù)的查詢以滿足現(xiàn)實需求。又由實驗4可得，改進后的限制模式圖匹配方法描述的查詢模式圖突破了原本限制模式圖的描述范圍有限的缺陷，它不僅可以描述滿足搜索條件的YV,YE以及滿足限制條件的還可以描述任一特定結構的連通子圖。

第二，限制語義的正確性。通過實驗2，3的對比，可以發(fā)現(xiàn)實驗2的結果集有24個，實驗3的結果集有22個并且這兩個結果集是包含關系，實驗2中的24個結果集可以分成實驗3的22個結果集和剩余2個結果組成的集合。觀察數(shù)據(jù)可知，這兩個集合是不相交的，由此可得，實驗2和3的查詢結果在邏輯上是一致的，這就反映了限制語義查詢的正確性。

4　結語

本文以H省全員人口數(shù)據(jù)為基礎，以圖結構為模型對親屬數(shù)據(jù)構造親屬關系網(wǎng)絡。針對親屬關系網(wǎng)絡中特定家庭結構查詢的問題結合實際需求，提出了限制圖模式匹配的方法。實驗發(fā)現(xiàn)限制圖模式匹配方法中的限制模式圖的定義不能描述一些本文提出的圖模式匹配方法不僅可以達到個性化匹配，實現(xiàn)用戶友好性查詢，而且簡化了家庭結構的查詢，提高了查詢正確率，為親屬數(shù)據(jù)的研究提供了新的方法。

[1] 喬少杰, 郭俊, 韓楠, 張小松, 元呂安, 唐常杰. 大規(guī)模復雜網(wǎng)絡社區(qū)并行發(fā)現(xiàn)算法. 計算機學報. 2015.38

[2] 王元卓, 靳小龍, 程學旗. 網(wǎng)絡大數(shù)據(jù)的現(xiàn)代與展望. 計算機學報. 2016. 06. 1126-1138.

[3] 李釗, 基于復雜網(wǎng)絡的復雜信息系統(tǒng)網(wǎng)絡脫皮結構安全性研究. 北京. 北京郵電大學. 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] 郭瑞強, 閆紹惠, 趙書良, 申玉鳳. 親屬關系網(wǎng)絡的關系追溯算法. 計算機應用. 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] 郭瑞強, 周 萌, 魏連秋, 郭阿為, 閆紹惠. 親屬關系網(wǎng)絡統(tǒng)計特性研究. 計算機應用與軟件. 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] 張浩, 基于親屬關系網(wǎng)絡的圖匹配查詢方法研究. 河北師范大學. 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)；校級研究生創(chuàng)新資助項目(xj2016038)。

通訊聯(lián)系人: 郭瑞強。