Common Neighbours

Common Neighbours measure is defined as number of common neighbours of two given vertices.

\(CN(x,y)=|N(x)\cap N(y)|\)

Where \(N(x)\) is set of neighbours of vertex \(x\)

For further informations please refer to [Newman].

For memory consumption optimization, informations about neighbours are held in memory efficient implementations of collections available in fastutil library.

import ml.sparkling.graph.operators.OperatorsDSL._
import org.apache.spark.SparkContext
import org.apache.spark.graphx.Graph

implicit ctx:SparkContext=???
// initialize your SparkContext as implicit value
val graph =???
// load your graph (for example using Graph loading API)

val commonNeighbours: Graph[_, Int] = graph.commonNeighbours()
// Graph where each edge is associated with number of common neighbours of vertices on edge

You can also compute common neighbours for graph treated as undirected one:

import ml.sparkling.graph.operators.OperatorsDSL._
import org.apache.spark.SparkContext
import org.apache.spark.graphx.Graph

implicit ctx:SparkContext=???
// initialize your SparkContext as implicit value
val graph =???
// load your graph (for example using Graph loading API)

val commonNeighbours: Graph[_, Int] = graph.commonNeighbours(treatAsUndirected=true)
// raph where each edge is associated with number of common neighbours of vertices on edge where edges are treated as undirected

References:

[Newman]

Newman, M. E. J. (2001). Clustering and preferential attachment in growing networks. pages1–13, PDF