Class GroupDegree¶

Inheritance Relationships¶

Class Documentation¶

class GroupDegree : public NetworKit::Algorithm¶

Public Functions

GroupDegree(const Graph &G, count k = 1, bool countGroupNodes = true)¶

Finds the group with the highest group degree centrality according to the definition proposed in ‘The centrality of groups and classes’ by Everett et al. (The Journal of mathematical sociology, 1999). This is a submodular but non monotone function so the algorithm can find a solution that is at least 1/2 of the optimum. Worst-case running time is quadratic, but usually faster in real-world networks. The ‘countGroupNodes’ option also count the nodes inside the group in the score, this make the group degree monotone and submodular and the algorithm is guaranteed to return a (1 - 1/e)-approximation of the optimal solution.

Parameters:

• G – A graph.

• k – Size of the group of nodes

• countGroupNodes – if nodes inside the group should be counted in the centrality score.

virtual void run() override¶

Computes the group with maximum degree centrality of the graph passed in the constructor.

inline std::vector<node> groupMaxDegree()¶

Returns the group with maximum degree centrality.

inline count getScore()¶

Returns the score of the group with maximum degree centrality (i.e. the number of nodes outside the group that can be reached in one hop from at least one node in the group).

inline count scoreOfGroup(const std::vector<node> &group) const¶

Returns the score of the given group.

Protected Functions

void init()¶

void updateQueue()¶

void updateGroup()¶

inline void computeScore()¶

inline void checkGroup(const std::vector<node> &group) const¶

Protected Attributes

const Graph &G¶

const count k¶

const bool countGroupNodes¶

count n¶

std::vector<node> group¶

std::vector<int64_t> gain¶

std::vector<bool> reachable¶

std::vector<bool> affected¶

std::vector<bool> inGroup¶

Aux::BucketPQ queue¶

count groupScore¶