org.graphstream.algorithm.measure

Class SurpriseMeasure

java.lang.Object

org.graphstream.algorithm.measure.SurpriseMeasure

All Implemented Interfaces:

Algorithm

public class SurpriseMeasure
extends java.lang.Object
implements Algorithm

Surprise measure. Description from Wikipedia : Surprise (denoted S) is a measure of community structure in complex networks. The name Surprise derives from the fact that its maximization finds the most surprising partition into communities of the network, that is, the most unlikely one. S accurately evaluates, in a global manner, the quality of a partition using a cumulative hypergeometric distribution.

Scientific Reference:

Rodrigo Aldecoa, Ignacio Marin, "Deciphering Network Community Structure by Surprise", 2011, PLoS ONE 6(9)

Field Summary

Fields

Modifier and Type	Field and Description
static java.lang.String	ATTRIBUTE Default attribute key where the result of the algorithm, a double value, is stored.

Constructor Summary

Constructors

Constructor and Description
SurpriseMeasure() Default constructor.
SurpriseMeasure(java.lang.String communityAttributeKey) Constructor allowing to set the node attribute key containing index of organizations.
SurpriseMeasure(java.lang.String communityAttributeKey, java.lang.String surpriseAttributeKey) Same as SurpriseMeasure(String) but allowing to set the graph attribute that will contain the result of the computation.

Method Summary

Modifier and Type	Method and Description
static double	binomialCoefficient(double n, double r) Helper to compute the binomial coefficient.
void	compute() Run the algorithm.
static double	cumulativeHypergeometricDistribution(double xStart, double xEnd, double N, double n, double k) Helper to compute the cumulative hypergeometric distribution.
java.lang.String	defaultResult()
double	getSurprise() Get the last computed surprise value contained in the graph.
static double	hypergeometricDistribution(double x, double N, double n, double k) Helper to compute the hypergeometric distribution.
void	init(org.graphstream.graph.Graph graph) Initialization of the algorithm.
void	setCommunityAttributeKey(java.lang.String communityAttributeKey)

Methods inherited from class java.lang.Object

equals, getClass, hashCode, notify, notifyAll, toString, wait, wait, wait

Field Detail

ATTRIBUTE

public static final java.lang.String ATTRIBUTE

Default attribute key where the result of the algorithm, a double value, is stored.

See Also:

Constant Field Values

Constructor Detail

SurpriseMeasure

public SurpriseMeasure()

Default constructor.

SurpriseMeasure

public SurpriseMeasure(java.lang.String communityAttributeKey)

Constructor allowing to set the node attribute key containing index of organizations.

Parameters:

communityAttributeKey - key attribute of organizations

SurpriseMeasure

public SurpriseMeasure(java.lang.String communityAttributeKey,
                       java.lang.String surpriseAttributeKey)

Same as SurpriseMeasure(String) but allowing to set the graph attribute that will contain the result of the computation.

Parameters:

communityAttributeKey - community attribute key

surpriseAttributeKey - surprise attribute key

Method Detail

init

public void init(org.graphstream.graph.Graph graph)

Description copied from interface: Algorithm

Initialization of the algorithm. This method has to be called before the Algorithm.compute() method to initialize or reset the algorithm according to the new given graph.

Specified by:

init in interface Algorithm

Parameters:

graph - The graph this algorithm is using.

compute

public void compute()

Description copied from interface: Algorithm

Run the algorithm. The Algorithm.init(Graph) method has to be called before computing.

Specified by:

compute in interface Algorithm

See Also:

Algorithm.init(Graph)

defaultResult

public java.lang.String defaultResult()

setCommunityAttributeKey

public void setCommunityAttributeKey(java.lang.String communityAttributeKey)

getSurprise

public double getSurprise()

Get the last computed surprise value contained in the graph.

Returns:

surprise value

binomialCoefficient

public static double binomialCoefficient(double n,
                                         double r)

Helper to compute the binomial coefficient.

Parameters:

n - number of elements in set

r - number of elements

Returns:

the binomial coefficient

hypergeometricDistribution

public static double hypergeometricDistribution(double x,
                                                double N,
                                                double n,
                                                double k)

Helper to compute the hypergeometric distribution. See this page for more information about this function.

Parameters:

x - x

N - N

n - n

k - k

Returns:

hypergeometric Distribution

cumulativeHypergeometricDistribution

public static double cumulativeHypergeometricDistribution(double xStart,
                                                          double xEnd,
                                                          double N,
                                                          double n,
                                                          double k)

Helper to compute the cumulative hypergeometric distribution. See this page for more information about this function.

Parameters:

xStart - xStart

xEnd - xEnd

N - N

n - n

k - k

Returns:

Cumulative Hypergeometric Distribution