Triangle k Core

From visone user support

Jump to: navigation, search

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 Δ(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 Ck(G).

More detailed background information is provided in

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)

Personal tools