9.3.4. The Balanced Triads algorithm

This section describes the Balanced Triads algorithm in the Neo4j Labs Graph Algorithms library.

Balanced Triads algorithm is used to evaluate structural balance of the graph.

It is based on the Balance Theory proposed by Fritz Heider in 1958. Unlike other algorithms where there are only positive relationships available, balance theory differentiates between positive and negative relationships. Certain structures between individuals and objects are perceived as balanced whereas others are not. In general balanced structures are preferred over imbalanced ones.

The Balanced Triads algorithm was developed by the Neo4j Labs team and is not officially supported.

This section includes:

9.3.4.1. History and explanation

Balanced triads is an algorithm that counts the number of balanced and unbalanced triads a node is member of. It uses Signed graph model to differentiate between positive and negative relationships using the sign of the weight.

Determining if the triad is balanced is simple math:

+ + + = Balanced - + - = Balanced - + + = Unbalanced - - - = Unbalanced

9.3.4.2. Use-cases - when to use the Balance Triads algorithm

9.3.4.3. Balanced Triads algorithm sample

This sample will explain the Balanced Triads algorithm, using a simple graph:

balanced triads

The following will create a sample graph: 

MERGE (a:Person {name:'Anna'})
MERGE (b:Person {name:'Dolores'})
MERGE (c:Person {name:'Matt'})
MERGE (d:Person {name:'Larry'})
MERGE (e:Person {name:'Stefan'})
MERGE (f:Person {name:'Sophia'})
MERGE (g:Person {name:'Robin'})
MERGE (a)-[:TYPE {weight:1.0}]->(b)
MERGE (a)-[:TYPE {weight:-1.0}]->(c)
MERGE (a)-[:TYPE {weight:1.0}]->(d)
MERGE (a)-[:TYPE {weight:-1.0}]->(e)
MERGE (a)-[:TYPE {weight:1.0}]->(f)
MERGE (a)-[:TYPE {weight:-1.0}]->(g)
MERGE (b)-[:TYPE {weight:-1.0}]->(c)
MERGE (c)-[:TYPE {weight:1.0}]->(d)
MERGE (d)-[:TYPE {weight:-1.0}]->(e)
MERGE (e)-[:TYPE {weight:1.0}]->(f)
MERGE (f)-[:TYPE {weight:-1.0}]->(g)
MERGE (g)-[:TYPE {weight:1.0}]->(b);

The following will count the number of balanced and unbalanced triads that a node is a member of, and return a stream with nodeId, balanced and unbalanced

call algo.balancedTriads.stream('Person','TYPE',{weightProperty:'weight'})
YIELD nodeId, balanced, unbalanced
RETURN algo.asNode(nodeId).name as person,balanced,unbalanced
ORDER BY balanced + unbalanced DESC
LIMIT 10

The following will count the number of balanced and unbalanced triads that a node is member of, and write it back. It will return the total balanced triads and unbalanced triads count of the given graph: 

CALL algo.balancedTriads('Person', 'TYPE', {weightProperty:'weight'})
YIELD loadMillis, computeMillis, writeMillis, nodeCount, balancedTriadCount, unbalancedTriadCount;

Table 9.51. Results
nodeId balanced unbalanced

Anna

3

3

Matt

1

1

Larry

1

1

Stefan

1

1

Sophia

1

1

Dolores

1

1

Anna is a member of six triads out of which three are balanced and three are unbalanced. All others are each members of one balanced and one unbalanced triad or triangle.

9.3.4.4. Syntax

The following will count the number of balanced and unbalanced triads that a node is a member of, and return a stream with nodeId, balanced and 'unbalanced': 

CALL algo.balancedTriads.stream(label:String, relationship:String, {concurrency:4})
YIELD nodeId, balanced, unbalanced

Table 9.52. Parameters
Name Type Default Optional Description

label

string

null

yes

The label to load from the graph. If null, load all nodes.

relationship

string

null

yes

The relationship type to load from the graph. If null, load all relationships.

weightProperty

string

null

no

The property name that contains weight. If weight is positive, algorithm treats the relationship as positive. With a negative weight, relationship is treated as negative. Must be numeric.

concurrency

int

available CPUs

yes

The number of concurrent threads used for running the algorithm. Also provides the default value for 'readConcurrency'.

readConcurrency

int

value of 'concurrency'

yes

The number of concurrent threads used for reading the graph.

Table 9.53. Results
Name Type Description

nodeId

int

The ID of node.

balanced

int

The number of balanced triads a node is member of.

unbalanced

int

The number of unbalanced a node is member of.

The following will count the number of balanced and unbalanced triads that a node is member of, and write it back. It will return the total balanced triads and unbalanced triads count of the given graph: 

CALL algo.balancedTriads(label:String, relationship:String,
  {concurrency:4, write:true, weightProperty:'weight', balancedProperty:'balanced', unbalancedProperty:'unbalanced'})
YIELD loadMillis, computeMillis, writeMillis, nodeCount, balancedTriadCount, unbalancedTriadCount

Table 9.54. Parameters
Name Type Default Optional Description

label

string

null

yes

The label to load from the graph. If null, load all nodes.

relationship

string

null

yes

The relationship type to load from the graph. If null, load all relationships.

concurrency

int

available CPUs

yes

The number of concurrent threads used for running the algorithm. Also provides the default value for 'readConcurrency' and 'writeConcurrency'.

readConcurrency

int

value of 'concurrency'

yes

The number of concurrent threads used for reading the graph.

writeConcurrency

int

value of 'concurrency'

yes

The number of concurrent threads used for writing the result.

unbalancedProperty

string

'unbalanced'

yes

The property name written back to the count of unbalanced triads a node is member of.

write

boolean

true

yes

Specifies if the result should be written back as a node property.

Table 9.55. Results
Name Type Description

loadMillis

int

Milliseconds for loading data

computeMillis

int

Milliseconds for running the algorithm

writeMillis

int

Milliseconds for writing result data back

postProcessingMillis

int

Milliseconds for computing percentiles and community count

nodeCount

int

The number of nodes considered

balancedTriadCount

int

The number of balanced triads in the given graph

unbalancedTriadCount

int

The number of unbalanced triads in the given graph

p1

double

The 1 percentile of number of balanced triads.

p5

double

The 5 percentile of number of balanced triads.

p10

double

The 10 percentile of number of balanced triads.

p25

double

The 25 percentile of number of balanced triads.

p50

double

The 50 percentile of number of balanced triads.

p75

double

The 75 percentile of number of balanced triads.

p90

double

The 90 percentile of number of balanced triads.

p95

double

The 95 percentile of number of balanced triads.

p99

double

The 99 percentile of number of balanced triads.

p100

double

The 100 percentile of number of balanced triads.

write

boolean

Specifies if the result was written back as a node property

balancedProperty

string

The property name the number of balanced triads is written to

unbalancedProperty

string

The property name the number of unbalanced triads is written to

9.3.4.5. Graph type support

The Balanced Triads algorithm support the following graph type:

  • ✓ undirected, weighted