Modularity

Modularity measures strength of division of a network into communities (modules,clusters). Measures takes values from range \(<-1,1>\). Value close to 1 indicates strong community structure. When \(Q=0\) then the community division is not better than random.

\(Q=\sum_{i=1}^{k}{(e_{ii}-a_i^2)}\)

Where \(k\) is number of communities, \(e_{ii}\) is number of edges that has both ends in community \(i\) and \(a_i\) is number of edges with one end in community \(i\)

For further informations please refer to [lecture] and [Newman].

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 modularity: Double= graph.modularity()
// Modularity value for graph

References:

[lecture]

Carl Kingsford (2009). Modularity, PDF

[Newman]

Newman, M. E., & Girvan, M. (2004). Finding and evaluating community structure in networks. Physical review E, 69(2), 026113. PDF