On the effect of the average clustering coefficient on topology-based link prediction in featureless graphs
Fuente:
arXiv
Saved in:
| Main Authors: | , |
|---|---|
| Format: | Preprint |
| Published: |
2025
|
| Subjects: | |
| Online Access: | |
| Tags: |
Add Tag
No Tags, Be the first to tag this record!
|
| _version_ | 1866912184381997056 |
|---|---|
| author | Rafiepour, Mehrdad Vahidipour, S. Mehdi |
| author_facet | Rafiepour, Mehrdad Vahidipour, S. Mehdi |
| contents | Link prediction is a fundamental problem in graph theory with diverse applications, including recommender systems, community detection, and identifying spurious connections. While feature-based methods achieve high accuracy, their reliance on node attributes limits their applicability in featureless graphs. For such graphs, structure-based approaches, including common neighbor-based and degree-dependent methods, are commonly employed. However, the effectiveness of these methods depends on graph density, with common neighbor-based algorithms performing well in dense graphs and degree-dependent methods being more suitable for sparse or tree-like graphs. Despite this, the literature lacks a clear criterion to distinguish between dense and sparse graphs. This paper introduces the average clustering coefficient as a criterion for assessing graph density to assist with the choice of link prediction algorithms. To address the scarcity of datasets for empirical analysis, we propose a novel graph generation method based on the Barabasi-Albert model, which enables controlled variation of graph density while preserving structural heterogeneity. Through comprehensive experiments on synthetic and real-world datasets, we establish an empirical boundary for the average clustering coefficient that facilitates the selection of effective link prediction techniques. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2501_06721 |
| institution | arXiv |
| publishDate | 2025 |
| record_format | arxiv |
| spellingShingle | On the effect of the average clustering coefficient on topology-based link prediction in featureless graphs Rafiepour, Mehrdad Vahidipour, S. Mehdi Social and Information Networks 05C85 G.2.2 Link prediction is a fundamental problem in graph theory with diverse applications, including recommender systems, community detection, and identifying spurious connections. While feature-based methods achieve high accuracy, their reliance on node attributes limits their applicability in featureless graphs. For such graphs, structure-based approaches, including common neighbor-based and degree-dependent methods, are commonly employed. However, the effectiveness of these methods depends on graph density, with common neighbor-based algorithms performing well in dense graphs and degree-dependent methods being more suitable for sparse or tree-like graphs. Despite this, the literature lacks a clear criterion to distinguish between dense and sparse graphs. This paper introduces the average clustering coefficient as a criterion for assessing graph density to assist with the choice of link prediction algorithms. To address the scarcity of datasets for empirical analysis, we propose a novel graph generation method based on the Barabasi-Albert model, which enables controlled variation of graph density while preserving structural heterogeneity. Through comprehensive experiments on synthetic and real-world datasets, we establish an empirical boundary for the average clustering coefficient that facilitates the selection of effective link prediction techniques. |
| title | On the effect of the average clustering coefficient on topology-based link prediction in featureless graphs |
| topic | Social and Information Networks 05C85 G.2.2 |
| url | https://arxiv.org/abs/2501.06721 |