All Classes Namespaces Files Functions Variables Typedefs Enumerations Enumerator Friends Macros Groups Pages
Public Member Functions | Protected Attributes | List of all members
NetworKit::LocalClusteringCoefficient Class Reference

#include <LocalClusteringCoefficient.h>

Public Member Functions

 LocalClusteringCoefficient (const NetworKit::Graph &G, bool turbo=false)
 Constructs the LocalClusteringCoefficient class for the given Graph G. More...
 
void run () override
 Computes the local clustering coefficient on the graph passed in constructor. More...
 
virtual double maximum () override
 Get the theoretical maximum of centrality score in the given graph. More...
 
- Public Member Functions inherited from NetworKit::Centrality
 Centrality (const Graph &G, bool normalized=false, bool computeEdgeCentrality=false)
 Constructs the Centrality class for the given Graph G. More...
 
virtual ~Centrality ()=default
 Default destructor. More...
 
virtual std::vector< double > scores (bool moveOut=false)
 Get a vector containing the centrality score for each node in the graph. More...
 
virtual std::vector< double > edgeScores ()
 Get a vector containing the edge centrality score for each edge in the graph (where applicable). More...
 
virtual std::vector< std::pair
< node, double > > 
ranking ()
 Get a vector of pairs sorted into descending order. More...
 
virtual double score (node v)
 Get the centrality score of node v calculated by run(). More...
 
virtual double centralization ()
 Compute the centralization of a network with respect to some centrality measure. More...
 
- Public Member Functions inherited from NetworKit::Algorithm
 Algorithm ()
 Constructor to the algorithm base class. More...
 
virtual ~Algorithm ()=default
 Virtual default destructor. More...
 
bool hasFinished () const
 Indicates whether an algorithm has completed computation or not. More...
 
void assureFinished () const
 Assure that the algorithm has been run, throws a std::runtime_error otherwise. More...
 
virtual std::string toString () const
 Returns a string with the algorithm's name and its parameters, if there are any. More...
 
virtual bool isParallel () const
 

Protected Attributes

bool turbo
 
- Protected Attributes inherited from NetworKit::Centrality
const GraphG
 
std::vector< double > scoreData
 
std::vector< double > edgeScoreData
 
bool normalized
 
bool computeEdgeCentrality
 
- Protected Attributes inherited from NetworKit::Algorithm
bool hasRun
 A boolean variable indicating whether an algorithm has finished its computation or not. More...
 

Constructor & Destructor Documentation

NetworKit::LocalClusteringCoefficient::LocalClusteringCoefficient ( const NetworKit::Graph G,
bool  turbo = false 
)

Constructs the LocalClusteringCoefficient class for the given Graph G.

If the local clustering coefficient scores should be normalized, then set normalized to true. The graph may not contain self-loops.

There are two algorithms available. The trivial (parallel) algorithm needs only a small amount of additional memory. The turbo mode adds a (sequential, but fast) pre-processing step using ideas from [0]. This reduces the running time significantly for most graphs. However, the turbo mode needs O(m) additional memory. In practice this should be a bit less than half of the memory that is needed for the graph itself. The turbo mode is particularly effective for graphs with nodes of very high degree and a very skewed degree distribution.

[0] Triangle Listing Algorithms: Back from the Diversion Mark Ortmann and Ulrik Brandes * 2014 Proceedings of the Sixteenth Workshop on Algorithm Engineering and Experiments (ALENEX). 2014, 1-8

Parameters
GThe graph.
turboIf the turbo mode shall be activated. TODO running time

Member Function Documentation

double NetworKit::LocalClusteringCoefficient::maximum ( )
overridevirtual

Get the theoretical maximum of centrality score in the given graph.

Returns
The maximum centrality score.

Reimplemented from NetworKit::Centrality.

void NetworKit::LocalClusteringCoefficient::run ( )
overridevirtual

Computes the local clustering coefficient on the graph passed in constructor.

Implements NetworKit::Centrality.

Member Data Documentation

bool NetworKit::LocalClusteringCoefficient::turbo
protected

The documentation for this class was generated from the following files: