Publikation:

Cluster-Faithful Graph Visualization : New Metrics and Algorithms

Lade...
Vorschaubild

Dateien

Zu diesem Dokument gibt es keine Dateien.

Datum

2024

Autor:innen

Cai, Shijun
Hong, Seok-Hee
Meidiana, Amyra
Eades, Peter

Herausgeber:innen

Kontakt

ISSN der Zeitschrift

Electronic ISSN

ISBN

Bibliografische Daten

Verlag

Schriftenreihe

Auflagebezeichnung

URI (zitierfähiger Link)
ArXiv-ID

Internationale Patentnummer

Angaben zur Forschungsförderung

Projekt

Open Access-Veröffentlichung
Core Facility der Universität Konstanz

Gesperrt bis

Titel in einer weiteren Sprache

Publikationstyp
Beitrag zu einem Konferenzband
Publikationsstatus
Published

Erschienen 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.00029

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)
004 Informatik

Schlagwörter

Konferenz

2024 IEEE 17th Pacific Visualization Conference (PacificVis), 23. Apr. 2024 - 26. Apr. 2024, Tokyo, Japan
Rezension
undefined / . - undefined, undefined

Forschungsvorhaben

Organisationseinheiten

Zeitschriftenheft

Zugehörige Datensätze in KOPS

Zitieren

ISO 690CAI, 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.00029
BibTex
@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>

Interner Vermerk

xmlui.Submission.submit.DescribeStep.inputForms.label.kops_note_fromSubmitter

Kontakt
URL der Originalveröffentl.

Prüfdatum der URL

Prüfungsdatum der Dissertation

Finanzierungsart

Kommentar zur Publikation

Allianzlizenz
Corresponding Authors der Uni Konstanz vorhanden
Internationale Co-Autor:innen
Universitätsbibliographie
Ja
Begutachtet
Diese Publikation teilen