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.
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 .
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
is the maximal k such that 