Triangle k Core: Difference between revisions
Jump to navigation
Jump to search
No edit summary |
No edit summary |
||
| 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
