概述

k-Truss算法能识别图中称为Truss（桁架）的最大的、紧密连接的子图。该算法在各个领域都有广泛的应用，包括社交网络、生物网络和交通网络，通过发现密切相关的节点组成的社区或集群，k-Truss算法为复杂网络的结构和连通性提供了有价值的见解。

k-Truss最初由J. Cohen在2005年定义：

• J. Cohen, Trusses: Cohesive Subgraphs for Social Network Analysis (2005)

基本概念

k-Truss

Truss的概念是根据对社交凝聚力的观察而提出的：如果两个人关系紧密，他们很可能也与他人有共同联系。由此创建k-Truss：A和B之间的连接只有在至少k-2个其他人的支持下才被认为是合法的，这些人分别与A和B有连接。换句话说，k-Truss中每条边所连接的两个节点至少有k–2个共同邻居。

正式的定义是，k-Truss是图中的最大子图，其中每条边至少由k-2对边支撑，与该边形成三角形。

下面是一个示例图，其中3-truss和4-truss以红色突出显示。此图没有k值为5或更大的truss。

嬴图的k-Truss算法识别图中每个连通分量的最大Truss。

特殊说明

• 每个Truss中至少包含3个节点（当k≥3）。
• 在两点之间可能存在多条边的复杂图中，Truss中的三角形是按边计数的。另请参阅三角形计算算法。
• k-Truss算法忽略边的方向，按照无向边进行计算。

示例图集

创建示例图集：

// 在空图集中逐行运行以下语句
insert().into(@default).nodes([{_id:"a"}, {_id:"b"}, {_id:"c"}, {_id:"d"}, {_id:"e"}, {_id:"f"}, {_id:"g"}, {_id:"h"}, {_id:"i"}, {_id:"j"}, {_id:"k"}, {_id:"l"}, {_id:"m"}])
insert().into(@default).edges([{_from:"b", _to:"a"}, {_from:"d", _to:"a"}, {_from:"c", _to:"a"}, {_from:"d", _to:"c"}, {_from:"f", _to:"a"}, {_from:"f", _to:"d"}, {_from:"d", _to:"f"}, {_from:"f", _to:"d"}, {_from:"d", _to:"e"}, {_from:"e", _to:"f"}, {_from:"f", _to:"c"}, {_from:"c", _to:"h"}, {_from:"i", _to:"m"}, {_from:"i", _to:"g"}, {_from:"k", _to:"c"}, {_from:"k", _to:"c"}, {_from:"k", _to:"f"}, {_from:"j", _to:"l"}, {_from:"k", _to:"l"}, {_from:"g", _to:"k"}, {_from:"m", _to:"k"}, {_from:"l", _to:"f"}, {_from:"m", _to:"f"}, {_from:"f", _to:"g"}, {_from:"g", _to:"m"}, {_from:"m", _to:"l"}])

创建HDC图集

将当前图集全部加载到HDC服务器hdc-server-1上，并命名为 hdc_ktruss：

CALL hdc.graph.create("hdc-server-1", "hdc_ktruss", {
  nodes: {"*": ["*"]},
  edges: {"*": ["*"]},
  direction: "undirected",
  load_id: true,
  update: "static",
  query: "query",
  default: false
})

hdc.graph.create("hdc_ktruss", {
  nodes: {"*": ["*"]},
  edges: {"*": ["*"]},
  direction: "undirected",
  load_id: true,
  update: "static",
  query: "query",
  default: false
}).to("hdc-server-1")

参数

算法名：k_truss

文件回写

CALL algo.k_truss.write("hdc_ktruss", {
  params: {
    k: 4,
    return_id_uuid: "id"
  },
  return_params: {
    file: {
      filename: "4truss.txt"
    }
  }
})

algo(k_truss).params({
  project: "hdc_ktruss",
  k: 4,
  return_id_uuid: "id"  
}).write({
  file: {
    filename: "4truss.txt"
  }
})

结果：

_id
e--[110]--f
k--[117]--f
k--[119]--l
m--[121]--k
m--[123]--f
m--[126]--l
c--[103]--a
g--[120]--k
g--[125]--m
d--[102]--a
d--[104]--c
d--[107]--f
d--[109]--e
f--[105]--a
f--[106]--d
f--[108]--d
f--[111]--c
f--[124]--g
l--[122]--f

完整返回

CALL algo.k_truss("hdc_ktruss", {
  params: {
    k: 5
  },
  return_params: {}
}) YIELD truss
RETURN truss

exec{
  algo(k_truss).params({
    k: 5
  }) as truss
  return truss
} on hdc_ktruss

结果：

流式返回

CALL algo.k_truss("hdc_ktruss", {
  params: {
    k: 5
  },
  return_params: {
    stream: {}
  }
}) YIELD truss5
FOR node IN pnodes(truss5)
RETURN collect_list(node._id)

exec{
  algo(k_truss).params({
    k: 5
  }).stream() as truss5
 uncollect pnodes(truss5) as node
 return collect(node._id)
} on hdc_ktruss

["d","a","d","c","d","f","d","e","f","a","f","d","f","d","f","c","e","f"]