Triangle k Core

The triangle k core, or k truss has been intoduced by Cohen (NSA Tech. Report 2008) and Zhang and Parthasarathy (ICDE 2012) independently and runs in $\mathcal{O}(\Delta(G)m)$ time, where $\Delta(G)$ is the maximum degree and $m$ the number of edges.

Definition Triangle Core

The triangle k-core of a simple undirected graph $G = (V,E)$ is the inclusion maximal subgraph $C_{k}(G) \subset G$ where each edge $e \in E(C_k(G))$ is part of at least $k$ triangles in $C_k(G)$.

More detailed background information is provided in

• Cohen, Jonathan. "Trusses: Cohesive subgraphs for social network analysis." National Security Agency Technical Report (2008).
• Zhang, Yang, and Srinivasan Parthasarathy. "Extracting analyzing and visualizing triangle k-core motifs within networks." In Data Engineering (ICDE), 2012 IEEE 28th International Conference on, pp. 1049-1060. IEEE, 2012.

Definition Triangle Core Number

The triangle core number of an edge $e \in E(G)$ is the maximal k such that $e \in C_k(G)$