Class GroupDegree

Inheritance Relationships

Base Type

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.

  • 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