Class PLM¶

Inheritance Relationships¶

Class Documentation¶

class PLM : public NetworKit::CommunityDetectionAlgorithm¶

Parallel Louvain Method - a multi-level modularity maximizer.

Public Functions

PLM(const Graph &G, bool refine = false, double gamma = 1.0, std::string par = "balanced", count maxIter = 32, bool turbo = true, bool recurse = true)¶

Parameters:

• G – [in] input graph

• refine – [in] add a second move phase to refine the communities

• par – [in] parallelization strategy

• gammamulti-resolution – [in] modularity parameter: 1.0 -> standard modularity 0.0 -> one community 2m -> singleton communities

• maxIter – [in] maximum number of iterations for move phase

• parallelCoarsening – [in] use parallel graph coarsening

• turbo – [in] faster but uses O(n) additional memory per thread

• recurse – [in] use recursive coarsening, see http://journals.aps.org/pre/abstract/10.1103/PhysRevE.89.049902 for some explanations (default: true)

PLM(const Graph &G, const PLM &other)¶

virtual void run() override¶

Detect communities.

const std::map<std::string, std::vector<count>> &getTiming() const¶

Returns fine-grained running time measurements for algorithm engineering purposes.

Public Static Functions

static std::pair<Graph, std::vector<node>> coarsen(const Graph &G, const Partition &zeta)¶

Coarsens a graph based on a given partition and returns both the coarsened graph and a mapping for the nodes from fine to coarse.

Parameters:

• graph – The input graph

• zeta – Partition of the graph, which represents the desired state of the coarsened graph

Returns:

pair of coarsened graph and node-mappings from fine to coarse graph

static Partition prolong(const Graph &Gcoarse, const Partition &zetaCoarse, const Graph &Gfine, std::vector<node> nodeToMetaNode)¶

Calculates a partition containing the mapping of node-id from a fine graph to a cluster-id from partition based on a coarse graph.

Parameters:

• Gcoarse – Coarsened graph

• zetaCoarse – Partition, which contains information about clusters in the coarsened graph

• Gfine – Fine graph

• nodeToMetaNode – mapping for node-id from fine to coarse graph

Returns:

Partition, which contains the cluster-id in the coarse graph for every node from the fine graph