Class TopCloseness¶

Inheritance Relationships¶

Class Documentation¶

class TopCloseness : public NetworKit::Algorithm¶

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

• G – An unweighted graph.

• k – Number 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_heu – If true, the neighborhood-based lower bound is computed and nodes are sorted according to it. If false, nodes are simply sorted by degree.

• sec_heu – If true, the BFSbound is re-computed at each iteration. If false, BFScut is used.

virtual void run() override¶

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

inline std::vector<node> topkNodesList(bool includeTrail = false)¶

Returns a list with the k nodes with highest closeness. WARNING: closeness centrality of some nodes below the top-k could be equal to the k-th closeness, we call them trail. Set the parameter includeTrail to true to also include those nodes but consider that the resulting vector could be longer than k.

Parameters:

includeTrail – Whether or not to include trail nodes.

inline std::vector<edgeweight> topkScoresList(bool includeTrail = false)¶

Returns a list with the scores of the k nodes with highest closeness WARNING: closeness centrality of some nodes below the top-k could be equal to the k-th closeness, we call them trail. Set the parameter includeTrail to true to also include those centrality values but consider that the resulting vector could be longer than k.

Parameters:

includeTrail – Whether or not to include trail centrality value.

inline void restrictTopKComputationToNodes(const std::vector<node> &nodeList)¶

Restricts the top-k closeness computation to a subset of nodes. If the given list is empty, all nodes in the graph will be considered. Note: Actual existence of included nodes in the graph is not checked.

Parameters:

nodeList – Subset of nodes.