networkit.community¶

class networkit.community.AdjustedRandMeasure¶

Bases: DissimilarityMeasure

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:

G (networkit.Graph) – The input graph.
first (networkit.Partition) – The first partition.
second (networkit.Partition) – The second partition.

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¶

Bases: Algorithm

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)¶

Bases: LocalCoverEvaluation

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:

G (networkit.Graph) – The graph on which the evaluation is performed.
C (networkit.Cover) – The cover that shall be evaluated.
reference (networkit.Cover) – The cover to which the similarity shall be computed.

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

Bases: LocalCoverEvaluation

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:

G (networkit.Graph) – The graph on which the measure shall be evaluated.
C (networkit.Cover) – The cover that shall be evaluated.

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:

zeta (networkit.Partition) – The Partition for which the coverage shall be calculated.
G (networkit.Graph) – The Graph to which zeta belongs.

Returns:

The coverage in the given Partition.

Return type:

float

class networkit.community.CutClustering(G, alpha)¶

Bases: CommunityDetector

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:

zeta (networkit.Partition) – The Partition for which the edgeCut shall be calculated.
G (networkit.Graph) – The Graph to which zeta belongs.

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:

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

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:

zeta (networkit.Partition) – The first partition.
eta (networkit.Partition) – The second partition.
G (networkit.Graph) – The input graph.

Returns:

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

Return type:

bool

static getImbalance(zeta, G)¶

Get the imbalance of clusters in the given partition.

Parameters:

zeta (networkit.Partition) – The first partition.
G (networkit.Graph, optional) – The input graph to compare the imbalance to. Default: None

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:

G (networkit.Graph) – The input graph.
zeta (networkit.Partition) – The first partition.

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:

G (networkit.Graph) – The input graph.
zeta (networkit.Partition) – The first partition.

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:

G (networkit.Graph) – The input graph.
zeta (networkit.Partition) – The first partition.

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¶

Bases: DissimilarityMeasure

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:

G (networkit.Graph) – The graph.
first (networkit.Partition) – The first partition.
second (networkit.Partition) – The second partition.

Returns:

Dissimilarity between partition first and second.

Return type:

float

class networkit.community.HubDominance¶

Bases: object

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:

zeta (networkit.Partition or networkit.Cover) – The Partition or Cover for which the hub dominance shall be calculated.
G (networkit.Graph) – The Graph to which zeta belongs.

Returns:

The average hub dominance in the given Partition or Cover.

Return type:

float

class networkit.community.IntrapartitionDensity(G, P)¶

Bases: LocalPartitionEvaluation

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:

G (networkit.Graph) – The graph on which the measure shall be evaluated.
P (networkit.Partition) – The partition that shall be evaluated.

getGlobal()¶

Get the global intra-cluster density.

Returns:: The global intra-cluster density.
Return type:: float

class networkit.community.IsolatedInterpartitionConductance(G, P)¶

Bases: LocalPartitionEvaluation

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:

G (networkit.Graph) – The graph on which the measure shall be evaluated.
P (networkit.Partition) – The partition that shall be evaluated.

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

Bases: LocalPartitionEvaluation

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:

G (networkit.Graph) – The graph on which the measure shall be evaluated.
P (networkit.Partition) – The partition that shall be evaluated.

class networkit.community.JaccardMeasure¶

Bases: DissimilarityMeasure

getDissimilarity(G, first, second)¶

Returns dissimilarity between two partitions.

Parameters:

G (networkit.Graph) – The input graph.
first (networkit.Partition) – The first partition.
second (networkit.Partition) – The second partition.

Returns:

Dissimilarity between partition first and second.

Return type:

float

class networkit.community.LFM(G, scd)¶

Bases: OverlappingCommunityDetector

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:

G (networkit.Graph) – The graph on which the algorithm has to run.
scd (networkit.scd.SelectiveCommunityDetector) – The selective community detector algorithm which is run on randomly selected seed nodes

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)¶

Bases: CommunityDetector

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¶

Bases: Algorithm

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)¶

Bases: 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 for Covers.

class networkit.community.LocalPartitionEvaluation(G, P)¶

Bases: 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 for Partitions.

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

Bases: CommunityDetector

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. Default: 32
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:

zeta (networkit.Partition) – The Partition for which the modularity shall be calculated
G (networkit.Graph) – The Graph to which zeta belongs

Returns:

The modularity in the given Partition

Return type:

float

class networkit.community.NMIDistance¶

Bases: DissimilarityMeasure

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:

G (networkit.Graph) – The graph.
first (networkit.Partition) – The first partition.
second (networkit.Partition) – The second partition.

Returns:

Dissimilarity between partition first and second.

Return type:

float

class networkit.community.NodeStructuralRandMeasure¶

Bases: DissimilarityMeasure

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:

G (networkit.Graph) – The input graph.
first (networkit.Partition) – The first partition.
second (networkit.Partition) – The second partition.

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¶

Bases: Algorithm

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)¶

Bases: DissimilarityMeasure

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:

G (networkit.Graph) – The input graph.
first (networkit.Partition or networkit.Cover) – The first input partition/cover.
second (networkit.Partition or networkit.Cover) – The second input partition/cover. Must be the same type as first.

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)¶

Bases: CommunityDetector

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)¶

Bases: CommunityDetector

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
maxIterations (int, optional) – The maximum number of local move iterations. 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)¶

Bases: CommunityDetector

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)¶

Bases: LocalPartitionEvaluation

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:

G (networkit.Graph) – The graph on which the measure shall be evaluated.
P (networkit.Partition) – The partition that shall be evaluated.

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

Bases: LocalPartitionEvaluation

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:

G (networkit.Graph) – The graph on which the measure shall be evaluated.
P (networkit.Partition) – The partition that shall be evaluated.

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(zeta, eta)¶

Calculate the intersection of two partitions zeta and eta.

Parameters:

zeta (networkit.Partition) – The first partition.
eta (networkit.Partition) – The second partition.

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)¶

Bases: LocalPartitionEvaluation

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:

G (networkit.Graph) – The graph on which the measure shall be evaluated.
P (networkit.Partition) – The partition that shall be evaluated.

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:

G (networkit.Graph) – The graph on which the evaluation is performed.
P (networkit.Partition) – The input Partition.

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:

algo (networkit.community.CommunityDetector) – Community detection algorithm instance
G (networkit.Graph) – The graph on which the evaluation is performed.

Returns:

inspection of communities (needs external tabulate-module)

Return type:

tabulate.tabulate

networkit.community.inspectCommunities(zeta, G)¶

Display information about communities.

Parameters:

zeta (networkit.Partition) – The input Partition.
G (networkit.Graph) – The graph on which the evaluation is performed.

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

networkit.community.readCommunities(path, format='default')¶

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.