gov.sandia.cognition.graph.community

Class Louvain<NodeNameType>

java.lang.Object

gov.sandia.cognition.graph.community.Louvain<NodeNameType>

Type Parameters:

NodeNameType - The class type for the graph's nodes

@PublicationReference(author="Vincent D Blondel, Jean-Loup Guillaume, Renaud Lambiotte, Etienne Lefebvre",
                      title="Fast unfolding of communities in large networks",
                      type=Journal,
                      year=2008,
                      publication="Journal of Statistical Mechanics: Theory and Experiment")
public class Louvain<NodeNameType>
extends java.lang.Object

This class performs community detection using the Louvain method. Each instance should be used to run Louvain only one time.

Author:

jdwendt

Nested Class Summary

Nested Classes

Modifier and Type	Class and Description
static class	Louvain.LouvainHierarchy<NodeNameType> The return type from running Louvain.

Constructor Summary

Constructors

Constructor and Description
Louvain(DirectedNodeEdgeGraph<NodeNameType> graph) Initializes the internal Louvain datatypes that store the necessaries to run Louvain on the input graph.
Louvain(DirectedNodeEdgeGraph<NodeNameType> graph, int maxNumPasses, double minModularityGain) Initializes the internal Louvain datatypes that store the necessaries to run Louvain on the input graph.

Method Summary

Modifier and Type	Method and Description
void	initialPartition(java.util.Map<NodeNameType,java.lang.Integer> initPart) The input partition will serve as the initial partition for the graph (replacing Louvain's default "each node to its own community" partitioning).
double	modularity() Returns the modularity of the most recent partitioning of the graph
void	setRandomSet(long seed) Initialize the random number generator with the input seed.
Louvain.LouvainHierarchy<NodeNameType>	solveCommunities() Solves for community detection of the graph passed in during the constructor.

Methods inherited from class java.lang.Object

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

Constructor Detail

Louvain

public Louvain(DirectedNodeEdgeGraph<NodeNameType> graph)

Initializes the internal Louvain datatypes that store the necessaries to run Louvain on the input graph.

Parameters:

graph - The graph to execute community detection on

Louvain

public Louvain(DirectedNodeEdgeGraph<NodeNameType> graph,
               int maxNumPasses,
               double minModularityGain)

Initializes the internal Louvain datatypes that store the necessaries to run Louvain on the input graph.

Parameters:

graph - The graph to execute community detection on

maxNumPasses - The maximum number of passes to iterate within each level of the hierarchy

minModularityGain - The minimum the amount modularity must improve on each iteration to continue iterating within each level of the hierarchy.

Method Detail

setRandomSet

public void setRandomSet(long seed)

Initialize the random number generator with the input seed.

Parameters:

seed - The seed for the random number generator

initialPartition

public void initialPartition(java.util.Map<NodeNameType,java.lang.Integer> initPart)

The input partition will serve as the initial partition for the graph (replacing Louvain's default "each node to its own community" partitioning). NOTE: This initial partitioning will be modified by solveCommunities to find a "local best" community detection. Thus nodes assigned to the same community by the input to this method may be separated to different communities by the community detection algorithm.

Parameters:

initPart - The initial partitioning where the key is a node id and the value is a community id. Not all nodes need be assigned.

Throws:

java.lang.IllegalArgumentException - if an input key does not exist in the graph.

modularity

public double modularity()

Returns the modularity of the most recent partitioning of the graph

Returns:

the modularity of the most recent partitioning of the graph

solveCommunities

public Louvain.LouvainHierarchy<NodeNameType> solveCommunities()

Solves for community detection of the graph passed in during the constructor. If this was called previously, the same result will be returned herein. If you want a new random run, create a new instance with the same graph.

Returns:

The hierarchy of the community structure for all nodes.