Conductance

Overview

Conductance is a natural and widely-adopted notion of community goodness and has the ability to detect both non-overlapping and highly overlapping communities for weighted networks. It is particularly useful when studying random walks in graphs.

• Empirical Comparison of Algorithms for Network Community Detection (2010)
• Defining and Evaluating Network Communities based on Ground-truth (2012)

Concepts

Cut

In graph theory, a cut is the partition that divides a graph into two disjoint subsets. The weight of a cut is the sum of weights of the edges crossing the cut.

The example graph is separated into two clusters, with node A, B and C as Cluster Yellow and node D, E, F,and G as Cluster Blue. The cut here crosses edge AE and edge CD, and the weight of the cut is 2.

Conductance

Conductance is a metric to measure the quality of a partition. Given a graph G = (V,E), when it is partitioned into two sets, S and V\S, the conductance is defined as

where δ(S) is defined to be the set of edges of G with exactly one endpoint in set S. The lower the conductance, the better the identified community is. As the example graph above, Cut₂ is better than Cut₁.

Syntax

• Command: algo(conductance)
• Parameters:

Examples

File Writeback

Direct Return

Stream Return