An effective algorithm for genealogical graph partitioning

摘要

This study proposes a novel Approximately Balanced Tree Partitioning Algorithm (TPA) to overcome the significant challenges in genealogical data management, encompassing the storage, maintenance, and interpretation of complex familial networks. Our TPA is adept at modularizing and simplifying intricate relationships in genealogical graphs into logically succinct tree structures, reducing user cognitive load and enhancing the utility of genealogical data in real applications like hereditary disease research, forensic investigation, and consanguinity counseling. In addition, TPA prioritizes structural closeness in partitioning to avoid misleading insights from unrelated data points and maintain a balance of node distribution to prevent workload and communication overheads in distributed graph data processing systems. The effectiveness of our algorithm is demonstrated through extensive experiments on four real-world genealogical datasets, substantiating its superiority over five state-of-the-art rival models in dealing with the complex and rapidly expanding landscape of genealogical data.

关键词