Event‐based Dynamic Graph Drawing without the Agonizing Pain

Arleo, A.; Miksch, S.; Archambault, Daniel

doi:10.1111/cgf.14615

Journal article 618 views 79 downloads

Event‐based Dynamic Graph Drawing without the Agonizing Pain

A. Arleo

, S. Miksch

, Daniel Archambault

Computer Graphics Forum, Volume: 41, Issue: 6, Pages: 226 - 244

Swansea University Author: Daniel Archambault

PDF | Version of Record

© 2022 The Authors. This is an open access article under the terms of the Creative Commons Attribution License
Download (1.92MB)

Check full text

DOI (Published version): 10.1111/cgf.14615

Abstract

Temporal networks can naturally model real-world complex phenomena such as contact networks, information dissemination and physical proximity. However, nodes and edges bear real-time coordinates, making it difficult to organize them into discrete timeslices, without a loss of temporal information du...

Full description

Published in:	Computer Graphics Forum
ISSN:	0167-7055 1467-8659
Published:	Wiley 2022
Online Access:	Check full text
URI:	https://cronfa.swan.ac.uk/Record/cronfa60330
Tags:	Add Tag No Tags, Be the first to tag this record!

first_indexed	2022-06-28T10:06:19Z
last_indexed	2023-01-13T19:20:23Z
id	cronfa60330
recordtype	SURis
fullrecord	<?xml version="1.0" encoding="utf-8"?><rfc1807 xmlns:xsi="http://www.w3.org/2001/XMLSchema-instance" xmlns:xsd="http://www.w3.org/2001/XMLSchema"><bib-version>v2</bib-version><id>60330</id><entry>2022-06-28</entry><title>Event‐based Dynamic Graph Drawing without the Agonizing Pain</title><swanseaauthors><author><sid>8fa6987716a22304ef04d3c3d50ef266</sid><ORCID>0000-0003-4978-8479</ORCID><firstname>Daniel</firstname><surname>Archambault</surname><name>Daniel Archambault</name><active>true</active><ethesisStudent>false</ethesisStudent></author></swanseaauthors><date>2022-06-28</date><deptcode>SCS</deptcode><abstract>Temporal networks can naturally model real-world complex phenomena such as contact networks, information dissemination and physical proximity. However, nodes and edges bear real-time coordinates, making it difficult to organize them into discrete timeslices, without a loss of temporal information due to projection. Event-based dynamic graph drawing rejects the notion of a timeslice and allows each node and edge to retain its own real-valued time coordinate. While existing work has demonstrated clear advantages for this approach, they come at a running time cost. We investigate the problem of accelerating event-based layout to make it more competitive with existing layout techniques. In this paper, we describe the design, implementation and experimental evaluation of MultiDynNoS, the first multi-level event-based graph layout algorithm. We consider three operators for coarsening and placement, inspired by Walshaw, GRIP and FM3, which we couple with an event-based graph drawing algorithm. We also propose two extensions to the core algorithm: AutoTau and Bend Transfer. We perform two experiments: first, we compare MultiDynNoS variants to existing state-of-the-art dynamic graph layout approaches; second, we investigate the impact of each of the proposed algorithm extensions. MultiDynNoS proves to be competitive with existing approaches, and the proposed extensions achieve their design goals and contribute in opening new research directions.</abstract><type>Journal Article</type><journal>Computer Graphics Forum</journal><volume>41</volume><journalNumber>6</journalNumber><paginationStart>226</paginationStart><paginationEnd>244</paginationEnd><publisher>Wiley</publisher><placeOfPublication/><isbnPrint/><isbnElectronic/><issnPrint>0167-7055</issnPrint><issnElectronic>1467-8659</issnElectronic><keywords>Visualization, Graph Drawing, Temporal Networks</keywords><publishedDay>1</publishedDay><publishedMonth>9</publishedMonth><publishedYear>2022</publishedYear><publishedDate>2022-09-01</publishedDate><doi>10.1111/cgf.14615</doi><url>http://dx.doi.org/10.1111/cgf.14615</url><notes/><college>COLLEGE NANME</college><department>Computer Science</department><CollegeCode>COLLEGE CODE</CollegeCode><DepartmentCode>SCS</DepartmentCode><institution>Swansea University</institution><apcterm>Other</apcterm><funders>The authors acknowledge TU Wien Bibliothek for financial supportthrough its Open Access Funding Programme.</funders><projectreference/><lastEdited>2023-05-22T15:18:44.3605675</lastEdited><Created>2022-06-28T10:58:38.7263121</Created><path><level id="1">Faculty of Science and Engineering</level><level id="2">School of Mathematics and Computer Science - Computer Science</level></path><authors><author><firstname>A.</firstname><surname>Arleo</surname><orcid>0000-0003-2008-3651</orcid><order>1</order></author><author><firstname>S.</firstname><surname>Miksch</surname><orcid>0000-0003-4427-5703</orcid><order>2</order></author><author><firstname>Daniel</firstname><surname>Archambault</surname><orcid>0000-0003-4978-8479</orcid><order>3</order></author></authors><documents><document><filename>60330__25237__b468c6b2b118416ca373d33decde6423.pdf</filename><originalFilename>60330_VoR.pdf</originalFilename><uploaded>2022-09-27T13:37:49.7415660</uploaded><type>Output</type><contentLength>2014767</contentLength><contentType>application/pdf</contentType><version>Version of Record</version><cronfaStatus>true</cronfaStatus><documentNotes>© 2022 The Authors. This is an open access article under the terms of the Creative Commons Attribution License</documentNotes><copyrightCorrect>true</copyrightCorrect><language>eng</language><licence>http://creativecommons.org/licenses/by/4.0/</licence></document></documents><OutputDurs/></rfc1807>
spelling	v2 60330 2022-06-28 Event‐based Dynamic Graph Drawing without the Agonizing Pain 8fa6987716a22304ef04d3c3d50ef266 0000-0003-4978-8479 Daniel Archambault Daniel Archambault true false 2022-06-28 SCS Temporal networks can naturally model real-world complex phenomena such as contact networks, information dissemination and physical proximity. However, nodes and edges bear real-time coordinates, making it difficult to organize them into discrete timeslices, without a loss of temporal information due to projection. Event-based dynamic graph drawing rejects the notion of a timeslice and allows each node and edge to retain its own real-valued time coordinate. While existing work has demonstrated clear advantages for this approach, they come at a running time cost. We investigate the problem of accelerating event-based layout to make it more competitive with existing layout techniques. In this paper, we describe the design, implementation and experimental evaluation of MultiDynNoS, the first multi-level event-based graph layout algorithm. We consider three operators for coarsening and placement, inspired by Walshaw, GRIP and FM3, which we couple with an event-based graph drawing algorithm. We also propose two extensions to the core algorithm: AutoTau and Bend Transfer. We perform two experiments: first, we compare MultiDynNoS variants to existing state-of-the-art dynamic graph layout approaches; second, we investigate the impact of each of the proposed algorithm extensions. MultiDynNoS proves to be competitive with existing approaches, and the proposed extensions achieve their design goals and contribute in opening new research directions. Journal Article Computer Graphics Forum 41 6 226 244 Wiley 0167-7055 1467-8659 Visualization, Graph Drawing, Temporal Networks 1 9 2022 2022-09-01 10.1111/cgf.14615 http://dx.doi.org/10.1111/cgf.14615 COLLEGE NANME Computer Science COLLEGE CODE SCS Swansea University Other The authors acknowledge TU Wien Bibliothek for financial supportthrough its Open Access Funding Programme. 2023-05-22T15:18:44.3605675 2022-06-28T10:58:38.7263121 Faculty of Science and Engineering School of Mathematics and Computer Science - Computer Science A. Arleo 0000-0003-2008-3651 1 S. Miksch 0000-0003-4427-5703 2 Daniel Archambault 0000-0003-4978-8479 3 60330__25237__b468c6b2b118416ca373d33decde6423.pdf 60330_VoR.pdf 2022-09-27T13:37:49.7415660 Output 2014767 application/pdf Version of Record true © 2022 The Authors. This is an open access article under the terms of the Creative Commons Attribution License true eng http://creativecommons.org/licenses/by/4.0/
title	Event‐based Dynamic Graph Drawing without the Agonizing Pain
spellingShingle	Event‐based Dynamic Graph Drawing without the Agonizing Pain Daniel Archambault
title_short	Event‐based Dynamic Graph Drawing without the Agonizing Pain
title_full	Event‐based Dynamic Graph Drawing without the Agonizing Pain
title_fullStr	Event‐based Dynamic Graph Drawing without the Agonizing Pain
title_full_unstemmed	Event‐based Dynamic Graph Drawing without the Agonizing Pain
title_sort	Event‐based Dynamic Graph Drawing without the Agonizing Pain
author_id_str_mv	8fa6987716a22304ef04d3c3d50ef266
author_id_fullname_str_mv	8fa6987716a22304ef04d3c3d50ef266_***_Daniel Archambault
author	Daniel Archambault
author2	A. Arleo S. Miksch Daniel Archambault
format	Journal article
container_title	Computer Graphics Forum
container_volume	41
container_issue	6
container_start_page	226
publishDate	2022
institution	Swansea University
issn	0167-7055 1467-8659
doi_str_mv	10.1111/cgf.14615
publisher	Wiley
college_str	Faculty of Science and Engineering
hierarchytype
hierarchy_top_id	facultyofscienceandengineering
hierarchy_top_title	Faculty of Science and Engineering
hierarchy_parent_id	facultyofscienceandengineering
hierarchy_parent_title	Faculty of Science and Engineering
department_str	School of Mathematics and Computer Science - Computer Science{{{_:::_}}}Faculty of Science and Engineering{{{_:::_}}}School of Mathematics and Computer Science - Computer Science
url	http://dx.doi.org/10.1111/cgf.14615
document_store_str	1
active_str	0
description	Temporal networks can naturally model real-world complex phenomena such as contact networks, information dissemination and physical proximity. However, nodes and edges bear real-time coordinates, making it difficult to organize them into discrete timeslices, without a loss of temporal information due to projection. Event-based dynamic graph drawing rejects the notion of a timeslice and allows each node and edge to retain its own real-valued time coordinate. While existing work has demonstrated clear advantages for this approach, they come at a running time cost. We investigate the problem of accelerating event-based layout to make it more competitive with existing layout techniques. In this paper, we describe the design, implementation and experimental evaluation of MultiDynNoS, the first multi-level event-based graph layout algorithm. We consider three operators for coarsening and placement, inspired by Walshaw, GRIP and FM3, which we couple with an event-based graph drawing algorithm. We also propose two extensions to the core algorithm: AutoTau and Bend Transfer. We perform two experiments: first, we compare MultiDynNoS variants to existing state-of-the-art dynamic graph layout approaches; second, we investigate the impact of each of the proposed algorithm extensions. MultiDynNoS proves to be competitive with existing approaches, and the proposed extensions achieve their design goals and contribute in opening new research directions.
published_date	2022-09-01T15:18:42Z
_version_	1766604273269866496
score	11.036334

Event‐based Dynamic Graph Drawing without the Agonizing Pain

Similar Items