Saved in:
| Main Authors: | , , , , , , |
|---|---|
| Format: | Preprint |
| Published: |
2024
|
| Subjects: | |
| Online Access: | https://arxiv.org/abs/2410.00601 |
| Tags: |
Add Tag
No Tags, Be the first to tag this record!
|
| _version_ | 1866913826999369728 |
|---|---|
| author | Beth, Christian Fleischmann, Pamela Huch, Annika Kazempour, Daniyal Kröger, Peer Kulow, Andrea Renz, Matthias |
| author_facet | Beth, Christian Fleischmann, Pamela Huch, Annika Kazempour, Daniyal Kröger, Peer Kulow, Andrea Renz, Matthias |
| contents | In 2017 Day et al. introduced the notion of locality as a structural complexity-measure for patterns in the field of pattern matching established by Angluin in 1980. In 2019 Casel et al. showed that determining the locality of an arbitrary pattern is NP-complete. Inspired by hierarchical clustering, we extend the notion to coloured graphs, i.e., given a coloured graph determine an enumeration of the colours such that colouring the graph stepwise according to the enumeration leads to as few clusters as possible. Next to first theoretical results on graph classes, we propose a priority search algorithm to compute the $k$-locality of a graph. The algorithm is optimal in the number of marking prefix expansions, and is faster by orders of magnitude than an exhaustive search. Finally, we perform a case study on a DBLP subgraph to demonstrate the potential of $k$-locality for knowledge discovery. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2410_00601 |
| institution | arXiv |
| publishDate | 2024 |
| record_format | arxiv |
| spellingShingle | $k$-local Graphs Beth, Christian Fleischmann, Pamela Huch, Annika Kazempour, Daniyal Kröger, Peer Kulow, Andrea Renz, Matthias Combinatorics Data Structures and Algorithms Social and Information Networks In 2017 Day et al. introduced the notion of locality as a structural complexity-measure for patterns in the field of pattern matching established by Angluin in 1980. In 2019 Casel et al. showed that determining the locality of an arbitrary pattern is NP-complete. Inspired by hierarchical clustering, we extend the notion to coloured graphs, i.e., given a coloured graph determine an enumeration of the colours such that colouring the graph stepwise according to the enumeration leads to as few clusters as possible. Next to first theoretical results on graph classes, we propose a priority search algorithm to compute the $k$-locality of a graph. The algorithm is optimal in the number of marking prefix expansions, and is faster by orders of magnitude than an exhaustive search. Finally, we perform a case study on a DBLP subgraph to demonstrate the potential of $k$-locality for knowledge discovery. |
| title | $k$-local Graphs |
| topic | Combinatorics Data Structures and Algorithms Social and Information Networks |
| url | https://arxiv.org/abs/2410.00601 |