计算机应用 ›› 2014, Vol. 34 ›› Issue (7): 1988-1991.DOI: 10.11772/j.issn.1001-9081.2014.07.1988

• 数据技术 • 上一篇    下一篇

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

郭瑞强,闫绍惠,赵书良,申玉凤   

  1. 河北师范大学 数学与信息科学学院,石家庄 050024
  • 收稿日期:2014-01-07 修回日期:2014-02-26 出版日期:2014-07-01 发布日期:2014-08-01
  • 通讯作者: 闫绍惠
  • 作者简介:郭瑞强(1974-),男,河北石家庄人,副教授,博士,CCF会员,主要研究方向:数据挖掘、Web智能系统;闫绍惠(1988-),女,河北承德人,硕士,主要研究方向:数据挖掘、复杂网络;赵书良(1967-),男,河北石家庄人,教授,博士,主要研究方向:智能信息处理;申玉凤(1987-),女,河北石家庄人,硕士,主要研究方向:数据挖掘。
  • 基金资助:

    国家自然科学资金;河北省教育厅自然科学研究项目;河北师范大学应用开发基金项目

Relationships retrospect algorithm on kinship network

GUO Ruiqiang,YAN Shaohui,ZHAO Shuliang,SHEN Yufeng   

  1. College of Mathematics and Information Science, Hebei Normal University, Shijiazhuang Hebei 050024, China
  • Received:2014-01-07 Revised:2014-02-26 Online:2014-07-01 Published:2014-08-01
  • Contact: YAN Shaohui

摘要:

人与人之间通过婚姻关系和亲子关系构成了亲属关系网络。针对亲属关系网络庞大、难以追溯等问题,结合广度优先搜索策略,提出了两种亲属关系追溯算法:半径搜索和定向搜索。依托河北省全员人口数据库,将数据范围扩展到复杂网络的层次,以市级亲属关系数据为例构建亲属关系网络,包含约415万个节点,约1088万条边。采用双向亲属关系存储,避免了亲属关系回溯查询等问题。实验结果表明关系追溯算法能够准确定位特定关系亲属,同时具有较高的执行效率和较好的灵活性。

Abstract:

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 4150000 vertexes, and about 10880000 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.

中图分类号: