2
$\begingroup$

Cross-posted on Mathematics SE.

Since I have to implement an algorithm in the language of linear algebra, I'm trying to understand K-Truss Graphs which are defined as such

The k-truss is a subset of the graph with the same number of vertices, where each edge appears in at least $𝑘 − 2$ triangles in the original graph.

Given this example:

Example

The $4$-Truss should be $2-1-4$ since we want edges present in at least $2$ triangles of the original graph:

  • edge $1-2$ is present in triangle $0-1-2$ and triangle $1-2-4.$
  • edge $1-4$ is present in triangle $1-3-4$ and triangle $1-2-4.$

Is the solution given on my example correct?

$\endgroup$
5
  • 1
    $\begingroup$ I don't think your example is correct. From this description, a 'truss' is a subgraph of some original graph. A k-truss requires that every edge $e$ in your truss, is supported by at least k-2 edges that are also part of the truss and that form triangles with edge $e$. In the example that you gave for the subgraph induced by vertices {1,2,4}, edge (0,1) cannot be a supporting edge as it is not part of the subgraph. $\endgroup$ Aug 19 at 0:25
  • 1
    $\begingroup$ The subgraph induced by vertices {1,2,4} is however a 3-truss because every edge {(1,4),(2,4),(1,2)} is part of at least 1 triangle made up of nodes that are part of the truss. $\endgroup$ Aug 19 at 0:29
  • $\begingroup$ Thanks for the answer Joris, so, {0,1,2} and {1,3,4} are also 3-truss, is that correct? $\endgroup$
    – karalis1
    Aug 19 at 10:01
  • 2
    $\begingroup$ Welcome to OR.SE. In future, please add a cross-posting link to your question when you cross-post. $\endgroup$
    – TheSimpliFire
    Aug 19 at 14:47
  • $\begingroup$ @TheSimpliFire sorry didn't know this rule, thanks for the edit $\endgroup$
    – karalis1
    Aug 19 at 14:48
3
$\begingroup$

The definition of a k-truss you are working with seems to deviate from the 'standard' definition. See below for a few different definitions that boil down to the same thing.

A k-truss of a graph $G$ is the largest subgraph of $G$ such that each edge is contained in at least $k−2$ triangles in this subgraph.

source: Li, Z., Lu, Y., Zhang, WP. et al. Discovering Hierarchical Subgraphs of K-Core-Truss. Data Sci. Eng. 3, 136–149 (2018)

A k-truss is an inclusion-maximal subgraph $H$ in which each edge belongs to at least $k - 2$ triangles inside $H$

source: A. Conte, D. De Sensi, R. Grossi, A. Marino and L. Versari, "Truly Scalable K-Truss and Max-Truss Algorithms for Community Detection in Graphs," in IEEE Access, vol. 8, pp. 139096-139109, 2020

As I stated in the comments earlier, the subgraph induced by vertex set $\{2,1,4\}$ is not a 4-truss because that would require that every edge in your induced subgraph, is contained in 2 different triangles which must also be contained in the subgraph. In your case, edge $(1,2)$ is only contained in 1 triangle.

Following the above definitions, the subgraph induced by vertex set $\{2,1,4\}$ is not a 3-truss either, because it is not maximal. A 3-truss of your graph, would be the entire graph, since that is the largest subgraph in which every edge is part of at least 1 triangle in your subgraph.

Your graph does not contain a k-truss with $k\geq 4$.

Edit: as often in mathematics, there are inconsistencies in definitions. The definitions I cited above, explicitly require a k-truss to be the largest subgraph or an inclusion-maximal subgraph $H$ s.t. every edge in $H$ is covered by at least $k-2$ triangles in $H$. Note that there's a difference between largest (read: maximum) and maximal subgraph. Moreover, some works seem to drop this 'maximal' requirement and refer to a k-truss as any (not necessarily maximal) subgraph $H$ s.t. every edge in $H$ is covered by at least $k-2$ triangles in $H$, see e.g.: https://louridas.github.io/rwa/assignments/finding-trusses/

$\endgroup$
1
  • $\begingroup$ perfectly explained, thank you again! $\endgroup$
    – karalis1
    Aug 19 at 21:54

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.