亲属关系网络的关系追溯算法

Relationships retrospect algorithm on kinship network

人与人之间通过婚姻关系和亲子关系构成了亲属关系网络。针对亲属关系网络庞大、难以追溯等问题,结合广度优先搜索策略,提出了两种亲属关系追溯算法:半径搜索和定向搜索。依托河北省全员人口数据库,将数据范围扩展到复杂网络的层次,以市级亲属关系数据为例构建亲属关系网络,包含约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： radius- search 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.