networkit.community

This module handles community detection, i.e. the discovery of densely connected groups in networks.

class 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.

G : Graph
The graph on which the partitions shall be compared
zeta : Partition
The first partiton
eta : Partition
The second partition
double
The adjusted rand dissimilarity
class 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

G: Graph
The graph for which the clustering shall be generated
k: count
The number of clusters that shall be generated
Partition
The generated partition
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.

G: Graph
The graph for which the clustering shall be generated
k: count
The number of clusters that shall be generated
Partition
The generated partition
makeOneClustering(self, Graph G)

Generate a clustering with one cluster consisting of all nodes

G: Graph
The graph for which the clustering shall be generated
Partition
The generated partition
makeRandomClustering(self, Graph G, count k)

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

G: Graph
The graph for which the clustering shall be generated
k: count
The number of clusters that shall be generated
Partition
The generated partition
makeSingletonClustering(self, Graph G)

Generate a clustering where each node has its own cluster

G: Graph
The graph for which the clustering shall be generated
Partition
The generated partition
class networkit.community.CommunityDetector(*args, **namedargs)

Bases: _NetworKit.Algorithm

Abstract base class for static community detection algorithms

getPartition(self)

Returns a partition of the clustering.

Partition:
A Partition of the clustering.
class 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.

G : Graph
The graph.
normalized : boolean
Divide each core number by the maximum degree.
enforceBucketQueueAlgorithm : boolean
enforce switch to sequential algorithm
storeNodeOrder : boolean
If set to True, the order of the nodes in ascending order of the cores is stored and can later be returned using getNodeOrder(). Enforces the sequential bucket priority queue algorithm.
getCover(self)

Get the k-cores as cover.

vector
The k-cores as sets of nodes, indexed by k.
getNodeOrder(self)

Get the node order.

This is only possible when storeNodeOrder was set.

list
The nodes sorted by increasing core number.
getPartition(self)

Get the k-shells as a partition object.

Partition
The k-shells
maxCoreNumber(self)

Get maximum core number.

index
The maximum core number.
class 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

G : Graph
The graph on which the measure shall be evaluated
C : Cover
The cover that shall be evaluated
class networkit.community.Coverage

Bases: object

Coverage is the fraction of intra-community edges

getQuality(self, Partition zeta, Graph G)
class 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
static 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.

G : Graph
The graph.
dict
A dictionary with the parameter values as keys and the corresponding Partition instances as values
class networkit.community.EdgeListPartitionReader

Bases: object

Reads a partition from an edge list type of file

read(self, path)
class networkit.community.GraphClusteringTools

Bases: object

static communicationGraph(Graph graph, Partition zeta)
static equalClustering(Partition zeta, Partition eta, Graph G)
static getImbalance(Partition zeta)
static isOneClustering(Graph G, Partition zeta)
static isProperClustering(Graph G, Partition zeta)
static isSingletonClustering(Graph G, Partition zeta)
static weightedDegreeWithCluster(Graph graph, Partition zeta, node u, index cid)
class 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)
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, 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.

zeta : Partition or Cover
The Partition or Cover for which the hub dominance shall be calculated
G : Graph
The Graph to which zeta belongs
double
The average hub dominance in the given Partition or Cover
class networkit.community.InfomapAdapter(G)

Bases: object

getPartition()
infomapPath = None
run()
classmethod setPath(infomapPath)
class 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.

G : Graph
The graph on which the measure shall be evaluated
P : Partition
The partition that shall be evaluated
getGlobal(self)

Get the global intra-cluster density.

double:
The global intra-cluster density.
class 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

G : Graph
The graph on which the measure shall be evaluated
P : Partition
The partition that shall be evaluated
class 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

G : Graph
The graph on which the measure shall be evaluated
P : Partition
The partition that shall be evaluated
class networkit.community.JaccardMeasure

Bases: _NetworKit.DissimilarityMeasure

TODO:

getDissimilarity(self, Graph G, Partition first, Partition second)
class 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.

count
Number of iterations.
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).

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(self, Partition zeta, Graph G)
class 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)
class 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)
class networkit.community.PLM

