Bases: DissimilarityMeasure
The adjusted rand dissimilarity measure as proposed by Huber and Arabie in “Comparing partitions” (http://link.springer.com/article/10.1007/BF01908075)
Returns dissimilarity between two partitions.
G (networkit.Graph) – The input graph.
first (networkit.Partition) – The first partition.
second (networkit.Partition) – The second partition.
Dissimilarity between partition first and second.
float
Bases: object
Generators for various clusterings
Generate a clustering with k clusters to which nodes are assigned in continuous blocks
G (networkit.Graph) – The graph for which the clustering shall be generated.
k (int) – The number of clusters that shall be generated.
The generated partition.
networkit.Partition
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.
G (networkit.Graph) – The graph for which the clustering shall be generated.
k (int) – The number of clusters that shall be generated.
The generated partition.
networkit.Partition
Generate a clustering with one cluster consisting of all nodes.
G (networkit.Graph) – The graph for which the clustering shall be generated.
The generated partition.
networkit.Partition
Generate a clustering with k clusters to which nodes are assigned randomly.
G (networkit.Graph) – The graph for which the clustering shall be generated.
k (int) – The number of clusters that shall be generated.
The generated partition.
networkit.Partition
Generate a clustering where each node has its own cluster
G (networkit.Graph) – The graph for which the clustering shall be generated.
The generated partition.
networkit.Partition
Bases: Algorithm
Abstract base class for static community detection algorithms.
Returns a partition of the clustering.
A Partition of the clustering.
networkit.Partition
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
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.
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
G (networkit.Graph) – The graph on which the measure shall be evaluated.
C (networkit.Cover) – The cover that shall be evaluated.
Bases: object
Coverage is the fraction of intra-community edges
Calculates the coverage in the given Partition of the given Graph.
zeta (networkit.Partition) – The Partition for which the coverage shall be calculated.
G (networkit.Graph) – The Graph to which zeta belongs.
The coverage in the given Partition.
float
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.
G (networkit.Graph) – The input graph.
alpha (float) – The parameter for the cut clustering algorithm.
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.
G (networkit.Graph) – The input graph.
A dictionary with the parameter values as keys and the corresponding Partition instances as values.
dict(str :
networkit.Partition)
Bases: object
Abstract base class for partition/community dissimilarity measures
Bases: object
Edge cut is the total weight of inter-community edges
Calculates the edgeCut in the given Partition of the given Graph.
zeta (networkit.Partition) – The Partition for which the edgeCut shall be calculated.
G (networkit.Graph) – The Graph to which zeta belongs.
The edgeCut in the given Partition.
float
Bases: object
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.
graph (networkit.Graph) – The input graph.
zeta (networkit.Partition) – Partition, which contains information about clusters in the graph.
Communication graph given by the input graph and its partition.
networkit.Graph
Check whether two paritions are equal for a given graph.
zeta (networkit.Partition) – The first partition.
eta (networkit.Partition) – The second partition.
G (networkit.Graph) – The input graph.
True if both partitions are the same, False if not.
bool
Get the imbalance of clusters in the given partition.
zeta (networkit.Partition) – The first partition.
G (networkit.Graph, optional) – The input graph to compare the imbalance to. Default: None
Imbalance of the partition.
int
Check whether a partition is a one clustering for a given graph.
G (networkit.Graph) – The input graph.
zeta (networkit.Partition) – The first partition.
True if the partition is a one clustering, False if not.
bool
Check whether a partition is a proper clustering for a given graph.
G (networkit.Graph) – The input graph.
zeta (networkit.Partition) – The first partition.
True if the partition is a proper clustering, False if not.
bool
Check whether a partition is a singleton clustering for a given graph.
G (networkit.Graph) – The input graph.
zeta (networkit.Partition) – The first partition.
True if the partition is a singleton clustering, False if not.
bool
Get weightedDegree of node u for a cluster (represented by a partition) of index cid.
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.
weighted degree of node u for cluster index cid.
float
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.
Returns dissimilarity between two partitions.
G (networkit.Graph) – The graph.
first (networkit.Partition) – The first partition.
second (networkit.Partition) – The second partition.
Dissimilarity between partition first and second.
float
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
Calculates the dominance of hubs in the given Partition or Cover of the given Graph.
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.
The average hub dominance in the given Partition or Cover.
float
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.
G (networkit.Graph) – The graph on which the measure shall be evaluated.
P (networkit.Partition) – The partition that shall be evaluated.
Get the global intra-cluster density.
The global intra-cluster density.
float
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
G (networkit.Graph) – The graph on which the measure shall be evaluated.
P (networkit.Partition) – The partition that shall be evaluated.
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
G (networkit.Graph) – The graph on which the measure shall be evaluated.
P (networkit.Partition) – The partition that shall be evaluated.
Bases: DissimilarityMeasure
Returns dissimilarity between two partitions.
G (networkit.Graph) – The input graph.
first (networkit.Partition) – The first partition.
second (networkit.Partition) – The second partition.
Dissimilarity between partition first and second.
float
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.
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
Bases: CommunityDetector
Label propagation-based community detection algorithm which processes nodes in increasing order of node degree.
Get number of iterations in last run.
Number of iterations.
int
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.
Get the maximum value of all clusters.
The maximum value.
float
Get the minimum value of all clusters.
The minimum value.
float
Get the (unweighted) average value of all clusters.
The unweighted average value.
float
Get the value of the specified cluster.
i (int) – The cluster to get the value for.
The value of cluster i.
float
Get the values of all clusters.
The values of all clusters.
list(float)
Get the average value weighted by cluster size.
The weighted average value.
float
If small values are better (otherwise large values are better).
If small values are better.
bool
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.
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.
Bases: CommunityDetector
Community detection algorithm based on the Louvain algorithm. Uses the Map Equation to find communities.
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”
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:
Calculates the modularity in the given Partition of the given Graph.
zeta (networkit.Partition) – The Partition for which the modularity shall be calculated
G (networkit.Graph) – The Graph to which zeta belongs
The modularity in the given Partition
float
Bases: DissimilarityMeasure
The NMI distance assigns a similarity value in [0,1] to two partitions of a graph.
Returns dissimilarity between two partitions.
G (networkit.Graph) – The graph.
first (networkit.Partition) – The first partition.
second (networkit.Partition) – The second partition.
Dissimilarity between partition first and second.
float
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.
Returns dissimilarity between two partitions.
G (networkit.Graph) – The input graph.
first (networkit.Partition) – The first partition.
second (networkit.Partition) – The second partition.
Dissimilarity between partition first and second.
float
Bases: object
Bases: Algorithm
Abstract base class for static overlapping community detection algorithms.
Returns a cover of the clustering.
A Cover of the clustering.
networkit.Cover
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
normalization (networkit.community.Normalization, optional) – Normalization strategy for OverlappingNMIDistance. Default: networkit.community.Normalization.MAX
ValueError – If normalization is not one of the available methods.
References
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.
Calculate the dissimilarity.
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.
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.
Resulting overlapping NMI distance.
float
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
normalization (networkit.community.Normalization) – Normalization strategy for OverlappingNMIDistance.
ValueError – If normalization is not one of the available methods.
Bases: CommunityDetector
Parallel Louvain Method - the Louvain method, optionally extended to a full multi-level algorithm with refinement.
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
Coarsens a graph based on a given partition and returns both the coarsened graph and a mapping for the nodes from fine to coarse.
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
Pair of coarsened graph and node-mappings from fine to coarse graph.
networkit.Graph
Get detailed time measurements.
Time for computing PLM.
float
Calculates a partition containing the mapping of node-id from a fine graph to a cluster-id from partition based on a coarse graph.
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.
Output partition.
networkit.Partition
Bases: CommunityDetector
Parallel label propagation for community detection: Moderate solution quality, very short time to solution.
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.
Get list of running times for each iteration.
The list of running times in milliseconds.
int
Get number of iterations in last run.
The number of iterations.
int
Bases: CommunityDetector
Parallel Leiden Algorithm.
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
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.
G (networkit.Graph) – The graph on which the measure shall be evaluated.
P (networkit.Partition) – The partition that shall be evaluated.
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
G (networkit.Graph) – The graph on which the measure shall be evaluated.
P (networkit.Partition) – The partition that shall be evaluated.
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 the intersection of two partitions zeta and eta.
zeta (networkit.Partition) – The first partition.
eta (networkit.Partition) – The second partition.
The intersection of zeta and eta.
networkit.Partition
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.
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
Retrieves the partitioning after run() was called.
The resulting partition. Only valid if run()
was called before.
networkit.Partition
Runs the partitioning.
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.
G (networkit.Graph) – The graph on which the measure shall be evaluated.
P (networkit.Partition) – The partition that shall be evaluated.
Check if a given node is stable, i.e. more connected to its own partition than to other partitions.
u (int) – The node to check.
If the node u is stable.
bool
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.
G (networkit.Graph) – The graph on which the evaluation is performed.
P (networkit.Partition) – The input Partition.
Compare the partitions with respect to several (dis)similarity measures.
Notes
Currently not implemented.
Perform high-performance community detection on the graph.
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
Return communities (as type Partition).
networkit.Partition
Evaluate a community detection algorithm
algo (networkit.community.CommunityDetector) – Community detection algorithm instance
G (networkit.Graph) – The graph on which the evaluation is performed.
inspection of communities (needs external tabulate-module)
tabulate.tabulate
Display information about communities.
zeta (networkit.Partition) – The input Partition.
G (networkit.Graph) – The graph on which the evaluation is performed.
inspection of communities (needs external tabulate-module)
tabulate.tabulate
Perform community detection on the k-core of the graph, which possibly
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
Return communities (as type Partition).
networkit.Partition
Read a partition into communities from a file
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”
Write a partition into communities to a file
communities (networkit.Partition) – The input communities.
path (str) – Path to write the file to.