电导度量 (Conductance metric)

术语表

有向: 有向特征。该算法在有向图上定义良好。
有向: 有向特征。该算法忽略图的方向。
有向: 有向特征。该算法不能在有向图上运行。
无向: 无向特征。该算法在无向图上定义良好。
无向: 无向特征。该算法忽略图的无向性。
异构节点: 异构节点完全支持。该算法有能力区分不同类型的节点。
异构节点: 异构节点允许。该算法平等对待所有选定的节点，无论其标签如何。
异构关系: 异构关系完全支持。该算法有能力区分不同类型的关系。
异构关系: 异构关系允许。该算法平等对待所有选定的关系，无论其类型如何。
加权关系: 加权特征。该算法支持将关系属性用作权重，通过 relationshipWeightProperty 配置参数指定。
加权关系: 加权特征。该算法将每个关系视为同等重要，忽略任何关系权重值。
节点属性: 节点属性特征。该算法使用节点属性。

简介

电导率 (Conductance) 是一种用于评估社区发现质量的度量指标。社区 C 中的节点关系连接到 C 内部或 C 外部的节点。电导率是指指向 C 外部的关系数与 C 的关系总数之间的比率。电导率越低，说明社区越“紧密”。

Yang 和 Leskovec 在其论文《基于地面实况定义和评估网络社区》(Defining and Evaluating Network Communities based on Ground-truth) 中指出，电导率是评估真实世界图中实际社区的一个非常好的指标。

该算法的运行时间与图中的关系数量呈线性关系。

语法

本节介绍了在每种执行模式下运行电导率算法所使用的语法。我们正在描述命名图变体的语法。要了解有关通用语法变体的更多信息，请参阅语法概述。

示例 1. 每种模式下的电导率语法

在命名图上以流模式运行电导率。

CALL gds.conductance.stream(
  graphName: String,
  configuration: Map
) YIELD
  community: Integer,
  conductance: Float

表 1. 参数
名称	类型	默认	可选	描述
graphName	字符串	`不适用`	否	存储在目录中的图的名称。
配置	Map	`{}`	是	算法特定配置和/或图过滤配置。

表 2. 配置
名称	类型	默认	可选	描述
nodeLabels	字符串列表	`['*']`	是	使用给定的节点标签过滤命名图。具有任何给定标签的节点都将被包含。
relationshipTypes	字符串列表	`['*']`	是	使用给定的关系类型过滤命名图。具有任何给定类型的关系都将被包含。
concurrency	整数	`4 ^[1]`	是	用于运行算法的并发线程数。
jobId	字符串	`内部生成`	是	可以提供一个 ID 以更轻松地跟踪算法的进度。
logProgress	布尔值	`true`	是	如果禁用，进度百分比将不会被记录。
relationshipWeightProperty	字符串	`null`	是	用作权重的关系属性名称。如果未指定，算法将作为无权重运行。
communityProperty	字符串	`不适用`	否	包含每个节点作为整数的社区 ID 的节点属性。请注意，只有非负的社区 ID 被视为有效，并将计算其电导率。
1. 在 GDS 会话中，默认值为可用处理器的数量。

表 3. 结果
名称	类型	描述
社区	整数	社区 ID。
电导率	浮点数	社区的电导率。

只有非负的社区 ID 对于识别社区才是有效的。社区 ID 为负的节点仅在它们连接到有效社区中的节点时才参与计算，从而对这些有效社区的外部关系计数做出贡献。

示例

以下所有示例应在空数据库中运行。

这些示例将 Cypher 投影作为规范。原生投影将在未来版本中弃用。

在本节中，我们将展示在具体图上运行电导率算法的示例。目的是说明结果的样子，并为如何在实际环境中使用该算法提供指南。我们将在一个由少数节点以特定模式连接的小型社交网络图上进行演示。示例图如下所示

以下 Cypher 语句将在 Neo4j 数据库中创建示例图：

CREATE
  (nAlice:User {name: 'Alice', seed: 42}),
  (nBridget:User {name: 'Bridget', seed: 42}),
  (nCharles:User {name: 'Charles', seed: 42}),
  (nDoug:User {name: 'Doug'}),
  (nMark:User {name: 'Mark'}),
  (nMichael:User {name: 'Michael'}),

  (nAlice)-[:LINK {weight: 1}]->(nBridget),
  (nAlice)-[:LINK {weight: 1}]->(nCharles),
  (nCharles)-[:LINK {weight: 1}]->(nBridget),

  (nAlice)-[:LINK {weight: 5}]->(nDoug),

  (nMark)-[:LINK {weight: 1}]->(nDoug),
  (nMark)-[:LINK {weight: 1}]->(nMichael),
  (nMichael)-[:LINK {weight: 1}]->(nMark);

该图有两个联系紧密的 Users（用户）集群。在这些集群之间有一条单一的边。连接每个组件中节点的这些关系具有一个 weight（权重）属性，该属性决定了关系的强度。

现在我们可以投影该图并将其存储在图目录中。我们将加载 LINK 关系，并将方向设置为 UNDIRECTED（无向），因为这最适合我们用于创建待评估社区的 Louvain 算法。

以下语句将投影图并将其存储在图目录中。

MATCH (source:User)
OPTIONAL MATCH (source)-[r:LINK]->(target:User)
RETURN gds.graph.project(
  'myGraph',
  source,
  target,
  {
    sourceNodeProperties: source { .seed },
    targetNodeProperties: target { .seed },
    relationshipProperties: r { .weight }
  },
  { undirectedRelationshipTypes: ['*'] }
)

现在我们运行 Louvain 算法来将节点划分为可以评估的社区。

以下代码将运行 Louvain 算法并将结果存储在 myGraph 中

CALL gds.louvain.mutate('myGraph', { mutateProperty: 'community', relationshipWeightProperty: 'weight' })
YIELD communityCount

表 4. 结果
communityCount
3

现在，我们的内存图 myGraph 中填充了键为 community 的节点属性，我们可以将其设置为使用电导率进行评估的输入。节点现在的社区分配方式如下

表 5. 社区分配
名称 (name)	社区
"Alice"	1
“Bridget”	3
“Charles”	3
“Doug”	1
“Mark”	5
“Michael”	5

请参阅流节点属性过程，了解如何获取此类分配表。

有关 Louvain 的更多信息，请参阅其算法页面。

流模式

既然我们已经有了社区发现结果，我们就可以根据电导率度量来评估它的好坏。请注意，在本例中，我们使用了关系由关系属性加权的特性。

电导率流过程会返回每个社区的电导率。这使我们能够直接检查结果或在 Cypher 中对其进行后处理，而不会产生任何副作用。

有关流模式的更多详细信息，请参阅流 (Stream)。

以下代码将以 stream 模式运行电导率算法

CALL gds.conductance.stream('myGraph', { communityProperty: 'community', relationshipWeightProperty: 'weight' })
YIELD community, conductance

表 6. 结果
社区	电导率
1	0.23076923076923078
3	0.5
5	0.2

我们可以看到，加权图中电导率最低的社区是社区 5。这意味着 5 是“最紧密”的社区，因为其大部分关系权重都在社区内部。