On the number of small edge-weighted subgraphs
Fuente:
arXiv
Salvato in:
| Autori principali: | , |
|---|---|
| Natura: | Preprint |
| Pubblicazione: |
2025
|
| Soggetti: | |
| Accesso online: | |
| Tags: |
Aggiungi Tag
Nessun Tag, puoi essere il primo ad aggiungerne!!
|
| _version_ | 1866917088289882112 |
|---|---|
| author | Yu, Feng Yuan, Mingao |
| author_facet | Yu, Feng Yuan, Mingao |
| contents | Subgraph counting is a fundamental task that underpins several network analysis methodologies, including community detection and graph two-sample tests. Counting subgraphs is a computationally intensive problem. Substantial research has focused on developing efficient algorithms and strategies to make it feasible for larger unweighted graphs. Implementing those algorithms can be a significant hurdle for data professionals or researchers with limited expertise in algorithmic principles and programming. Furthermore, many real-world networks are weighted. Computing the number of weighted subgraphs in weighted networks presents a computational challenge, as no efficient algorithm exists for the worst-case scenario. In this paper, we derive explicit formulas for counting small edge-weighted subgraphs using the weighted adjacency matrix. These formulas are applicable to unweighted networks, offering a simple and highly practical analytical tool for researchers across various scientific domains. In addition, we introduce a generalized methodology for calculating arbitrary weighted subgraphs. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2511_14058 |
| institution | arXiv |
| publishDate | 2025 |
| record_format | arxiv |
| spellingShingle | On the number of small edge-weighted subgraphs Yu, Feng Yuan, Mingao Combinatorics 05C30, 05C50, 05C85 Subgraph counting is a fundamental task that underpins several network analysis methodologies, including community detection and graph two-sample tests. Counting subgraphs is a computationally intensive problem. Substantial research has focused on developing efficient algorithms and strategies to make it feasible for larger unweighted graphs. Implementing those algorithms can be a significant hurdle for data professionals or researchers with limited expertise in algorithmic principles and programming. Furthermore, many real-world networks are weighted. Computing the number of weighted subgraphs in weighted networks presents a computational challenge, as no efficient algorithm exists for the worst-case scenario. In this paper, we derive explicit formulas for counting small edge-weighted subgraphs using the weighted adjacency matrix. These formulas are applicable to unweighted networks, offering a simple and highly practical analytical tool for researchers across various scientific domains. In addition, we introduce a generalized methodology for calculating arbitrary weighted subgraphs. |
| title | On the number of small edge-weighted subgraphs |
| topic | Combinatorics 05C30, 05C50, 05C85 |
| url | https://arxiv.org/abs/2511.14058 |