org.graphstream.algorithm.measure

Class Modularity

java.lang.Object

org.graphstream.stream.SinkAdapter

org.graphstream.algorithm.measure.CommunityMeasure

org.graphstream.algorithm.measure.Modularity

All Implemented Interfaces:

Algorithm, DynamicAlgorithm, org.graphstream.stream.AttributeSink, org.graphstream.stream.ElementSink, org.graphstream.stream.Sink

public class Modularity
extends CommunityMeasure

Computes and updates the modularity of a given graph as it evolves.

Author:

Yoann Pigné, Guillaume-Jean Herbiet

Scientific Reference :

M. E. Newman and M. Girvan, “Finding and Evaluating Community Structure in Networks,” Physical Review E (Statistical, Nonlinear, and Soft Matter Physics), vol. 69, no. 2, pp. 026 113+, Feb 2004.

Constructor Summary

Constructors

Constructor and Description
Modularity() New modularity algorithm using the default marker for communities and no weight on edges.
Modularity(String marker) New modularity algorithm with a given marker for communities and no weight on edges.
Modularity(String marker, String weightMarker) New weighted modularity algorithm with a given marker for communities and the given weightMarker for edge weights.

Method Summary

Methods

Modifier and Type	Method and Description
void	compute() Run the algorithm.
void	setWeightMarker(String weightMarker) Enables weighted extension of the modularity using the given weightMarker for edge weights.

Methods inherited from class org.graphstream.algorithm.measure.CommunityMeasure

edgeAdded, edgeRemoved, getLastComputedValue, getMeasure, graphCleared, init, nodeAdded, nodeAttributeAdded, nodeAttributeChanged, nodeRemoved, terminate

Methods inherited from class org.graphstream.stream.SinkAdapter

edgeAttributeAdded, edgeAttributeChanged, edgeAttributeRemoved, graphAttributeAdded, graphAttributeChanged, graphAttributeRemoved, nodeAttributeRemoved, stepBegins

Methods inherited from class java.lang.Object

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

Constructor Detail

Modularity

public Modularity()

New modularity algorithm using the default marker for communities and no weight on edges.

Modularity

public Modularity(String marker)

New modularity algorithm with a given marker for communities and no weight on edges.

Parameters:

marker - name of the attribute marking the communities.

Modularity

public Modularity(String marker,
          String weightMarker)

New weighted modularity algorithm with a given marker for communities and the given weightMarker for edge weights.

Parameters:

marker - name of the attribute marking the communities.

weightMarker - name of the attribute marking the weight of edges.

Method Detail

setWeightMarker

public void setWeightMarker(String weightMarker)

Enables weighted extension of the modularity using the given weightMarker for edge weights.

Parameters:

weightMarker - name of the attribute marking the weight of edges.

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

Specified by:

compute in class CommunityMeasure

See Also:

Algorithm.init(Graph)

Computational Complexity :

O(n+m!+m!k)