Triangle k Core: Difference between revisions
Jump to navigation
Jump to search
No edit summary |
No edit summary |
||
| (6 intermediate revisions by 2 users not shown) | |||
| Line 1: | Line 1: | ||
The triangle k core, or k truss has been intoduced by [http://www.csee.ogi.edu/~zak/cs506-pslc/trusses.pdf Cohen (NSA Tech. Report 2008)] and [http://web.cse.ohio-state.edu/~zhangya/ICDE12_conf_full_179.pdf Zhang and Parthasarathy (ICDE 2012)] 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>. | ||
More detailed background information is provided in | More detailed background information is provided in | ||
* Cohen, Jonathan. "Trusses: Cohesive subgraphs for social network analysis." National Security Agency Technical Report (2008). | |||
* Zhang, Yang, and Srinivasan Parthasarathy. "Extracting analyzing and visualizing triangle k-core motifs within networks." In Data Engineering (ICDE), 2012 IEEE 28th International Conference on, pp. 1049-1060. IEEE, 2012. | |||
=== 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> | ||
Latest revision as of 13:34, 10 June 2015
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 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
- Cohen, Jonathan. "Trusses: Cohesive subgraphs for social network analysis." National Security Agency Technical Report (2008).
- Zhang, Yang, and Srinivasan Parthasarathy. "Extracting analyzing and visualizing triangle k-core motifs within networks." In Data Engineering (ICDE), 2012 IEEE 28th International Conference on, pp. 1049-1060. IEEE, 2012.
Definition Triangle Core Number
The triangle core number of an edge is the maximal k such that
