ClusteringCoefficient.hs

{-# LANGUAGE TypeFamilies, EmptyDataDecls, TypeOperators, FlexibleInstances, MultiParamTypeClasses, FlexibleContexts #-}
-- | 
-- Module    : GraphHammer.ClusteringCoefficient
-- Copyright : (C) 2013 Parallel Scientific Labs, LLC.
-- License   : GPLv2
-- Stability : unstable
--
-- Clustering coefficient computation analysis, i.e. for each node of the graph calculate clustering coefficient.
--
-- /Clustering coefficient/ of a node is the ratio of the number of connections in the neighborhood of
-- a node and the number of connections if the neighborhood was fully connected. Here neighborhood of 
-- node A means the nodes that are --  connected to A but does not include A itself. Note that a fully
-- connected group of `n` nodes has `n*(n-1)\/2` connections, and the number of connection in the fully 
-- connected group is the "GraphHammer.TriangleCount" of the node. 
--
-- The clustering coefficient is used as a measure on importantness of the node in the graph.
--
-- Full featured support for the Clustering Coeffient program is not
-- ready at the moment, so clustering coefficient is currently disabled.
-- This program is used as a milestone for implementing additional
-- features in the GraphHammer.
module GraphHammer.ClusteringCoefficient(
	  ClusteringCoefficient(..)
	, clusteringCoefficient
	) where

import GraphHammer
import GraphHammer.TriangleCount
import GraphHammer.VertexDegree

-- | ClusteringCoefficient analysis tag
data ClusteringCoefficient = ClusteringCoefficient

type instance RequiredAnalyses ClusteringCoefficient = TriangleCount :. VertexDegree :. Nil

-- | ClusteringCoefficient analysis:
-- 'GraphHammerTriangleCount.triangleCount' \/ ('GraphHammer.VertexDegree.vertexDegree'*('GraphHammer.VertexDegree.vertexDegree'-1)/2)
clusteringCoefficient :: (EnabledAnalysis ClusteringCoefficient wholeset
                         , EnabledAnalysis TriangleCount wholeset
                         , EnabledAnalysis VertexDegree wholeset)
                      => Analysis (ClusteringCoefficient :. TriangleCount :. VertexDegree :. Nil) wholeset
clusteringCoefficient = derivedAnalysis triangleCount ClusteringCoefficient $ \cc from to -> do
	let update index = do
		tc <- getAnalysisResult TriangleCount index
		deg <- getAnalysisResult VertexDegree index
		putAnalysisResult cc index (divV (tc *. cst 100) (deg *. (deg -. cst 1)))
	update from
	update to