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::GroupCloseness Class Reference

#include <GroupCloseness.h>

Public Member Functions

 GroupCloseness (const Graph &G, count k=1, count H=0)
 Finds the group of nodes with highest (group) closeness centrality. More...
 
void run ()
 Computes the group with maximum closeness on the graph passed in the constructor. More...
 
std::vector< nodegroupMaxCloseness ()
 Returns group with maximum closeness. More...
 
double computeFarness (std::vector< node > S, count H=std::numeric_limits< count >::max())
 Computes farness (i.e., inverse of the closeness) for a given group (stopping after H iterations if H > 0). 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

edgeweight computeImprovement (node u, count n, Graph &G, count h)
 
std::vector< countnewDistances (node u, count n, Graph &G, count h)
 

Protected Attributes

Graph G
 
count k = 1
 
std::vector< countD
 
count iters
 
count maxD
 
std::vector< countd
 
std::vector< countd1
 
std::vector< nodeS
 
count H = 0
 
- 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::GroupCloseness::GroupCloseness ( const Graph G,
count  k = 1,
count  H = 0 
)

Finds the group of nodes with highest (group) closeness centrality.

The algorithm is the one proposed in Bergamini et al., ALENEX 2018 and finds a solution that is a (1-1/e)-approximation of the optimum. The worst-case running time of this approach is quadratic, but usually much faster in practice.

Parameters
GAn unweighted graph.
kSize of the group of nodes
HIf equal 0, simply runs the algorithm proposed in Bergamini et al.. If > 0, interrupts all BFSs after H iterations (suggested for very large networks). @

Member Function Documentation

double NetworKit::GroupCloseness::computeFarness ( std::vector< node S,
count  H = std::numeric_limits<count>::max() 
)

Computes farness (i.e., inverse of the closeness) for a given group (stopping after H iterations if H > 0).

edgeweight NetworKit::GroupCloseness::computeImprovement ( node  u,
count  n,
Graph G,
count  h 
)
protected
std::vector< node > NetworKit::GroupCloseness::groupMaxCloseness ( )
inline

Returns group with maximum closeness.

std::vector< count > NetworKit::GroupCloseness::newDistances ( node  u,
count  n,
Graph G,
count  h 
)
protected
void NetworKit::GroupCloseness::run ( )
virtual

Computes the group with maximum closeness on the graph passed in the constructor.

Implements NetworKit::Algorithm.

Member Data Documentation

std::vector<count> NetworKit::GroupCloseness::D
protected
std::vector<count> NetworKit::GroupCloseness::d
protected
std::vector<count> NetworKit::GroupCloseness::d1
protected
Graph NetworKit::GroupCloseness::G
protected
count NetworKit::GroupCloseness::H = 0
protected
count NetworKit::GroupCloseness::iters
protected
count NetworKit::GroupCloseness::k = 1
protected
count NetworKit::GroupCloseness::maxD
protected
std::vector<node> NetworKit::GroupCloseness::S
protected

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