Class CliqueDetect¶

Inheritance Relationships¶

Class Documentation¶

class CliqueDetect : public NetworKit::SelectiveCommunityDetector¶

The CliqueDetect algorithm. It finds the largest clique in the seed node’s neighborhood.

The algorithm can handle weighted graphs. There, the clique with the highest sum of internal edge weights is returned. This sum includes edge weights to the seed node(s) to ensure that cliques that are well-connected to the seed node(s) are preferred.

See also: Hamann, M.; Röhrs, E.; Wagner, D. Local Community Detection Based on Small Cliques. Algorithms 2017, 10, 90. https://doi.org/10.3390/a10030090

Public Functions

CliqueDetect(const Graph &g)¶

Construct a Cliquedetect object.

Parameters:

G – [in] The graph to detect communities on

virtual std::set<node> expandOneCommunity(node seed) override¶

Expands a single seed node/vertex into a maximal clique.

Parameters:

s – [in] the seed node

Returns:

A community of the seed node

virtual std::set<node> expandOneCommunity(const std::set<node> &seeds) override¶

Detect a single clique for the given seed nodes.

The resulting community is a clique iff the seeds form a clique. Otherwise, only the added nodes form a clique that is fully connected to the seed nodes.

Parameters:

seeds – The seeds for the community.

Returns:

The found community as set of nodes.

Protected Functions

std::vector<node> getMaximumWeightClique(const std::vector<node> &nodes, const std::vector<edgeweight> &seedToNodeWeight) const¶