Bases: _NetworKit.CommunityDetector

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

G : Graph
A graph.
refine : bool, optional
Add a second move phase to refine the communities.
gamma : double
Multi-resolution modularity parameter: 1.0 -> standard modularity 0.0 -> one community 2m -> singleton communities
par : string
parallelization strategy
maxIter : count
maximum number of iterations for move phase
turbo : bool, optional
faster but uses O(n) additional memory per thread
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(Graph G, Partition zeta, bool parallel=False)
getTiming(self)

Get detailed time measurements.

static prolong(Graph Gcoarse, Partition zetaCoarse, Graph Gfine, vector[node] nodeToMetaNode)
class 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.

count
The list of running times in milliseconds.
numberOfIterations(self)

Get number of iterations in last run.

count
The number of iterations.
class networkit.community.ParallelPartitionCoarsening

Bases: _NetworKit.GraphCoarsening

class 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.

size : index, optional
Maximum index of an element. Default is 0.
addToSubset(self, s, e)

Add a (previously unassigned) element e to the set s.

s : index
The index of the subset.
e : index
The element to add.
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.

useTurbo : bool
Default: false. If set to true, a vector instead of a map to assign new ids which results in a shorter running time but possibly a large space overhead.
contains(self, index e)

Check if partition assigns a valid subset to the element e.

e : index
The element.
bool
True if the assigned subset is valid, False otherwise.
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.

index
The index of the new element.
getMembers(self, s)

Get the members of the subset s.

s : index
The subset.
set
A set containing the members of `s.
getName(self)

Get the human-readable identifier.

string
The name of this partition.
getSubsetIds(self)

Get the ids of nonempty subsets.

set
A set of ids of nonempty subsets.
getVector(self)

Get the actual vector representing the partition data structure.

vector
Vector containing information about partitions.
inSameSubset(self, index e1, index e2)

Check if two elements e1 and e2 belong to the same subset.

e1 : index
An Element.
e2 : index
An Element.
bool
True if e1 and e2 belong to same subset, False otherwise.
lowerBound(self)

Get a lower bound for the subset ids that have been assigned.

index
The lower bound.
mergeSubsets(self, index s, index t)

Assigns the elements from both sets to a new set and returns the id of it.

s : index
Set to merge.
t : index
Set to merge.
index
Id of newly created set.
moveToSubset(self, index s, index e)

Move the (previously assigned) element e to the set `s.

s : index
The index of the subset.
e : index
The element to move.
numberOfElements(self)
count
Number of elements in the partition.
numberOfSubsets(self)

Get the current number of sets in this partition.

count
The current number of sets.
setName(self, string name)

Set a human-readable identifier name for the instance.

name : string
The name.
setUpperBound(self, index upper)

Sets an upper bound for the subset ids that can be assigned.

upper : index
Highest assigned subset id + 1
subsetOf(self, e)

Get the set (id) in which the element e is contained.

e : index
Index of element.
index
The index of the set in which e is contained.
subsetSizeMap(self)

Get a map from subset id to size of the subset.

dict
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.

vector
A vector of subset sizes.
toSingleton(self, index e)

Creates a singleton set containing the element e.

e : index
The index of the element.
upperBound(self)

Return an upper bound for the subset ids that have been assigned. (This is the maximum id + 1.)

index
The upper bound.
class 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.

G : Graph
The graph on which the measure shall be evaluated
P : Partition
The partition that shall be evaluated
class 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

G : Graph
The graph on which the measure shall be evaluated
P : Partition
The partition that shall be evaluated
class 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

zeta: Partition
The first partition
eta: Partition
The second partition
Partition
The intersection of zeta and eta
class networkit.community.PartitionReader

Bases: object

Reads a partition from a file. File format: line i contains subset id of element i.

read(self, path)
class 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)
class 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.

G : Graph
The graph on which the measure shall be evaluated
P : Partition
The partition that shall be evaluated
isStable(self, node u)

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

u : node
The node to check
bool
If the node u is stable.
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