A parallel Fruchterman-Reingold algorithm optimized for fast visualization of large graphs and swarms of data

详细信息    查看全文

• 作者：Petr Gajdo&scaron ; ^{petr.gajdos@vsb.cz" class="auth_mail" title="E-mail the corresponding author} ; Tomá ; &scaron ; Ježowicz ^{tomas.jezowicz.st@vsb.cz" class="auth_mail" title="E-mail the corresponding author} ; Vojtěch Uher ^{vojtech.uher@vsb.cz" class="auth_mail" title="E-mail the corresponding author} ; Pavel Dohná ; lek ; ^{pavel.dohnalek@vsb.cz" class="auth_mail" title="E-mail the corresponding author}
• 关键词：Graph layouts ; Nearest neighbors ; Fruchterman&ndash ; Reingold ; Fast graph visualization ; GPU ; CUDA
• 刊名：Swarm and Evolutionary Computation
• 出版年：2016
• 出版时间：February 2016
• 年：2016
• 卷：26
• 期：Complete
• 页码：56-63
• 全文大小：2360 K

文摘

Graphs in computer science are widely used in social network analysis, computer networks, transportation networks, and many other areas. In general, they can visualize relationships between objects. However, fast drawing of graphs and other structures containing large numbers of data points with readable layouts is still a challenge. This paper describes a novel variant of the Fruchterman–Reingold graph layout algorithm which is adapted to GPU parallel architecture. A new approach based on space-filling curves and a new way of repulsive forces computation on GPU are described. The paper contains both performance and quality tests of the new algorithm.