亲属关系网络的关系追溯算法
|
摘要
人与人之间通过婚姻关系和亲子关系构成了亲属关系网络。针对亲属关系网络庞大、难以追溯等问题,结合广度优先搜索策略,提出了两种亲属关系追溯算法:半径搜索和定向搜索。依托河北省全员人口数据库,将数据范围扩展到复杂网络的层次,以市级亲属关系数据为例构建亲属关系网络,包含约415万个节点,约1088万条边。采用双向亲属关系存储,避免了亲属关系回溯查询等问题。实验结果表明关系追溯算法能够准确定位特定关系亲属,同时具有较高的执行效率和较好的灵活性。
Kinship network is made up of marriage and parent-child relationship. Searching a special relationship on a huge kinship network is very difficult. This paper proposed two algorithms by extending breadth-first-search method: radiussearch and directional-search. The data of the kinship network was extracted from Hebei province population database, which included about 4 150 000 vertexes, and about 10 880 000 edges. The network stored bilateral relationships, which declined some unnecessary back tracking. The experimental results show that the kinship retrospect algorithm can exactly locate some specific persons by the network. At the same time the algorithms can achieve high performance and guarantee high flexibility.
Kinship network is made up of marriage and parent-child relationship. Searching a special relationship on a huge kinship network is very difficult. This paper proposed two algorithms by extending breadth-first-search method: radiussearch and directional-search. The data of the kinship network was extracted from Hebei province population database, which included about 4 150 000 vertexes, and about 10 880 000 edges. The network stored bilateral relationships, which declined some unnecessary back tracking. The experimental results show that the kinship retrospect algorithm can exactly locate some specific persons by the network. At the same time the algorithms can achieve high performance and guarantee high flexibility.
引文
[1]BERNERS-LEE T,HALL W,HENDLER J,et al.Creating a science of the Web[J].Science,2006,313(5788):769-711.
[2]WANG J W,RONG L L.Cascade-based attack vulnerability on the US power grid[J].Safety Science,2009,47(10):1332-1336.
[3]OROSZ G,WILSON R E,STEPAN G.Traffic jams:dynamics and control[J].Philosophical Transactions of the Royal Society,2010,368(1928):4455-4479.
[4]BULDYREV S V,PARSHANI R,PAUL G,et al.Catastrophic cascade of failures in interdependent networks[J].Nature,2010,464(7291):1025-1028.
[5]BATAGELJ V,MRVAR A.Analysis of kinship relations with Pajek[J].Social Science Computer Review,2007,26(2):224-246.
[6]HAMBERGER K,HOUSEMAN M,DOUGLAS R W.Kinship network analysis[EB/OL].[2013-10-10].http://eclectic.ss.uci.edu/~drwhite/Feb20115605-Scott-Chap35.pdf.
[7]HAMBERGER K.Matrimonial circuits in kinship networks:Calculation,enumeration and census[J].Social Networks,2011,33(2):113-128.
[8]WHITE D R,HOUSEMAN M.A reticular approach to kinship[C/OL].[2013-10-10].http://intersci.ss.uci.edu/wiki/pdf/The_reticular_approach_to_kinship2a.pdf.
[9]HAMBERGER K.Matrimonial circuits in kinship networks:Calculation,enumeration and census[J].Social Networks,2011,33(2):113-128.
[10]CHEN Y L,LU J T.Mining inheritance rules from genealogical data[C]//Advances in Web-Age Information Management,LNCS3192.Berlin:Springer,2004:569-578.
[11]PRIGNANO L,SERVA M.Genealogical trees from genetic distances[J].European Physical Journal B,2009,69(3):455-463.
[12]BATAGELJ V,MRVAR A.Pajek-program for large network analysis[EB/OL].[2013-10-10].http://Pajek.imfm.si/doku.php?id=Pajek.
[2]WANG J W,RONG L L.Cascade-based attack vulnerability on the US power grid[J].Safety Science,2009,47(10):1332-1336.
[3]OROSZ G,WILSON R E,STEPAN G.Traffic jams:dynamics and control[J].Philosophical Transactions of the Royal Society,2010,368(1928):4455-4479.
[4]BULDYREV S V,PARSHANI R,PAUL G,et al.Catastrophic cascade of failures in interdependent networks[J].Nature,2010,464(7291):1025-1028.
[5]BATAGELJ V,MRVAR A.Analysis of kinship relations with Pajek[J].Social Science Computer Review,2007,26(2):224-246.
[6]HAMBERGER K,HOUSEMAN M,DOUGLAS R W.Kinship network analysis[EB/OL].[2013-10-10].http://eclectic.ss.uci.edu/~drwhite/Feb20115605-Scott-Chap35.pdf.
[7]HAMBERGER K.Matrimonial circuits in kinship networks:Calculation,enumeration and census[J].Social Networks,2011,33(2):113-128.
[8]WHITE D R,HOUSEMAN M.A reticular approach to kinship[C/OL].[2013-10-10].http://intersci.ss.uci.edu/wiki/pdf/The_reticular_approach_to_kinship2a.pdf.
[9]HAMBERGER K.Matrimonial circuits in kinship networks:Calculation,enumeration and census[J].Social Networks,2011,33(2):113-128.
[10]CHEN Y L,LU J T.Mining inheritance rules from genealogical data[C]//Advances in Web-Age Information Management,LNCS3192.Berlin:Springer,2004:569-578.
[11]PRIGNANO L,SERVA M.Genealogical trees from genetic distances[J].European Physical Journal B,2009,69(3):455-463.
[12]BATAGELJ V,MRVAR A.Pajek-program for large network analysis[EB/OL].[2013-10-10].http://Pajek.imfm.si/doku.php?id=Pajek.