This module handles community detection, i.e. the discovery of densely connected groups in networks.
networkit.community.
AdjustedRandMeasure
Bases: _NetworKit.DissimilarityMeasure
The adjusted rand dissimilarity measure as proposed by Huber and Arabie in “Comparing partitions” (http://link.springer.com/article/10.1007/BF01908075)
getDissimilarity
(self, Graph G, Partition first, Partition second)Get the adjust rand dissimilarity. Runs in O(n log(n)).
Note that the dissimilarity can be larger than 1 if the partitions are more different than expected in the random model.
networkit.community.
ClusteringGenerator
Bases: object
Generators for various clusterings
makeContinuousBalancedClustering
(self, Graph G, count k)Generate a clustering with k clusters to which nodes are assigned in continuous blocks
makeNoncontinuousBalancedClustering
(self, Graph G, count 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.
makeOneClustering
(self, Graph G)Generate a clustering with one cluster consisting of all nodes
makeRandomClustering
(self, Graph G, count k)Generate a clustering with k clusters to which nodes are assigned randomly
makeSingletonClustering
(self, Graph G)Generate a clustering where each node has its own cluster
networkit.community.
CommunityDetector
(*args, **namedargs)Bases: _NetworKit.Algorithm
Abstract base class for static community detection algorithms
getPartition
(self)Returns a partition of the clustering.
networkit.community.
CoreDecomposition
Bases: _NetworKit.Centrality
Computes k-core decomposition of a graph.
CoreDecomposition(G)
Create CoreDecomposition class for graph G. The graph may not contain self-loops.
getCover
(self)Get the k-cores as cover.
getNodeOrder
(self)Get the node order.
This is only possible when storeNodeOrder was set.
getPartition
(self)Get the k-shells as a partition object.
maxCoreNumber
(self)Get maximum core number.
networkit.community.
CoverHubDominance
Bases: _NetworKit.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, Saramäki 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
networkit.community.
Coverage
Bases: object
Coverage is the fraction of intra-community edges
getQuality
(self, Partition zeta, Graph G)networkit.community.
CutClustering
Bases: _NetworKit.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 : Graph alpha : double
The parameter for the cut clustering algorithm
getClusterHierarchy
(Graph 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.
networkit.community.
EdgeListPartitionReader
Bases: object
Reads a partition from an edge list type of file
read
(self, path)networkit.community.
GraphClusteringTools
Bases: object
communicationGraph
(Graph graph, Partition zeta)equalClustering
(Partition zeta, Partition eta, Graph G)getImbalance
(Partition zeta)isOneClustering
(Graph G, Partition zeta)isProperClustering
(Graph G, Partition zeta)isSingletonClustering
(Graph G, Partition zeta)weightedDegreeWithCluster
(Graph graph, Partition zeta, node u, index cid)networkit.community.
GraphStructuralRandMeasure
Bases: _NetworKit.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
(self, Graph G, Partition first, Partition second)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, Saramäki 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
Calculates the dominance of hubs in the given Partition or Cover of the given Graph.
networkit.community.
InfomapAdapter
(G)Bases: object
getPartition
()infomapPath
= Nonerun
()setPath
(infomapPath)networkit.community.
IntrapartitionDensity
Bases: _NetworKit.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.
getGlobal
(self)Get the global intra-cluster density.
networkit.community.
IsolatedInterpartitionConductance
Bases: _NetworKit.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 Görke, Andrea Kappes and Dorothea Wagner, JEA 2015: http://dx.doi.org/10.1145/2638551
networkit.community.
IsolatedInterpartitionExpansion
Bases: _NetworKit.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 Görke, Andrea Kappes and Dorothea Wagner, JEA 2015: http://dx.doi.org/10.1145/2638551
networkit.community.
JaccardMeasure
Bases: _NetworKit.DissimilarityMeasure
TODO:
getDissimilarity
(self, Graph G, Partition first, Partition second)networkit.community.
LPDegreeOrdered
Bases: _NetworKit.CommunityDetector
Label propagation-based community detection algorithm which processes nodes in increasing order of node degree.
numberOfIterations
(self)Get number of iterations in last run.
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).
Modularity is defined as:
getQuality
(self, Partition zeta, Graph G)networkit.community.
NMIDistance
Bases: _NetworKit.DissimilarityMeasure
The NMI distance assigns a similarity value in [0,1] to two partitions of a graph.
getDissimilarity
(self, Graph G, Partition first, Partition second)networkit.community.
NodeStructuralRandMeasure
Bases: _NetworKit.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
(self, Graph G, Partition first, Partition second)networkit.community.
PLM
Bases: _NetworKit.CommunityDetector
Parallel Louvain Method - the Louvain method, optionally extended to a full multi-level algorithm with refinement
coarsen
(Graph G, Partition zeta, bool parallel=False)getTiming
(self)Get detailed time measurements.
prolong
(Graph Gcoarse, Partition zetaCoarse, Graph Gfine, vector[node] nodeToMetaNode)networkit.community.
PLP
Bases: _NetworKit.CommunityDetector
Parallel label propagation for community detection: Moderate solution quality, very short time to solution.
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
(self)Get list of running times for each iteration.
numberOfIterations
(self)Get number of iterations in last run.
networkit.community.
ParallelPartitionCoarsening
Bases: _NetworKit.GraphCoarsening
networkit.community.
Partition
Bases: object
Implements a partition of a set, i.e. a subdivision of the set into disjoint subsets.
Partition(z=0)
Create a new partition data structure for z elements.
addToSubset
(self, s, e)Add a (previously unassigned) element e to the set s.
allToSingletons
(self)Assigns every element to a singleton set. Set id is equal to element id.
compact
(self, useTurbo=False)Change subset IDs to be consecutive, starting at 0.
contains
(self, index e)Check if partition assigns a valid subset to the element e.
extend
(self)Extend the data structure and create a slot for one more element.
Initializes the entry to none and returns the index of the entry.
getMembers
(self, s)Get the members of the subset s.
getName
(self)Get the human-readable identifier.
getSubsetIds
(self)Get the ids of nonempty subsets.
getVector
(self)Get the actual vector representing the partition data structure.
inSameSubset
(self, index e1, index e2)Check if two elements e1 and e2 belong to the same subset.
lowerBound
(self)Get a lower bound for the subset ids that have been assigned.
mergeSubsets
(self, index s, index t)Assigns the elements from both sets to a new set and returns the id of it.
moveToSubset
(self, index s, index e)Move the (previously assigned) element e to the set `s.
numberOfElements
(self)numberOfSubsets
(self)Get the current number of sets in this partition.
setName
(self, string name)Set a human-readable identifier name for the instance.
setUpperBound
(self, index upper)Sets an upper bound for the subset ids that can be assigned.
subsetOf
(self, e)Get the set (id) in which the element e is contained.
subsetSizeMap
(self)Get a map from subset id to size of the subset.
subsetSizes
(self)Get a list of subset sizes. Indices do not necessarily correspond to subset ids.
toSingleton
(self, index e)Creates a singleton set containing the element e.
upperBound
(self)Return an upper bound for the subset ids that have been assigned. (This is the maximum id + 1.)
networkit.community.
PartitionFragmentation
Bases: _NetworKit.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.
networkit.community.
PartitionHubDominance
Bases: _NetworKit.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, Saramäki 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
networkit.community.
PartitionIntersection
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
(self, Partition zeta, Partition eta)Calculate the intersection of two partitions zeta and eta
networkit.community.
PartitionReader
Bases: object
Reads a partition from a file. File format: line i contains subset id of element i.
read
(self, path)networkit.community.
PartitionWriter
Bases: object
Writes a partition to a file. File format: line i contains subset id of element i.
write
(self, Partition zeta, path)networkit.community.
StablePartitionNodes
Bases: _NetworKit.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.
isStable
(self, node u)Check if a given node is stable, i.e. more connected to its own partition than to other partitions.
networkit.community.
communityGraph
(G, zeta)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
networkit.community.
compareCommunities
(G, zeta1, zeta2)Compare the partitions with respect to several (dis)similarity measures
networkit.community.
detectCommunities
(G, algo=None, inspect=True)Perform high-performance community detection on the graph. :param G the graph :param algorithm community detection algorithm instance :return communities (as type Partition)
networkit.community.
evalCommunityDetection
(algo, G)Evaluate a community detection algorithm
networkit.community.
inspectCommunities
(zeta, G)Display information about communities :param zeta communities :param G graph
networkit.community.
kCoreCommunityDetection
(G, k, algo=None, inspect=True)Perform community detection on the k-core of the graph, which possibly reduces computation time and enhances the result. :param G the graph (may not contain self-loops) :param k k as in k-core :param algorithm community detection algorithm instance :return communities (as type Partition)
networkit.community.
mesoscopicResponseFunction
(G, samples=100)networkit.community.
readCommunities
(path, format='default')Read a partition into communities from a file
networkit.community.
writeCommunities
(communities, path)Write a partition into communities to a file