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 inlcude 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. This suggests that the community is not tightly knit.

Example Graph

Run the following statements on an empty graph to define its structure and insert data:

GQLUQL
ALTER NODE default ADD PROPERTY {
  community_id uint32
};
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);

Creating HDC Graph

To load the entire graph to the HDC server hdc-server-1 as my_hdc_graph:

GQLUQL
CREATE HDC GRAPH my_hdc_graph ON "hdc-server-1" OPTIONS {
  nodes: {"*": ["*"]},
  edges: {"*": ["*"]},
  direction: "undirected",
  load_id: true,
  update: "static"
}

Parameters

Algorithm name: conductance

File Writeback

GQLUQL
CALL algo.conductance.write("my_hdc_graph", {
   community_property: "community_id"
}, {
  file: {
    filename: "conductance"
  }
})

File: conductance
community,conductance
2,0.4
1,0.4
3,0.2

Full Return

GQLUQL
CALL algo.conductance.run("my_hdc_graph", {
  community_property: "community_id"
}) YIELD r
RETURN r

Result:

Stream Return

GQLUQL
CALL algo.conductance.stream("my_hdc_graph", {
  community_property: "community_id"
}) YIELD r
RETURN r

Result: