com.raphtory.algorithms.generic.motif.ThreeNodeMotifs

ThreeNodeMotifs

ThreeNodeMotifs()

Count occurrences of three-node motifs that a node participates in.

The algorithm works by first counting star motifs, including potential triangles. Then, for each star we send a message to one of the neighbours to identify the potential third edge. Based on the responses, we correct the star counts and count the triangles.

Note

Stars are only counted once as they only appear in the counts for the central vertex. However, triangles appear for each of the 3 vertices, so the count for triangles should be divided by 3 when aggregating results to get motif counts for the whole graph.

Motifs

Stars

• 0: l <- c -> r

• 1: l -> c <- r

• 2: l -> c -> r

• 3: l -> c <-> r

• 4: l <- c <-> r

• 5: l <-> c <-> r

Triangles

(Index of star + third edge)

• 6: 0 + l -> r

• 7: 2 + l <- r

• 8: 3 + l -> r

• 9: 4 + l -> r

• 10: 4 + l <- r

• 11: 5 + l -> r

• 12: 5 + l <-> r

States

motifCounts: Array[Long]

Motif counts stored as an array (see indices above)

Returns

vertex name

Motif 0

Motif 12

name: String

motifCounts(0): Long

motifCounts(12): Long