k-truss是一种子图结构，用于在图中寻找凝聚子图。类似的结构还有k-core

支持度(support)：图的一条边e包含在k个三角形中，则support(e) = k

k-truss：图G的极大子图g。在g中，每条边的support >= k-2。
（也可以简化定义为support >= k）

很明显，对于两个正整数$k_1>k_2$，$k_1$-truss$\subseteq k_2$–truss

truss decomposition：为了计算一个图中所有的k-truss，可以计算每条边的turssness。边e所在的最大k值的k-truss，trussness(e) = k。k-truss是所有trussness(e) >= k的边的诱导子图。

代码：

#include <stdio.h>
#include <vector>
#include <map>
#include <queue>
using namespace std;vector<int> *g;
map<pair<int, int>, int> edge;
int n, m;  //最大顶点为n，边的数量为m
vector<int> sup, truss;   //边的支持度和truss
vector<pair<int, int>> edge2;void BuildGraph(char* file);
void truss_decomposition();
int sup_calculation();
vector<int> k_truss(int K);void BuildGraph(char* file)   //建立图
{FILE* f = fopen(file, "r");int a, b;//计算最大顶点编号为nwhile (fscanf(f, "%d %d", &a, &b) != EOF){if (a > n) n = a;if (b > n) n = b;++m;}rewind(f);g = new vector<int>[n + 1];edge2.resize(m);m = 0;//int eid = 0;while (fscanf(f, "%d %d", &a, &b) != EOF){if (a == b) continue;  //忽略指向自己的边if (a < b)  //令a>b{int t = a;a = b;b = t;}if (edge.find(pair<int, int>(a, b)) == edge.end())  //这条边目前不存在，避免重边{g[a].push_back(b);g[b].push_back(a);edge2[m] = pair<int, int>(a, b);edge[pair<int, int>(a, b)] = m;edge[pair<int, int>(b, a)] = m++;}}truss.resize(m);sup.resize(m);fclose(f);
}void truss_decomposition()
{int maxsup = sup_calculation();vector<int> *bin = new vector<int>[maxsup + 1];for (int i = 0; i < m; ++i)bin[sup[i]].push_back(i);vector<bool> del(m, false);for (int i = 0; i <= maxsup; ++i){for (int j = 0; j < bin[i].size(); ++j){int eid = bin[i][j];if (del[eid] == true) continue;truss[eid] = i + 2;del[eid] = true;int x = edge2[eid].first;int y = edge2[eid].second;if (g[x].size() < g[y].size()){int t = x;x = y; y = t;}for (int k = 0; k < g[y].size(); ++k){int w = g[y][k];int e = edge[pair<int, int>(y, w)];if (del[e] == true) continue;if (edge.find(pair<int, int>(x, w)) != edge.end())  //xyw构成三角形{e = edge[pair<int, int>(x, w)];if (del[e] == true) continue;if (sup[e] > i){sup[e]--;bin[sup[e]].push_back(e);}e = edge[pair<int, int>(y, w)];if (sup[e] > i){sup[e]--;bin[sup[e]].push_back(e);}}}}}delete[] bin;
}vector<int> k_truss(int K)   //计算指定k的k-truss
{queue<int> q;vector<int> res;vector<bool> del(m, false);int maxsup = sup_calculation();for (int i = 0; i < m; ++i){if (sup[i] < K - 2)q.push(i);}while (q.empty() == false){int eid = q.front();q.pop();if (del[eid] == true) continue;del[eid] = true;int x = edge2[eid].first;int y = edge2[eid].second;if (g[x].size() < g[y].size()){int t = x;x = y;y = t;}for (int k = 0; k < g[y].size(); ++k){int w = g[y][k];int e = edge[pair<int, int>(y, w)];if (del[e] == true) continue;if (edge.find(pair<int, int>(x, w)) != edge.end())  //xyw构成三角形{e = edge[pair<int, int>(x, w)];if (del[e] == true) continue;sup[e]--;if (sup[e] < K - 2)q.push(e);e = edge[pair<int, int>(y, w)];sup[e]--;if (sup[e] < K - 2)q.push(e);}}}for (int i = 0; i < m; ++i)if (del[i] == false)res.push_back(i);return res;
}int sup_calculation()
{int maxsup = 0;for (int i = 0; i <= n; ++i){for (int j = 0; j < g[i].size(); ++j){int w = g[i][j];    //i的相邻顶点if (i > w){int eid = edge[pair<int, int>(i, w)];  //边(i,w)sup[eid] = 0;//degree(u)>degree(v)int u = g[i].size() > g[w].size() ? i : w;int v = g[i].size() > g[w].size() ? w : i;for (int k = 0; k < g[v].size(); ++k)   //w的相邻顶点{if (edge.find(pair<int, int>(u, g[v][k])) != edge.end())sup[eid]++;}if (sup[eid] > maxsup)maxsup = sup[eid];}}}return maxsup;
}