Conductance

Overview

Conductance is a metric used to evaluate the quality of a community or cluster within a graph. Studies have shown that scoring functions that are based on conductance best capture the structure of ground-truth communities.

• J. Yang, J. Leskovec, Defining and Evaluating Network Communities based on Ground-truth (2012)

Concepts

Conductance

Intuitively, a good community should have strong internal connections and only weak connections to the rest of the graph.

For a community C and its complement C', the conductance of C is defined as the ratio of the cut size (the number of edges crossing between C and C') to the minimum volume of C and C' (i.e., the sum of degrees of nodes within each set):

In the example below, the community C is connected to the rest of the graph with three edges, i.e., cut(C, C') = 3. The conductance of C is then cond(C) = 3/min(19, 17) = 3/17 = 0.176471.

If we adjust the cut to include one more node in C, the conductance becomes cond(C) = 3/min(21, 15) = 3/15 = 0.2.

A small conductance value is desirable in community detection because it indicates a dense community with relatively few edges connecting to the outside. Conversely, a large conductance value means the community is loosely connected internally and has many edges reaching nodes outside the community.

Example Graph

GQL
INSERT (A:default {_id: "A", community_id: 1}), (B:default {_id: "B", community_id: 1}),
       (C:default {_id: "C", community_id: 1}), (D:default {_id: "D", community_id: 2}),
       (E:default {_id: "E", community_id: 2}), (F:default {_id: "F", community_id: 2}),
       (G:default {_id: "G", community_id: 1}), (H:default {_id: "H", community_id: 3}),
       (I:default {_id: "I", community_id: 3}), (J:default {_id: "J", community_id: 3}),
       (K:default {_id: "K", community_id: 3}),
       (A)-[:default]->(B), (A)-[:default]->(C),
       (A)-[:default]->(D), (A)-[:default]->(E),
       (A)-[:default]->(G), (D)-[:default]->(E),
       (D)-[:default]->(F), (E)-[:default]->(F),
       (G)-[:default]->(D), (G)-[:default]->(H),
       (H)-[:default]->(K), (I)-[:default]->(H),
       (I)-[:default]->(J), (J)-[:default]->(D),
       (J)-[:default]->(K)

Parameters

Run Mode

Returns:

GQL
CALL algo.conductance({
  communityProperty: "community_id"
}) YIELD community, conductance, volume, cut

Result:

Stream Mode

Returns the same columns as run mode, streamed for memory efficiency.

GQL
CALL algo.conductance.stream({
  communityProperty: "community_id"
}) YIELD community, conductance
RETURN community, conductance

Result:

Stats Mode

Returns:

GQL
CALL algo.conductance.stats({
  communityProperty: "community_id"
}) YIELD nodeCount, communityCount, avgConductance, minConductance, maxConductance

Result: