gov.sandia.cognition.graph.community

Class CommunityMetrics

java.lang.Object

gov.sandia.cognition.graph.community.CommunityMetrics

public class CommunityMetrics
extends java.lang.Object

This class stores several static methods for computing metrics specific to a graph and a set of communities. Unlike the GraphMetrics class, this does not preserve values for the community structure nor the graph internally -- each method is a separate call.

Author:

jdwendt

Constructor Summary

Constructors

Constructor and Description
CommunityMetrics()

Method Summary

Modifier and Type	Method and Description
static <NodeNameType> double	computeConductance(DirectedNodeEdgeGraph<NodeNameType> graph, java.util.Set<NodeNameType> community)
static <NodeNameType> double	computeGraphPermanance(DirectedNodeEdgeGraph<NodeNameType> graph, GraphMetrics<NodeNameType> metrics, NodePartitioning<NodeNameType> partitions) Computes the average permanence for the partitioning of the entire graph
static <NodeNameType> double	computeModularity(DirectedNodeEdgeGraph<NodeNameType> graph, NodePartitioning<NodeNameType> communities) Computes the modularity of the input graph into the input set of communities.
static <NodeNameType> double	computeModularity(DirectedNodeEdgeGraph<NodeNameType> graph, java.util.Set<java.util.Set<NodeNameType>> communities) Computes the modularity of the input graph into the input set of communities.
static <NodeNameType> double	computeModularity(NodePartitioning<NodeNameType> communities, GraphMetrics<NodeNameType> graphMetrics)
static <NodeNameType> double	computeModularity(java.util.Set<java.util.Set<NodeNameType>> communities, GraphMetrics<NodeNameType> graphMetrics) Computes the modularity of the graph (whose metrics were passed in) into the input set of communities.
static <NodeNameType> double	computeOneNodePermanence(GraphMetrics<NodeNameType> metrics, NodePartitioning<NodeNameType> partitions, NodeNameType node, DirectedNodeEdgeGraph<NodeNameType> graph)
static <NodeNameType> double	computeOneNodePermanenceById(GraphMetrics<NodeNameType> metrics, NodePartitioning<NodeNameType> partitions, int nodeId, DirectedNodeEdgeGraph<NodeNameType> graph) Computes the permanence for one node in the graph.

Methods inherited from class java.lang.Object

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

Constructor Detail

CommunityMetrics

public CommunityMetrics()

Method Detail

computeModularity

public static <NodeNameType> double computeModularity(DirectedNodeEdgeGraph<NodeNameType> graph,
                                                      java.util.Set<java.util.Set<NodeNameType>> communities)

Computes the modularity of the input graph into the input set of communities. NOTE: Modularity is intended for exclusive community detection (every node is in exactly one community), but this code does not check that the communities are constituted correctly. Therefore, if you insert garbage, be prepared for bad results!

Type Parameters:

NodeNameType -

Parameters:

graph - The graph that has been partitioned

communities - The partitions created on the input graph

Returns:

The modularity score

computeModularity

public static <NodeNameType> double computeModularity(java.util.Set<java.util.Set<NodeNameType>> communities,
                                                      GraphMetrics<NodeNameType> graphMetrics)

Computes the modularity of the graph (whose metrics were passed in) into the input set of communities. NOTE: Modularity is intended for exclusive community detection (every node is in exactly one community), but this code does not check that the communities are constituted correctly. Therefore, if you insert garbage, be prepared for bad results!

Type Parameters:

NodeNameType -

Parameters:

communities - The partitions created on the input graph

graphMetrics - The complete set of metrics for the partitioned graph

Returns:

The modularity score

computeModularity

public static <NodeNameType> double computeModularity(DirectedNodeEdgeGraph<NodeNameType> graph,
                                                      NodePartitioning<NodeNameType> communities)

Computes the modularity of the input graph into the input set of communities. NOTE: Modularity is intended for exclusive community detection (every node is in exactly one community), but this code does not check that the communities are constituted correctly. Therefore, if you insert garbage, be prepared for bad results!

Type Parameters:

NodeNameType -

Parameters:

graph - The graph that has been partitioned

communities - The partitions created on the input graph

Returns:

The modularity score

computeModularity

@PublicationReference(author="Wikipedia",
                      title="Modularity (networks)",
                      type=WebPage,
                      year=2016,
                      url="https://en.wikipedia.org/wiki/Modularity_(networks)")
public static <NodeNameType> double computeModularity(NodePartitioning<NodeNameType> communities,
                                                                                                                                                                                                                                                                                                           GraphMetrics<NodeNameType> graphMetrics)

computeConductance

@PublicationReference(author="Wikipedia",
                      title="Conductance (graph)",
                      type=WebPage,
                      year=2016,
                      url="https://en.wikipedia.org/wiki/Conductance_(graph)")
public static <NodeNameType> double computeConductance(DirectedNodeEdgeGraph<NodeNameType> graph,
                                                                                                                                                                                                                                                                                                        java.util.Set<NodeNameType> community)

computeOneNodePermanence

@PublicationReference(author="Tanmoy Chakraborty, Sriram Srinivasan, Niloy Ganguly, Animesh Mukherjee, and Sanjukta Bhowmick",
                      title="On the permanence of vertices in network communities",
                      year=2014,
                      type=Conference)
public static <NodeNameType> double computeOneNodePermanence(GraphMetrics<NodeNameType> metrics,
                                                                                                                                                                                                                                                                                                                                                        NodePartitioning<NodeNameType> partitions,
                                                                                                                                                                                                                                                                                                                                                        NodeNameType node,
                                                                                                                                                                                                                                                                                                                                                        DirectedNodeEdgeGraph<NodeNameType> graph)

computeOneNodePermanenceById

public static <NodeNameType> double computeOneNodePermanenceById(GraphMetrics<NodeNameType> metrics,
                                                                 NodePartitioning<NodeNameType> partitions,
                                                                 int nodeId,
                                                                 DirectedNodeEdgeGraph<NodeNameType> graph)

Computes the permanence for one node in the graph.

Type Parameters:

NodeNameType -

Parameters:

metrics - The graph metrics object to be used herein

partitions - The partitioning on the graph

nodeId - The node whose permanence is requested

graph - The graph being partitioned

Returns:

the permanence for the input node

computeGraphPermanance

public static <NodeNameType> double computeGraphPermanance(DirectedNodeEdgeGraph<NodeNameType> graph,
                                                           GraphMetrics<NodeNameType> metrics,
                                                           NodePartitioning<NodeNameType> partitions)

Computes the average permanence for the partitioning of the entire graph

Type Parameters:

NodeNameType -

Parameters:

graph - The graph to partition

metrics - The metrics on that graph

partitions - The partitioning of the graph

Returns:

the average permanence for the partitioning