Publikation: Cluster-Faithful Graph Visualization : New Metrics and Algorithms
Dateien
Datum
Autor:innen
Herausgeber:innen
ISSN der Zeitschrift
Electronic ISSN
ISBN
Bibliografische Daten
Verlag
Schriftenreihe
Auflagebezeichnung
DOI (zitierfähiger Link)
Internationale Patentnummer
Angaben zur Forschungsförderung
Projekt
Open Access-Veröffentlichung
Core Facility der Universität Konstanz
Titel in einer weiteren Sprache
Publikationstyp
Publikationsstatus
Erschienen in
Zusammenfassung
The cluster faithfulness metrics CQ measure how faithfully the ground truth clustering of a graph is represented as the geometric clustering in a drawing of the graph. Existing CQ metrics use k-means clustering, which effectively compute a geometric clustering when the cluster sizes are even, resulting in accurate CQ metrics. However, k-means clustering tends to compute clusters of even sizes and thus often fails to compute an accurate geometric clustering when the cluster sizes are uneven, leading to inaccurate CQ metrics.In this paper, we present a new cluster faithfulness metric CQ-HAC, using HAC (Hierarchical Agglomerative Clustering). HAC can compute a more accurate geometric clustering for uneven cluster sizes than k-means clustering. Consequently, CQ-HAC can more accurately measure cluster faithfulness, regardless of whether the sizes of clusters are even or uneven. Moreover, we present two algorithms, Cluster-kmeans and Cluster-HAC, for optimizing cluster faithfulness of graph drawings. Extensive experiments show that in practice, both algorithms always compute perfectly cluster-faithful drawings (i.e., CQ = 1) in our experiments using various graphs with both even and uneven cluster sizes, achieving significant improvement over existing graph layouts, including cluster-focused layouts.
Zusammenfassung in einer weiteren Sprache
Fachgebiet (DDC)
Schlagwörter
Konferenz
Rezension
Zitieren
ISO 690
CAI, Shijun, Seok-Hee HONG, Amyra MEIDIANA, Peter EADES, Daniel A. KEIM, 2024. Cluster-Faithful Graph Visualization : New Metrics and Algorithms. 2024 IEEE 17th Pacific Visualization Conference (PacificVis). Tokyo, Japan, 23. Apr. 2024 - 26. Apr. 2024. In: 2024 IEEE 17th Pacific Visualization Conference, PacificVis 2024, Tokyo, Japan 23-26 April 2024 : Proceedings. Los Alamitos, CA ; u.a.: IEEE, 2024, pp. 192-201. ISBN 979-8-3503-9380-4. Available under: doi: 10.1109/pacificvis60374.2024.00029BibTex
@inproceedings{Cai2024-04-23Clust-70094, year={2024}, doi={10.1109/pacificvis60374.2024.00029}, title={Cluster-Faithful Graph Visualization : New Metrics and Algorithms}, isbn={979-8-3503-9380-4}, publisher={IEEE}, address={Los Alamitos, CA ; u.a.}, booktitle={2024 IEEE 17th Pacific Visualization Conference, PacificVis 2024, Tokyo, Japan 23-26 April 2024 : Proceedings}, pages={192--201}, author={Cai, Shijun and Hong, Seok-Hee and Meidiana, Amyra and Eades, Peter and Keim, Daniel A.} }
RDF
<rdf:RDF xmlns:dcterms="http://purl.org/dc/terms/" xmlns:dc="http://purl.org/dc/elements/1.1/" xmlns:rdf="http://www.w3.org/1999/02/22-rdf-syntax-ns#" xmlns:bibo="http://purl.org/ontology/bibo/" xmlns:dspace="http://digital-repositories.org/ontologies/dspace/0.1.0#" xmlns:foaf="http://xmlns.com/foaf/0.1/" xmlns:void="http://rdfs.org/ns/void#" xmlns:xsd="http://www.w3.org/2001/XMLSchema#" > <rdf:Description rdf:about="https://kops.uni-konstanz.de/server/rdf/resource/123456789/70094"> <dc:creator>Hong, Seok-Hee</dc:creator> <bibo:uri rdf:resource="https://kops.uni-konstanz.de/handle/123456789/70094"/> <dc:contributor>Eades, Peter</dc:contributor> <dc:contributor>Meidiana, Amyra</dc:contributor> <dc:contributor>Hong, Seok-Hee</dc:contributor> <dcterms:title>Cluster-Faithful Graph Visualization : New Metrics and Algorithms</dcterms:title> <dspace:isPartOfCollection rdf:resource="https://kops.uni-konstanz.de/server/rdf/resource/123456789/36"/> <dcterms:issued>2024-04-23</dcterms:issued> <void:sparqlEndpoint rdf:resource="http://localhost/fuseki/dspace/sparql"/> <dcterms:isPartOf rdf:resource="https://kops.uni-konstanz.de/server/rdf/resource/123456789/36"/> <dc:contributor>Keim, Daniel A.</dc:contributor> <dc:language>eng</dc:language> <dc:date rdf:datatype="http://www.w3.org/2001/XMLSchema#dateTime">2024-06-11T11:28:22Z</dc:date> <foaf:homepage rdf:resource="http://localhost:8080/"/> <dc:creator>Eades, Peter</dc:creator> <dc:creator>Meidiana, Amyra</dc:creator> <dc:creator>Keim, Daniel A.</dc:creator> <dc:contributor>Cai, Shijun</dc:contributor> <dcterms:available rdf:datatype="http://www.w3.org/2001/XMLSchema#dateTime">2024-06-11T11:28:22Z</dcterms:available> <dc:creator>Cai, Shijun</dc:creator> <dcterms:abstract>The cluster faithfulness metrics CQ measure how faithfully the ground truth clustering of a graph is represented as the geometric clustering in a drawing of the graph. Existing CQ metrics use k-means clustering, which effectively compute a geometric clustering when the cluster sizes are even, resulting in accurate CQ metrics. However, k-means clustering tends to compute clusters of even sizes and thus often fails to compute an accurate geometric clustering when the cluster sizes are uneven, leading to inaccurate CQ metrics.In this paper, we present a new cluster faithfulness metric CQ-HAC, using HAC (Hierarchical Agglomerative Clustering). HAC can compute a more accurate geometric clustering for uneven cluster sizes than k-means clustering. Consequently, CQ-HAC can more accurately measure cluster faithfulness, regardless of whether the sizes of clusters are even or uneven. Moreover, we present two algorithms, Cluster-kmeans and Cluster-HAC, for optimizing cluster faithfulness of graph drawings. Extensive experiments show that in practice, both algorithms always compute perfectly cluster-faithful drawings (i.e., CQ = 1) in our experiments using various graphs with both even and uneven cluster sizes, achieving significant improvement over existing graph layouts, including cluster-focused layouts.</dcterms:abstract> </rdf:Description> </rdf:RDF>