networkit.community

The adjusted rand dissimilarity measure as proposed by Huber and Arabie in “Comparing partitions” (http://link.springer.com/article/10.1007/BF01908075)

getDissimilarity(G, first, second)

Returns dissimilarity between two partitions.

Parameters
Returns

Dissimilarity between partition first and second.

Return type

float

class networkit.community.ClusteringGenerator

Bases: object

Generators for various clusterings

makeContinuousBalancedClustering(G, k)

Generate a clustering with k clusters to which nodes are assigned in continuous blocks

Parameters
• G (networkit.Graph) – The graph for which the clustering shall be generated.

• k (int) – The number of clusters that shall be generated.

Returns

The generated partition.

Return type

networkit.Partition

makeNoncontinuousBalancedClustering(G, k)

Generate a clustering with k clusters, the ith node is assigned to cluster i % k. This means that for k**2 nodes, this clustering is complementary to the continuous clustering in the sense that no pair of nodes that is in the same cluster in one of the clusterings is in the same cluster in the other clustering.

Parameters
• G (networkit.Graph) – The graph for which the clustering shall be generated.

• k (int) – The number of clusters that shall be generated.

Returns

The generated partition.

Return type

networkit.Partition

makeOneClustering(G)

Generate a clustering with one cluster consisting of all nodes.

Parameters

G (networkit.Graph) – The graph for which the clustering shall be generated.

Returns

The generated partition.

Return type

networkit.Partition

makeRandomClustering(G, k)

Generate a clustering with k clusters to which nodes are assigned randomly.

Parameters
• G (networkit.Graph) – The graph for which the clustering shall be generated.

• k (int) – The number of clusters that shall be generated.

Returns

The generated partition.

Return type

networkit.Partition

makeSingletonClustering(G)

Generate a clustering where each node has its own cluster

Parameters

G (networkit.Graph) – The graph for which the clustering shall be generated.

Returns

The generated partition.

Return type

networkit.Partition

class networkit.community.CommunityDetector

Abstract base class for static community detection algorithms.

getPartition()

Returns a partition of the clustering.

Returns

A Partition of the clustering.

Return type

networkit.Partition

class networkit.community.CoverF1Similarity(G, C, reference)

Compare a given cover to a reference cover using the F1 measure. This is a typical similarity measure used to compare the found overlapping community structure to a ground truth community structure. Each cluster is compared to the best-matching reference cluster (in terms of highest F1 score). A value of 1 indicates perfect agreement while a while of 0 indicates complete disagreement. An example where this measure is used is the following paper:

Alessandro Epasto, Silvio Lattanzi, and Renato Paes Leme. 2017. Ego-Splitting Framework: from Non-Overlapping to Overlapping Clusters. In Proceedings of the 23rd ACM SIGKDD International Conference on Knowledge Discovery and Data Mining (KDD ‘17). ACM, New York, NY, USA, 145-154. DOI: https://doi.org/10.1145/3097983.3098054

Parameters
class networkit.community.CoverHubDominance(G, C)

A quality measure that measures the dominance of hubs in clusters. The hub dominance of a single cluster is defined as the maximum cluster-internal degree of a node in that cluster divided by the maximum cluster-internal degree, i.e. the number of nodes in the cluster minus one. The value for all clusters is defined as the average of all clusters. This implementation is a natural generalization of this measure for covers. Strictly speaking this is not a quality measure as this is rather dependent on the type of the considered graph, for more information see Lancichinetti A, Kivel M, Saramki J, Fortunato S (2010) Characterizing the Community Structure of Complex Networks PLoS ONE 5(8): e11976. doi: 10.1371/journal.pone.0011976 http://www.plosone.org/article/info%3Adoi%2F10.1371%2Fjournal.pone.0011976

Parameters
class networkit.community.Coverage

Bases: object

Coverage is the fraction of intra-community edges

getQuality(Partition zeta, Graph G)

Calculates the coverage in the given Partition of the given Graph.

Parameters
Returns

The coverage in the given Partition.

Return type

float

class networkit.community.CutClustering(G, alpha)

Cut clustering algorithm as defined in Flake, Gary William; Tarjan, Robert E.; Tsioutsiouliklis, Kostas. Graph Clustering and Minimum Cut Trees. Internet Mathematics 1 (2003), no. 4, 385–408.

Parameters
• G (networkit.Graph) – The input graph.

• alpha (float) – The parameter for the cut clustering algorithm.

static getClusterHierarchy(G)

Get the complete hierarchy with all possible parameter values.

Each reported parameter value is the lower bound for the range in which the corresponding clustering is calculated by the cut clustering algorithm.

Warning: all reported parameter values are slightly too high in order to avoid wrong clusterings because of numerical inaccuracies. Furthermore the completeness of the hierarchy cannot be guaranteed because of these inaccuracies. This implementation hasn’t been optimized for performance.

Parameters

G (networkit.Graph) – The input graph.

Returns

A dictionary with the parameter values as keys and the corresponding Partition instances as values.

Return type

dict(str : networkit.Partition)

class networkit.community.DissimilarityMeasure

Bases: object

Abstract base class for partition/community dissimilarity measures

class networkit.community.EdgeCut

Bases: object

Edge cut is the total weight of inter-community edges

getQuality(zeta, G)

Calculates the edgeCut in the given Partition of the given Graph.

Parameters
Returns

The edgeCut in the given Partition.

Return type

float

class networkit.community.GraphClusteringTools

Bases: object

static communicationGraph(graph, zeta)

Get the communication graph for a given graph and its partition. A communication graph consists of a number of nodes, which equal the number of clusters in the partition. The edges between nodes in the communication graph account for the total edge weight for all edges between two clusters. For unweighted graphs, the edge weight in the communication graph is equal to the number of edges between two clusters.

Parameters
Returns

Communication graph given by the input graph and its partition.

Return type

networkit.Graph

static equalClustering(zeta, eta, G)

Check whether two paritions are equal for a given graph.

Parameters
Returns

True if both partitions are the same, False if not.

Return type

bool

static getImbalance(zeta)

Get the imbalance of clusters in the given partition.

Parameters
Returns

Imbalance of the partition.

Return type

int

static isOneClustering(G, zeta)

Check whether a partition is a one clustering for a given graph.

Parameters
Returns

True if the partition is a one clustering, False if not.

Return type

bool

static isProperClustering(G, zeta)

Check whether a partition is a proper clustering for a given graph.

Parameters
Returns

True if the partition is a proper clustering, False if not.

Return type

bool

static isSingletonClustering(G, zeta)

Check whether a partition is a singleton clustering for a given graph.

Parameters
Returns

True if the partition is a singleton clustering, False if not.

Return type

bool

static weightedDegreeWithCluster(graph, zeta, u, cid)

Get weightedDegree of node u for a cluster (represented by a partition) of index cid.

Parameters
• graph (networkit.Graph) – The input graph.

• zeta (networkit.Partition) – Partition, which contains information about clusters in the graph.

• u (int) – The input node.

• cid (int) – Index of cluster.

Returns

weighted degree of node u for cluster index cid.

Return type

float

class networkit.community.GraphStructuralRandMeasure

The graph-structural Rand measure assigns a similarity value in [0,1] to two partitions of a graph, by considering connected pairs of nodes.

getDissimilarity(G, first, second)

Returns dissimilarity between two partitions.

Parameters
Returns

Dissimilarity between partition first and second.

Return type

float

class networkit.community.HubDominance

Bases: object

A quality measure that measures the dominance of hubs in clusters. The hub dominance of a single cluster is defined as the maximum cluster-internal degree of a node in that cluster divided by the maximum cluster-internal degree, i.e. the number of nodes in the cluster minus one. The value for all clusters is defined as the average of all clusters.

Strictly speaking this is not a quality measure as this is rather dependent on the type of the considered graph, for more information see Lancichinetti A, Kivel M, Saramki J, Fortunato S (2010) Characterizing the Community Structure of Complex Networks PLoS ONE 5(8): e11976. doi: 10.1371/journal.pone.0011976 http://www.plosone.org/article/info%3Adoi%2F10.1371%2Fjournal.pone.0011976

getQuality(zeta, G)

Calculates the dominance of hubs in the given Partition or Cover of the given Graph.

Parameters
Returns

The average hub dominance in the given Partition or Cover.

Return type

float

class networkit.community.IntrapartitionDensity(G, P)

The intra-cluster density of a partition is defined as the number of existing edges divided by the number of possible edges. The global value is the sum of all existing intra-cluster edges divided by the sum of all possible intra-cluster edges.

Parameters
getGlobal()

Get the global intra-cluster density.

Returns

The global intra-cluster density.

Return type

float

class networkit.community.IsolatedInterpartitionConductance(G, P)

Isolated inter-partition conductance is a measure for how well a partition (communtiy/cluster) is separated from the rest of the graph.

The conductance of a partition is defined as the weight of the cut divided by the volume (the sum of the degrees) of the nodes in the partition or the nodes in the rest of the graph, whatever is smaller. Small values thus indicate that the cut is small compared to the volume of the smaller of the separated parts. For the whole partitions usually the maximum or the unweighted average is used.

See also Experiments on Density-Constrained Graph Clustering, Robert Grke, Andrea Kappes and Dorothea Wagner, JEA 2015: http://dx.doi.org/10.1145/2638551

Parameters
class networkit.community.IsolatedInterpartitionExpansion(G, P)

Isolated inter-partition expansion is a measure for how well a partition (communtiy/cluster) is separated from the rest of the graph.

The expansion of a partition is defined as the weight of the cut divided by number of nodes in the partition or in the rest of the graph, whatever is smaller. Small values thus indicate that the cut is small compared to the size of the smaller of the separated parts. For the whole partitions usually the maximum or the unweighted average is used. Note that expansion values can be larger than 1.

See also Experiments on Density-Constrained Graph Clustering, Robert Grke, Andrea Kappes and Dorothea Wagner, JEA 2015: http://dx.doi.org/10.1145/2638551

Parameters
class networkit.community.JaccardMeasure
getDissimilarity(G, first, second)

Returns dissimilarity between two partitions.

Parameters
Returns

Dissimilarity between partition first and second.

Return type

float

class networkit.community.LFM(G, scd)

Local community expansion algorithm:

The LFM algorithm detects overlapping communities by repeatedly executing a given selective community detector algorithm for different random seed nodes which have not yet been assigned to any community.

Parameters

Notes

Local community expansion algorithm as introduced in:

Lancichinetti, A., Fortunato, S., & Kertész, J. (2009). Detecting the overlapping and hierarchical community structure in complex networks. New Journal of Physics, 11(3), 033015. https://doi.org/10.1088/1367-2630/11/3/033015

class networkit.community.LPDegreeOrdered(G)

Label propagation-based community detection algorithm which processes nodes in increasing order of node degree.

numberOfIterations()

Get number of iterations in last run.

Returns

Number of iterations.

Return type

int

class networkit.community.LocalCommunityEvaluation

Virtual base class of all evaluation methods for a single clustering which is based on the evaluation of single clusters. This is the base class both for Partitions as well as for Covers.

getMaximumValue()

Get the maximum value of all clusters.

Returns

The maximum value.

Return type

float

getMinimumValue()

Get the minimum value of all clusters.

Returns

The minimum value.

Return type

float

getUnweightedAverage()

Get the (unweighted) average value of all clusters.

Returns

The unweighted average value.

Return type

float

getValue(index i)

Get the value of the specified cluster.

Parameters

i (int) – The cluster to get the value for.

Returns

The value of cluster i.

Return type

float

getValues()

Get the values of all clusters.

Returns

The values of all clusters.

Return type

list(float)

getWeightedAverage()

Get the average value weighted by cluster size.

Returns

The weighted average value.

Return type

float

isSmallBetter()

If small values are better (otherwise large values are better).

Returns

If small values are better.

Return type

bool

class networkit.community.LocalCoverEvaluation(G, P)

Virtual base class of all evaluation methods for a single clustering which is based on the evaluation of single clusters. This is the base class for Covers.

class networkit.community.LocalPartitionEvaluation(G, P)

Virtual base class of all evaluation methods for a single clustering which is based on the evaluation of single clusters. This is the base class for Partitions.

class networkit.community.LouvainMapEquation(G, hierarchical=False, maxIterations=32, parallelizationStrategy='relaxmap')

Community detection algorithm based on the Louvain algorithm. Uses the Map Equation to find communities.

Parameters
• G (networkit.Graph) – The graph on which the algorithm has to run.

• hierarchical (bool, optional) – Iteratively create a graph of the locally optimal clusters and optimize locally on that graph.

• maxIterations (int, optional) – The maximum number of local move iterations.

• parallelizationStrategy (str, optional) – Parallelization strategy, possible values: “relaxmap”, “synchronous”, “none”. Default: “relaxmap”

class networkit.community.Modularity

Bases: object

Modularity is a quality index for community detection. It assigns a quality value in [-0.5, 1.0] to a partition of a graph which is higher for more modular networks and partitions which better capture the modular structure. See also http://en.wikipedia.org/wiki/Modularity_(networks).

Notes

Modularity is defined as:

$mod(\zeta) := \frac{\sum_{C \in \zeta} \sum_{ e \in E(C) } \omega(e)}{\sum_{e \in E} \omega(e)} - \frac{ \sum_{C \in \zeta}( \sum_{v \in C} \omega(v) )^2 }{4( \sum_{e \in E} \omega(e) )^2 }$
getQuality(zeta, G)

Calculates the modularity in the given Partition of the given Graph.

Parameters
Returns

The modularity in the given Partition

Return type

float

class networkit.community.NMIDistance

The NMI distance assigns a similarity value in [0,1] to two partitions of a graph.

getDissimilarity(G, first, second)

Returns dissimilarity between two partitions.

Parameters
Returns

Dissimilarity between partition first and second.

Return type

float

class networkit.community.NodeStructuralRandMeasure

The node-structural Rand measure assigns a similarity value in [0,1] to two partitions of a graph, by considering all pairs of nodes.

getDissimilarity(G, first, second)

Returns dissimilarity between two partitions.

Parameters
Returns

Dissimilarity between partition first and second.

Return type

float

class networkit.community.Normalization

Bases: object

ARITHMETIC_MEAN = 2
ArithmeticMean = 2
GEOMETRIC_MEAN = 1
GeometricMean = 1
JOINT_ENTROPY = 4
JointEntropy = 4
MAX = 3
MIN = 0
Max = 3
Min = 0
class networkit.community.OverlappingCommunityDetector

Abstract base class for static overlapping community detection algorithms.

getCover()

Returns a cover of the clustering.

Returns

A Cover of the clustering.

Return type

networkit.Cover

class networkit.community.OverlappingNMIDistance(normalization=networkit.community.Normalization.MAX)

Compare two covers using the overlapping normalized mutual information measure. This is a dissimilarity measure with a range of [0, 1]. A value of 0 indicates a perfect agreement while a 1 indicates complete disagreement.

For networkit.community.Normalization.Max normalization, this is the measure introduced in [NMI13]. Other normalization methods result in similar measures.

Parameter normalization can be one of the following:

• networkit.community.Normalization.MIN

• networkit.community.Normalization.GEOMETRIC_MEAN

• networkit.community.Normalization.ARITHMETIC_MEAN

• networkit.community.Normalization.MAX

• networkit.community.Normalization.JOINT_ENTROPY

Parameters

normalization (networkit.community.Normalization, optional) – Normalization strategy for OverlappingNMIDistance. Default: networkit.community.Normalization.MAX

Raises

ValueError – If normalization is not one of the available methods.

References

[NMI13]

McDaid, Aaron F., Derek Greene, and Neil Hurley. “Normalized Mutual Information to Evaluate Overlapping Community Finding Algorithms.” ArXiv:1110.2515 [Physics], August 2, 2013. http://arxiv.org/abs/1110.2515.

getDissimilarity(G, first, second)

Calculate the dissimilarity.

Parameters
Raises
• TypeError – If first and second do not have the same type.

• ValueError – If G, first and second do not have the matching number of nodes.

Returns

Resulting overlapping NMI distance.

Return type

float

setNormalization(self, normalization)

Set the normalization method.

Parameter normalization can be one of the following:

• networkit.community.Normalization.MIN

• networkit.community.Normalization.GEOMETRIC_MEAN

• networkit.community.Normalization.ARITHMETIC_MEAN

• networkit.community.Normalization.MAX

• networkit.community.Normalization.JOINT_ENTROPY

Parameters

normalization (networkit.community.Normalization) – Normalization strategy for OverlappingNMIDistance.

Raises

ValueError – If normalization is not one of the available methods.

class networkit.community.PLM(G, refine=False, gamma=1.0, par='balanced', maxIter=32, turbo=True, recurse=True)

Parallel Louvain Method - the Louvain method, optionally extended to a full multi-level algorithm with refinement.

Parameters
• G (networkit.Graph) – The input graph.

• refine (bool, optional) – Add a second move phase to refine the communities. Default: False

• gamma (float, optional) – Multi-resolution modularity parameter: 1.0 (standard modularity), 0.0 (one community), 2m (singleton communities). Default: 1.0

• par (str, optional) – Parallelization strategy, possible values: “none”, “simple”, “balanced”, “none randomized”. Default “balanced”

• maxIter (int, optional) – Maximum number of iterations for move phase. Default: 32

• turbo (bool, optional) – Faster but uses O(n) additional memory per thread. Default: True

• recurse (bool, optional) – Use recursive coarsening, see http://journals.aps.org/pre/abstract/10.1103/PhysRevE.89.049902 for some explanations. Default: True

static coarsen(G, zeta, parallel=False)

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
• G (networkit.Graph) – The input graph.

• zeta (networkit.Partition) – Partition of the graph, which represents the desired state of the coarsened graph.

• parallel (bool, optional) – Do the coarsening in parallel. Default: False

Returns

Pair of coarsened graph and node-mappings from fine to coarse graph.

Return type

networkit.Graph

getTiming()

Get detailed time measurements.

Returns

Time for computing PLM.

Return type

float

static prolong(Gcoarse, zetaCoarse, Gfine, 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 (networkit.Graph) – A coarse graph.

• zetaCoarse (networkit.Partition) – The first partition.

• Gfine (networkit.Graph) – A fine graph.

• nodeToMetaNode (list(int)) – Partition, which contains the cluster-id in the coarse graph for every node from the fine graph.

Returns

Output partition.

Return type

networkit.Partition

class networkit.community.PLP(G, updateThreshold=None, maxIterations=None, baseClustering=None)

Parallel label propagation for community detection: Moderate solution quality, very short time to solution.

Parameters
• G (networkit.Graph) – The graph on which the algorithm has to run.

• updateThreshold (int, optional) – number of nodes that have to be changed in each iteration so that a new iteration starts. Default: None

• baseClustering (networkit.Partition, optional) – PLP needs a base clustering to start from; if none is given the algorithm will run on a singleton clustering. Default: None

Notes

As described in Ovelgoenne et al: An Ensemble Learning Strategy for Graph Clustering Raghavan et al. proposed a label propagation algorithm for graph clustering. This algorithm initializes every vertex of a graph with a unique label. Then, in iterative sweeps over the set of vertices the vertex labels are updated. A vertex gets the label that the maximum number of its neighbors have. The procedure is stopped when every vertex has the label that at least half of its neighbors have.

getTiming()

Get list of running times for each iteration.

Returns

The list of running times in milliseconds.

Return type

int

numberOfIterations()

Get number of iterations in last run.

Returns

The number of iterations.

Return type

int

class networkit.community.ParallelLeiden(G, randomize=True, iterations=3, gamma=1)

Parallel Leiden Algorithm.

Parameters
• G (networkit.Graph) – A graph.

• randomize (bool, optional) – Whether to randomize the node order or not. Default: True

• iterations (int, optional) – Maximum count of Leiden runs. Default: 3

• gamma (float, optional) – Multi-resolution modularity parameter: 1.0 (standard modularity), 0.0 (one community), 2m (singleton communities). Default: 1.0

class networkit.community.PartitionFragmentation(G, P)

This measure evaluates how fragmented a partition is. The fragmentation of a single cluster is defined as one minus the number of nodes in its maximum connected componented divided by its total number of nodes. Smaller values thus indicate a smaller fragmentation.

Parameters
class networkit.community.PartitionHubDominance(G, P)

A quality measure that measures the dominance of hubs in clusters. The hub dominance of a single cluster is defined as the maximum cluster-internal degree of a node in that cluster divided by the maximum cluster-internal degree, i.e. the number of nodes in the cluster minus one. The value for all clusters is defined as the average of all clusters. Strictly speaking this is not a quality measure as this is rather dependent on the type of the considered graph, for more information see Lancichinetti A, Kivel M, Saramki J, Fortunato S (2010) Characterizing the Community Structure of Complex Networks PLoS ONE 5(8): e11976. doi: 10.1371/journal.pone.0011976 http://www.plosone.org/article/info%3Adoi%2F10.1371%2Fjournal.pone.0011976

Parameters
class networkit.community.PartitionIntersection(zeta, eta)

Bases: object

Class for calculating the intersection of two partitions, i.e. the clustering with the fewest clusters such that each cluster is a subset of a cluster in both partitions.

calculate()

Calculate the intersection of two partitions zeta and eta

Parameters
Returns

The intersection of zeta and eta.

Return type

networkit.Partition

class networkit.community.SpectralPartitioner(graph, count, balances=True)

Bases: object

Class to do spectral partitioning.

Please note that the code in this class assumes the nodes of a graph to be numbered from 0 to n.

Parameters
• graph (networkit.Graph) – The input graph.

• count (int) – The number of partitions to create.

• balanced (bool, optional) – Set this to false if you do not want to enforce balance, possibly increasing quality. Default: True

getPartition()

Retrieves the partitioning after run() was called.

Returns

The resulting partition. Only valid if run() was called before.

Return type

networkit.Partition

run()

Runs the partitioning.

class networkit.community.StablePartitionNodes(G, P)

Evaluates how stable a given partition is. A node is considered to be stable if it has strictly more connections to its own partition than to other partitions. Isolated nodes are considered to be stable. The value of a cluster is the percentage of stable nodes in the cluster. Larger values indicate that a clustering is more stable and thus better defined.

Parameters
isStable(u)

Check if a given node is stable, i.e. more connected to its own partition than to other partitions.

Parameters

u (int) – The node to check.

Returns

If the node u is stable.

Return type

bool

networkit.community.communityGraph(G, P)

Create a community graph, i.e. a graph in which one node represents a community and an edge represents the edges between communities, from a given graph and a community detection solution.

Parameters
networkit.community.compareCommunities(G, zeta1, zeta2)

Compare the partitions with respect to several (dis)similarity measures.

Notes

Currently not implemented.

networkit.community.detectCommunities(G, algo=None, inspect=True)

Perform high-performance community detection on the graph.

Parameters
• G (Graph) – The graph on which the evaluation is performed.

• algo (networkit.community.CommunityDetector) – Community detection algorithm instance. Default: None

• inspect (bool, optional) – Print properties of the found solution. Default: True

Returns

Return communities (as type Partition).

Return type

networkit.Partition

networkit.community.evalCommunityDetection(algo, G)

Evaluate a community detection algorithm

Parameters
Returns

inspection of communities (needs external tabulate-module)

Return type

tabulate.tabulate

networkit.community.inspectCommunities(zeta, G)

Parameters
Returns

inspection of communities (needs external tabulate-module)

Return type

tabulate.tabulate

networkit.community.kCoreCommunityDetection(G, k, algo=None, inspect=True)

Perform community detection on the k-core of the graph, which possibly

Parameters
• G (networkit.Graph) – The graph on which the evaluation is performed.

• k (float) – Set k as used in k-core.

• algo (networkit.community.CommunityDetector, optional) – Community detection algorithm instance. Default: None

• inspect (bool, optional) – Print properties of the found solution. Default: True

Returns

Return communities (as type Partition).

Return type

networkit.Partition

Read a partition into communities from a file

Parameters
• path (str) – Path to file, which contains information about communities.

• format (str, optional) – Format from file, possible values: “default”, “edgelist-t1”, “edgelist-t0”, “edgelist-s1”, “edgelist-s0”. Default: “default”

networkit.community.writeCommunities(communities, path)

Write a partition into communities to a file

Parameters
• communities (networkit.Partition) – The input communities.

• path (str) – Path to write the file to.