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

#include <TopCloseness.h>

Public Member Functions

 TopCloseness (const Graph &G, count k=1, bool first_heu=true, bool sec_heu=true)
 Finds the top k nodes with highest closeness centrality faster than computing it for all nodes, based on "Computing Top-k Closeness Centrality Faster in Unweighted Graphs", Bergamini et al., ALENEX16. More...
 
void run ()
 Computes top-k closeness on the graph passed in the constructor. More...
 
std::vector< nodetopkNodesList ()
 Returns a list with the k nodes with highest closeness. More...
 
std::vector< edgeweighttopkScoresList ()
 Returns a list with the scores of the k nodes with highest closeness. 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 Member Functions

void init ()
 
double BFScut (node v, double x, bool *visited, count *distances, node *pred, count *visEdges)
 
void computelBound1 (std::vector< double > &S)
 
void BFSbound (node x, std::vector< double > &S, count *visEdges, const std::vector< bool > &toAnalyze)
 
void computeReachable ()
 
void computeReachableNodesUndir ()
 
void computeReachableNodesDir ()
 

Protected Attributes

Graph G
 
count n
 
count k
 
bool first_heu
 
bool sec_heu
 
std::vector< nodetopk
 
count visEdges = 0
 
count n_op = 0
 
std::vector< std::vector< node > > levels
 
std::vector< countnodesPerLev
 
count nLevs = 0
 
std::vector< edgeweighttopkScores
 
std::vector< countmaxlevel
 
std::vector< countmaxlevelSize
 
std::vector< std::vector< count > > subtree
 
std::vector< double > farness
 
std::vector< countreachL
 
std::vector< countreachU
 
std::vector< countcomponent
 
- 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::TopCloseness::TopCloseness ( const Graph G,
count  k = 1,
bool  first_heu = true,
bool  sec_heu = true 
)

Finds the top k nodes with highest closeness centrality faster than computing it for all nodes, based on "Computing Top-k Closeness Centrality Faster in Unweighted Graphs", Bergamini et al., ALENEX16.

The algorithms is based on two independent heuristics, described in the referenced paper. We recommend to use first_heu = true and second_heu = false for complex networks and first_heu = true and second_heu = true for street networks or networks with large diameters. Notice that the worst case running time of the algorithm is O(nm), where n is the number of nodes and m is the number of edges. However, for most networks the empirical running time is O(m).

Parameters
GAn unweighted graph.
kNumber of nodes with highest closeness that have to be found. For example, if k = 10, the top 10 nodes with highest closeness will be computed.
first_heuIf true, the neighborhood-based lower bound is computed and nodes are sorted according to it. If false, nodes are simply sorted by degree.
sec_heuIf true, the BFSbound is re-computed at each iteration. If false, BFScut is used. @

Member Function Documentation

void NetworKit::TopCloseness::BFSbound ( node  x,
std::vector< double > &  S,
count visEdges,
const std::vector< bool > &  toAnalyze 
)
protected
double NetworKit::TopCloseness::BFScut ( node  v,
double  x,
bool *  visited,
count distances,
node pred,
count visEdges 
)
protected
void NetworKit::TopCloseness::computelBound1 ( std::vector< double > &  S)
protected
void NetworKit::TopCloseness::computeReachable ( )
protected
void NetworKit::TopCloseness::computeReachableNodesDir ( )
protected
void NetworKit::TopCloseness::computeReachableNodesUndir ( )
protected
void NetworKit::TopCloseness::init ( )
protected
void NetworKit::TopCloseness::run ( )
virtual

Computes top-k closeness on the graph passed in the constructor.

Implements NetworKit::Algorithm.

std::vector< node > NetworKit::TopCloseness::topkNodesList ( )
inline

Returns a list with the k nodes with highest closeness.

std::vector< edgeweight > NetworKit::TopCloseness::topkScoresList ( )
inline

Returns a list with the scores of the k nodes with highest closeness.

Member Data Documentation

std::vector<count> NetworKit::TopCloseness::component
protected
std::vector<double> NetworKit::TopCloseness::farness
protected
bool NetworKit::TopCloseness::first_heu
protected
Graph NetworKit::TopCloseness::G
protected
count NetworKit::TopCloseness::k
protected
std::vector<std::vector<node> > NetworKit::TopCloseness::levels
protected
std::vector<count> NetworKit::TopCloseness::maxlevel
protected
std::vector<count> NetworKit::TopCloseness::maxlevelSize
protected
count NetworKit::TopCloseness::n
protected
count NetworKit::TopCloseness::n_op = 0
protected
count NetworKit::TopCloseness::nLevs = 0
protected
std::vector<count> NetworKit::TopCloseness::nodesPerLev
protected
std::vector<count> NetworKit::TopCloseness::reachL
protected
std::vector<count> NetworKit::TopCloseness::reachU
protected
bool NetworKit::TopCloseness::sec_heu
protected
std::vector<std::vector<count> > NetworKit::TopCloseness::subtree
protected
std::vector<node> NetworKit::TopCloseness::topk
protected
std::vector<edgeweight> NetworKit::TopCloseness::topkScores
protected
count NetworKit::TopCloseness::visEdges = 0
protected

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