{-# 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