Dense Subgraph Discovery Meets Strong Triadic Closure
Chamalee Wickrama Arachchi, Iiro Kumpulainen, Nikolaj Tatti · 2025
Read Dense Subgraph Discovery Meets Strong Triadic Closure by Chamalee Wickrama Arachchi, Iiro Kumpulainen, Nikolaj Tatti (2025) in the Tower of Babel, a free online library of public-domain works preserved in clean, searchable text. No sign-up. The full text is served as a plain-text file at a predictable URL, where text is present: https://antarctic-labs.com/tower-of-babel/arxiv-2502-01435.txt.
Description
Chamalee Wickrama Arachchi, Iiro Kumpulainen, and Nikolaj Tatti merged two network ideas in twenty twenty-five: dense subgraph discovery and strong triadic closure. Dense subgraphs flag communities and anomalies, but real ties differ in strength. Strong triadic closure says that if a node binds strongly to two others, those two must share at least a weak tie — a rule that labels edges strong or weak.
Their score for a subgraph weighs strong edges fully and weak edges by a user parameter, per node. At one extreme the problem equals finding the densest subgraph; at the other, the largest clique, so it is hard in general. They give an exact integer programming algorithm and four fast heuristics. Experiments recover planted truth in synthetic data and run efficiently on real networks.
Catalog record
| CREATOR | Chamalee Wickrama Arachchi, Iiro Kumpulainen, Nikolaj Tatti |
|---|---|
| YEAR | 2025 |
| COLLECTION | PAPERS |
| FORMAT | TXT |
| FILE SIZE | 60 KB |
| VERSION | 1.0 |
| LICENSE | http://creativecommons.org/licenses/by/4.0/ |
| RIGHTS | CC BY |
| SOURCE | arXiv |
Source: https://arxiv.org/abs/2502-01435