Difference between revisions of "Triangle k Core"

From visone manual
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>
 
Haha
 

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