The k -truss index evaluates the influence of a node based on the \(k\)-truss decomposition of a graph \(G\) [2]. A \(k\)-truss is the maximal subgraph in which every edge participates in at least \(k-2\) triangles. Equivalently, a \(k\)-clique corresponds to a \((k-2)\)-truss and a \(k\)-truss is contained within a \((k+1)\)-core. Malliaros et al. [3] demonstrate that nodes belonging to the maximal \(k\)-truss subgraph exhibit stronger spreading influence than nodes identified by other centrality measures, including degree and \(k\)-core index.

References

[1] Shvydun, S. (2025). Zoo of Centralities: Encyclopedia of Node Metrics in Complex Networks. arXiv: 2511.05122 https://doi.org/10.48550/arXiv.2511.05122
[2] Cohen, J. (2008). Trusses: Cohesive subgraphs for social network analysis. National security agency technical report, 16(3.1), 1-29.
[3] Malliaros, F. D., Rossi, M. E. G., & Vazirgiannis, M. (2016). Locating influential nodes in complex networks. Scientific reports, 6(1), 19307. doi: 10.1038/srep19307.