基于親屬關(guān)系網(wǎng)絡(luò)的特定家庭結(jié)構(gòu)匹配方法研究

張　霞，郭瑞強(qiáng),2，高靜偉，王國強(qiáng)，薛少彤

(1. 河北師范大學(xué) 數(shù)學(xué)與信息科學(xué)學(xué)院 石家莊　050024；2. 河北省計(jì)算數(shù)學(xué)與應(yīng)用重點(diǎn)實(shí)驗(yàn)室（河北師范大學(xué)）石家莊　050024)

基于親屬關(guān)系網(wǎng)絡(luò)的特定家庭結(jié)構(gòu)匹配方法研究

張霞1，郭瑞強(qiáng)1,2，高靜偉1，王國強(qiáng)1，薛少彤1

(1. 河北師范大學(xué) 數(shù)學(xué)與信息科學(xué)學(xué)院 石家莊050024；2. 河北省計(jì)算數(shù)學(xué)與應(yīng)用重點(diǎn)實(shí)驗(yàn)室（河北師范大學(xué)）石家莊050024)

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

親屬關(guān)系網(wǎng)絡(luò)；圖數(shù)據(jù)庫；特定結(jié)構(gòu)；特定家庭結(jié)構(gòu)匹配

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

0　引言

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

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

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

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

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

1　基于圖數(shù)據(jù)庫構(gòu)建親屬關(guān)系網(wǎng)絡(luò)

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

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

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

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

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

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

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

2　限制圖模式匹配方法

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

圖2　子圖同構(gòu)算法舉例

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

圖3　子圖同構(gòu)算法舉例

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

圖4　限制模式圖匹配舉例

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

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

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

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

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

圖5　限制模式圖缺陷舉例

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

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

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

3　實(shí)驗(yàn)

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

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

圖6　子圖同構(gòu)實(shí)驗(yàn)結(jié)果舉例

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

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

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

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

實(shí)驗(yàn)4，采用改進(jìn)的限制圖模式匹配方法，查詢一個(gè)復(fù)雜而又特殊的家庭結(jié)構(gòu)，我們要查詢一個(gè)特殊的家庭。這個(gè)家庭是與一般三口之家在同一戶編號(hào)內(nèi)的殘缺家庭，正如下圖9-a所示，匹配結(jié)果如圖9-b中的R所示，其中，返回1個(gè)查詢結(jié)果集。

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

圖9　(b)改進(jìn)限制圖匹配查詢結(jié)果舉例

通過以上三個(gè)實(shí)驗(yàn)，我們可以得到兩個(gè)結(jié)論：

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

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

4　結(jié)語

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

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

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

[3] 李釗, 基于復(fù)雜網(wǎng)絡(luò)的復(fù)雜信息系統(tǒng)網(wǎng)絡(luò)脫皮結(jié)構(gòu)安全性研究. 北京. 北京郵電大學(xué). 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] 郭瑞強(qiáng), 閆紹惠, 趙書良, 申玉鳳. 親屬關(guān)系網(wǎng)絡(luò)的關(guān)系追溯算法. 計(jì)算機(jī)應(yī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] 劉丹軍, 趙書良, 趙嬌嬌, 郭曉波, 陳敏, 柳萌萌. 家譜關(guān)系的原圖表示. 計(jì)算機(jī)應(yīng)用. 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] 郭瑞強(qiáng), 周 萌, 魏連秋, 郭阿為, 閆紹惠. 親屬關(guān)系網(wǎng)絡(luò)統(tǒng)計(jì)特性研究. 計(jì)算機(jī)應(yī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] 張浩, 基于親屬關(guān)系網(wǎng)絡(luò)的圖匹配查詢方法研究. 河北師范大學(xué). 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

國家自然科學(xué)基金資助項(xiàng)目(61573127)；河北省教育廳自然科學(xué)研究項(xiàng)目(QN20131141)；校級(jí)研究生創(chuàng)新資助項(xiàng)目(xj2016038)。

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