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

Computes k-core decomposition of a graph. More...

#include <CoreDecomposition.h>

Public Member Functions

 CoreDecomposition (const Graph &G, bool normalized=false, bool enforceBucketQueueAlgorithm=false, bool storeNodeOrder=false)
 Create CoreDecomposition class for graph G. More...
 
void run ()
 Perform k-core decomposition of graph passed in constructor. More...
 
Cover getCover () const
 Get the k-cores as a graph cover object. More...
 
Partition getPartition () const
 Get the k-shells as a partition object. More...
 
index maxCoreNumber () const
 Get maximum core number. More...
 
double maximum ()
 Get the theoretical maximum of centrality score in the given graph. More...
 
const std::vector< node > & getNodeOrder () const
 Get the node order. More...
 
virtual bool isParallel () const
 The algorithm ParK can run in parallel under certain conditions, the bucket PQ based one cannot. 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...
 

Additional Inherited Members

- 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...
 

Detailed Description

Computes k-core decomposition of a graph.

Constructor & Destructor Documentation

NetworKit::CoreDecomposition::CoreDecomposition ( const Graph G,
bool  normalized = false,
bool  enforceBucketQueueAlgorithm = false,
bool  storeNodeOrder = false 
)

Create CoreDecomposition class for graph G.

The graph may not contain self-loops.

Contains the parallel algorithm by Dasari, N.S.; Desh, R.; Zubair, M., "ParK: An efficient algorithm for k-core decomposition on multicore processors," in Big Data (Big Data), * 2014 IEEE International Conference.

TODO complexity?

Parameters
GThe graph.
normalizedIf set to true the scores are normalized in the interval [0,1].
enforceBucketQueueAlgorithmIf set to true, uses a bucket priority queue data structure. This it is generally slower than ParK but may be more flexible. TODO check
storeNodeOrderIf set to true, the order of the nodes in ascending order of the cores is stored and can later be returned using getNodeOrder(). Enforces the sequential bucket priority queue algorithm.

Member Function Documentation

Cover NetworKit::CoreDecomposition::getCover ( ) const

Get the k-cores as a graph cover object.

Returns
the k-cores as a Cover
const std::vector< node > & NetworKit::CoreDecomposition::getNodeOrder ( ) const

Get the node order.

This is only possible when storeNodeOrder was set.

Returns
The nodes sorted by increasing core number.
Partition NetworKit::CoreDecomposition::getPartition ( ) const

Get the k-shells as a partition object.

Returns
the k-shells as a Partition
virtual bool NetworKit::CoreDecomposition::isParallel ( ) const
inlinevirtual

The algorithm ParK can run in parallel under certain conditions, the bucket PQ based one cannot.

Reimplemented from NetworKit::Algorithm.

index NetworKit::CoreDecomposition::maxCoreNumber ( ) const

Get maximum core number.

Returns
The maximum core number
double NetworKit::CoreDecomposition::maximum ( )
virtual

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

Returns
The theoretical maximum centrality score.

Reimplemented from NetworKit::Centrality.

void NetworKit::CoreDecomposition::run ( )
virtual

Perform k-core decomposition of graph passed in constructor.

Implements NetworKit::Centrality.


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