# Difference between revisions of "Triangle k Core"

Jump to navigation
Jump to search

Line 1: | Line 1: | ||

=Triangle k Core= | =Triangle k Core= | ||

+ | The triangle k core, or k truss have been intoduced by [http://www.csee.ogi.edu/~zak/cs506-pslc/trusses.pdf Cohen] and [http://web.cse.ohio-state.edu/~zhangya/ICDE12_conf_full_179.pdf Zhang and Parthasarathy] independently and runs in <math>\mathcal{O}(\Delta(G)m)</math> time, where <math>\Delta(G)</math> is the maximum degree and <math>m</math> the number of edges. | ||

=== Definition Triangle Core === | === Definition Triangle Core === | ||

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

Line 7: | Line 8: | ||

=== Definition Triangle Core Number === | === Definition Triangle Core Number === | ||

The triangle core number of an edge <math>e \in E(G)</math> is the maximal k such that <math>e \in C_k(G)</math> | The triangle core number of an edge <math>e \in E(G)</math> is the maximal k such that <math>e \in C_k(G)</math> | ||

− | |||

− |

## Revision as of 14:48, 8 June 2015

# Triangle k Core

The triangle k core, or k truss have been intoduced by Cohen and Zhang and Parthasarathy independently and runs in time, where is the maximum degree and the number of edges.

### Definition Triangle Core

The triangle k-core of a simple undirected graph is the inclusion maximal subgraph where each edge is part of at least triangles in .

More detailed background information is provided in

### Definition Triangle Core Number

The triangle core number of an edge is the maximal k such that