概述

p-Cohesion算法能识别网络中彼此高度关联的一组参与者（节点），并由内聚子图（Cohesive Subgraph）表示。通过了解各组内的连通性和相互依赖程度，该算法能够帮助深入分析图结构及其影响。

p-Cohesion的概念最初是由S. Morris在大群人相互作用的传染模型中提出的：

• S. Morris, Contagion. The Review of Economic Studies, 67(1), 57–78 (2000)

基本概念

p-Cohesion

关于群体的Cohesion（凝聚力），一个很自然的衡量标准是：与非成员相比，群体内成员之间互相联系的相对概率。令常数p∈(0,1)，p-Cohesion是一个连通子图，其中每个节点至少有占比为p的邻居在该子图中，每个节点在子图外的邻居占比不超过(1−p)。

与其他内聚子图模型相比，p-Cohesion模型具有两个明显的优势：

• p值较大时，p-Cohesion能同时保证内部的凝聚性和外部的稀疏性。
• 在很多场景下，由于图中各节点度的差异，考虑邻居的占比相较于考虑固定的邻居数（比如 k-Core）更为合适。

在下面的示例图中，假设p=0.6，每个节点旁的灰色标签表示该节点在p-cohesion中所需的最小邻居数。

以下分别是包含节点a和节点j的最小（指节点数量）p-cohesion 子图。

嬴图的p-Cohesion算法寻找包含查询节点的近似最小p-cohesion子图，并以节点集的形式返回子图。

特殊说明

• p-Cohesion算法忽略边的方向，按照无向边进行计算。

示例图集

创建示例图集：

// 在空图集中逐行运行以下语句
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"}])
insert().into(@default).edges([{_from:"K", _to:"J"}, {_from:"K", _to:"L"}, {_from:"J", _to:"L"}, {_from:"L", _to:"C"}, {_from:"C", _to:"A"}, {_from:"A", _to:"B"}, {_from:"C", _to:"B"}, {_from:"A", _to:"D"}, {_from:"B", _to:"G"}, {_from:"B", _to:"D"}, {_from:"D", _to:"C"}, {_from:"C", _to:"E"}, {_from:"C", _to:"F"}, {_from:"D", _to:"E"}, {_from:"E", _to:"F"}, {_from:"D", _to:"F"}, {_from:"D", _to:"H"}, {_from:"I", _to:"H"}, {_from:"F", _to:"I"}])

创建HDC图集

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

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

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

参数

算法名：p_cohesion

文件回写

CALL algo.p_cohesion.write("hdc_pcohesion", {
  params: {
    ids: ["A","I"],
    p: 0.7,
    return_id_uuid: "id"
  },
  return_params: {
    file: {
      filename: "cohesion"
    }
  }
})

algo(p_cohesion).params({
  projection: "hdc_pcohesion",
  ids: ["A","I"],
  p: 0.7,
  return_id_uuid: "id"
}).write({
  file: {
    filename: "cohesion"
  }
})

结果：

subgraph contains A: D,F,B,A,E,C,
subgraph contains I: I,D,F,H,B,A,E,C,

统计回写

CALL algo.p_cohesion.write("hdc_pcohesion", {
  params: {
    ids: ["A","I"],
    p: 0.7,
    return_id_uuid: "id"
  },
  return_params: {
    stats: {}
  }
})

algo(p_cohesion).params({
  projection: "hdc_pcohesion",
  ids: ["A","I"],
  p: 0.7,
  return_id_uuid: "id"
}).write({
  stats: {}
})

结果：

统计返回

CALL algo.p_cohesion("hdc_pcohesion", {
  params: {
    ids: ["A","I"],
    p: 0.7
  },
  return_params: {
    stats: {}
  }
}) YIELD s
RETURN s

exec{
  algo(p_cohesion).params({
    ids: ["A","I"],
    p: 0.7
  }).stats() as s
  return s
} on hdc_pcohesion

结果：