networkit.sparsification¶

class networkit.sparsification.AlgebraicDistanceSparsifier(numberSystems=10, numberIterations=30, omega=0.5, norm=0)¶

Bases: Sparsifier

Allows for global filtering with respect to (inverted) algebraic distances.

Parameters:

numberSystems (int, optional) – Number of vectors/systems used for algebraic iteration. Default: 10
numberIterations (int, optional) – Number of iterations in each system. Default: 30
omega (float, optional) – Attenuation factor in [0,1] influencing convergence speed. Default: 0.5
norm (int, optional) – The norm factor of the extended algebraic distance. Default: 0

scores(G)¶

Returns the inverted algebraic distance score of the input graph.

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

class networkit.sparsification.BinarySearchParameterization(sizeIncreasesWithParameter, lowerParameterBound, upperParameterBound, maxSteps)¶

Bases: object

Parameterizes a sparsification algorithm using binary search.

Parameters:

sizeIncreasesWithParameter (bool) – Set to True if the size of the sparsified graph increases with increasing parameter value.
lowerParameterBound (float) – Lower bound of the parameter domain (inclusive).
upperParameterBound (float) – Upper bound of the parameter domain (inclusive).
maxSteps (int) – The maximum number of steps to perform during binary search.

parameterize(algorithm, G, attribute, edgeRatio)¶

Parameterize the given sparsifier for the given input graph with the given target edge ratio. (To be implemented by derived class.)

Parameters:

algorithm (networkit.sparsification.Sparsifier) – The sparsification algorithm.
G (networkit.Graph) – The input graph.
attribute (list(float)) – An input edge attribute.
edgeRatio (float) – The target edge ratio.

class networkit.sparsification.ChanceCorrectedTriangleScore(G, triangles)¶

Bases: EdgeScore

Divide the number of triangles per edge by the expected number of triangles given a random edge distribution.

Parameters:

G (networkit.Graph) – The input graph.
triangles (list(int)) – Triangle count.

class networkit.sparsification.ChibaNishizekiQuadrangleEdgeScore(G)¶

Bases: EdgeScore

Calculates for each edge the number of quadrangles (circles of length 4) it is embedded in.

Parameters:: G (networkit.Graph) – The graph to count quadrangles on.

class networkit.sparsification.ChibaNishizekiTriangleEdgeScore(G)¶

Bases: EdgeScore

Calculates for each edge the number of triangles it is embedded in.

Parameters:: G (networkit.Graph) – The graph to count triangles on.

class networkit.sparsification.CompleteSearchParameterization(lowerParameterBound, upperParameterBound)¶

Bases: object

Parameterizes a sparsification algorithm using complete search (applicable only to algorithms which take as input a parameter from a small set of possible values).

Parameters:

lowerParameterBound (int) – Lower bound of the parameter domain (inclusive).
upperParameterBound (int) – Upper bound of the parameter domain (inclusive).

parameterize(algorithm, G, attribute, edgeRatio)¶

Parameterize the given sparsifier for the given input graph with the given target edge ratio. (To be implemented by derived class.)

Parameters:

algorithm (networkit.sparsification.Sparsifier) – The sparsification algorithm.
G (networkit.Graph) – The input graph.
attribute (list(float)) – An input edge attribute.
edgeRatio (float) – The target edge ratio.

class networkit.sparsification.ConstantScore(constValue=1.0)¶

Bases: object

Assigns as an attribute the same value to each edge (for sanity checks).

Parameters:: constValue (float, optional) – Value to assign to each edge. Default: 1.0

scores(G)¶

Returns an edge attribute that holds for each edge the constant value given in the constructor.

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

class networkit.sparsification.DegreeMultiscaleSparsifier(degsToAttrValue)¶

Bases: Sparsifier

Multiscale Sparsifier that uses node degrees (mapped to edges) as input edge weight.

Parameters:: degsToAttrValue (function) – Function that maps two node degrees to an edge score.

scores(G)¶

Returns an edge attribute that holds for each edge the maximum parameter value such that the edge is contained in the sparsified graph.

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

class networkit.sparsification.EdgeScore¶

Bases: Algorithm

Abstract base class for an edge score.

score(u, v=None)¶

Get a vector containing the score for a certain edge connecting node u and v.

Parameters:

u (int) – The first node.
v (int, optional) – The second node. Default: None

Returns:

List with scores. Scores are either int-values (unweighted) or float-values (weighted).

Return type:

list(int) or list(float)

scores()¶

Get a vector containing the score for each edge in the graph.

Returns:: List with scores. Scores are either int-values (unweighted) or float-values (weighted).
Return type:: list(int) or list(float)

class networkit.sparsification.EdgeScoreAsWeight(G, score, square, offset, factor)¶

Bases: object

Assigns an edge score as edge weight of a graph.

Parameters:

G (networkit.Graph) – The graph to assign edge weights to.
score (list(float)) – The input edge score.
squared (bool) – Edge weights will be squared if set to True.
offset (float) – This offset will be added to each edge weight.
factor (float) – Each edge weight will be multiplied by this factor.

getWeightedGraph()¶

Returns:: The weighted result graph.
Return type:: networkit.Graph

class networkit.sparsification.EdgeScoreBlender(G, attribute0, attribute1, selection)¶

Bases: EdgeScore

Blends two attribute vectors, the value is chosen depending on the supplied bool vector

Parameters:

G (networkit.Graph) – The graph for which the attribute shall be blended
attribute0 (list(float)) – The first attribute (chosen for selection[eid] == False)
attribute1 (list(float)) – The second attribute (chosen for selection[eid] == True)
selection (list(bool)) – The selection vector.

class networkit.sparsification.EdgeScoreLinearizer(G, a, inverse=False)¶

Bases: EdgeScore

Linearizes a score such that values are evenly distributed between 0 and 1.

Parameters:

G (networkit.Graph) – The input graph.
a (list(float)) – Edge score that shall be linearized.
inverse (bool, optional) – Set to True in order to inverse the resulting score. Default: False

class networkit.sparsification.EdgeScoreNormalizer(G, score, inverse=False, lower=0.0, uppper=1.0)¶

Bases: EdgeScore

Normalize an edge score such that it is in a certain range.

Parameters:

G (networkit.Graph) – The graph the edge score is defined on.
score (list(float)) – The edge score to normalize.
inverse (bool, optional) – Set to True in order to inverse the resulting score. Default: False
lower (float, optional) – Lower bound of the target range. Default: 0.0
upper (float, optional) – Upper bound of the target range. Default: 1.0

class networkit.sparsification.ForestFireScore(G, pf, tebr)¶

Bases: EdgeScore

A variant of the Forest Fire sparsification approach that is based on random walks. This attributizer calculates for each edge the minimum parameter value such that the edge is still contained in the sparsified graph.

Parameters:

G (networkit.Graph) – The graph to apply the Forest Fire algorithm to.
pf (float) – The probability for neighbor nodes to get burned aswell.
tebr (float) – The Forest Fire will burn until tebr * numberOfEdges edges have been burnt.

class networkit.sparsification.ForestFireSparsifier(burnProbability, targetBurntRatio)¶

Bases: Sparsifier

A variant of the Forest Fire sparsification approach proposed by Leskovec et al.

Parameters:

burnProbability (float) – The probability that the neighbor of a burnt node gets burnt as well.
edgeRatio (float) – The fires will stop when a edgeRatio * edgeCount edges have been burnt.

scores(G)¶

Returns an edge attribute that holds for each edge the maximum parameter value such that the edge is contained in the sparsified graph.

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

class networkit.sparsification.GeometricMeanScore(G, a)¶

Bases: EdgeScore

Normalizes the given edge attribute by the geometric average of the sum of the attributes of the incident edges of the incident nodes.

Parameters:

G (networkit.Graph) – The input graph.
a (list(float)) – Edge attribute that shall be normalized.

class networkit.sparsification.GlobalThresholdFilter(G, attribute, e, above)¶

Bases: object

Calculates a sparsified graph by filtering globally using a constant threshold value and a given edge attribute.

Parameters:

G (networkit.Graph) – The graph to sparsify.
attribute (list(float)) – The edge attribute to consider for filtering.
e (float) – Threshold value.
above (bool) – If set to True (False), all edges with an attribute value equal to or above (below) will be kept in the sparsified graph.

calculate()¶

class networkit.sparsification.JaccardSimilaritySparsifier¶

Bases: Sparsifier

An implementation of the Jaccard Similarity sparsification approach introduced by Satuluri et al.

scores(G)¶

Returns the jaccard coefficient of the neighborhoods of the two incident nodes.

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

class networkit.sparsification.LocalDegreeScore(G)¶

Bases: EdgeScore

The LocalDegree sparsification approach is based on the idea of hub nodes. This attributizer calculates for each edge the maximum parameter value such that the edge is still contained in the sparsified graph.

Parameters:: G (networkit.Graph) – The graph to apply the Local Degree algorithm to.

class networkit.sparsification.LocalDegreeSparsifier¶

Bases: Sparsifier

An implementation of the Local Degree sparsification algorithm.

scores(G)¶

Returns an edge score that holds for each edge the minimum parameter value such that the edge is contained in the sparsified graph.

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

class networkit.sparsification.LocalFilterScore(G, a, logarithmic=True)¶

Bases: EdgeScore

Local filtering edge scoring. Edges with high score are more important.

Edges are ranked locally, the top d^e (logarithmic, default) or 1+e*(d-1) edges (non-logarithmic) are kept. For equal attribute values, neighbors of low degree are preferred. If bothRequired is set (default: false), both neighbors need to indicate that they want to keep the edge.

Parameters:

G (networkit.Graph) – The input graph
a (list(float)) – The input attribute according to which the edges shall be fitlered locally.
logarithmic (bool, optional) – If the score shall be logarithmic in the rank (then d^e edges are kept), linear otherwise. Default: True

class networkit.sparsification.LocalSimilarityScore(G, triangles)¶

Bases: EdgeScore

An implementation of the Local Simlarity sparsification approach. This attributizer calculates for each edge the maximum parameter value such that the edge is still contained in the sparsified graph.

Parameters:

G (networkit.Graph) – The graph to apply the Local Similarity algorithm to.
triangles (list(int)) – Previously calculated edge triangle counts.

class networkit.sparsification.LocalSimilaritySparsifier¶

Bases: Sparsifier

An implementation of the Local Similarity sparsification approach introduced by Satuluri et al.

scores(G)¶

Returns an edge attribute that holds for each edge the minimum parameter value such that the edge is contained in the sparsified graph.

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

class networkit.sparsification.LocalSparsifier(sparsifier)¶

Bases: Sparsifier

Sparsification algorithm using an input sparsifier and passing the result of this algorithm to networkit.sparsification.LocalFilterScore for choosing edges, which should be present in the sparsified graph.

scores(G)¶

Returns an edge attribute that holds for each edge 1 - the minimum parameter value such that the edge is contained in the sparsified graph.

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

class networkit.sparsification.ModularityPartitionScore¶

Bases: object

Sparsification algorithm using networkit.community.PLM algorithm to detect communities and select only edges, where both ends are member of the same community.

scores(G)¶

Returns an edge attribute that holds for each edge the minimum parameter value such that the edge is contained in the sparsified graph.

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

class networkit.sparsification.MultiscaleScore(G, attribute)¶

Bases: EdgeScore

An implementation of the Multiscale Backbone. Calculates for each edge the minimum parameter value such that the edge is still contained in the sparsified graph.

Parameters:

G (networkit.Graph) – The graph to apply the Multiscale algorithm to.
attribute (list(float)) – The edge attribute the Multiscale algorithm is to be applied to.

class networkit.sparsification.MultiscaleSparsifier¶

Bases: Sparsifier

An implementation of the Multiscale backbone approach introduced by Serrano et al.

scores(G)¶

Returns an edge attribute that holds for each edge the minimum parameter value such that the edge is contained in the sparsified graph.

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

class networkit.sparsification.PrefixJaccardScore¶: Bases: EdgeScore

class networkit.sparsification.QuadrilateralSimmelianSparsifier¶

Bases: Sparsifier

An implementation of the Simmelian Sparsifiers based on quadrangles.

scores(G)¶

Returns an edge scoring attribute that can be used for global filtering.

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

class networkit.sparsification.RandomEdgeScore(G)¶

Bases: EdgeScore

Generates a random edge attribute. Each edge is assigned a random value in [0,1].

Parameters:: G (networkit.Graph) – The graph to calculate the Random Edge attribute for.

class networkit.sparsification.RandomEdgeSparsifier¶

Bases: Sparsifier

Random Edge sampling. Edges to keep in the sparsified graph are selected uniformly at random.

scores(G)¶

Returns an edge attribute that holds for each edge the minimum parameter value such that the edge is contained in the sparsified graph.

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

class networkit.sparsification.RandomNodeEdgeScore(G)¶

Bases: EdgeScore

Random Edge sampling. This attributizer returns edge attributes where each value is selected uniformly at random from [0,1].

Parameters:: G (networkit.Graph) – The graph to calculate the Random Edge attribute for.

class networkit.sparsification.RandomNodeEdgeSparsifier¶

Bases: Sparsifier

Random Edge sampling. Edges and nodes to keep in the sparsified graph are selected uniformly at random.

Parameters:: above (bool, optional) – If set to True (False), all nodes and edges with an attribute value equal to or above (below) will be kept in the sparsified graph. Default: True

scores(G)¶

Returns an edge attribute that holds for each edge the minimum parameter value such that the edge is contained in the sparsified graph.

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

class networkit.sparsification.SCANSparsifier¶

Bases: Sparsifier

A sparsifiier dervived from ‘SCAN: a structural clustering algorithm for networks’

scores(G)¶

Returns an edge attribute that holds for each edge the minimum parameter value such that the edge is contained in the sparsified graph.

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

class networkit.sparsification.SCANStructuralSimilarityScore(G, triangles)¶

Bases: EdgeScore

An implementation of the SCANStructuralSimilarityScore algorithm.

Parameters:

G (networkit.Graph) – The graph to apply the Local Similarity algorithm to.
triangles (list(int)) – Previously calculated edge triangle counts.

class networkit.sparsification.SimmelianMultiscaleSparsifier¶

Bases: Sparsifier

Multiscale Sparsifier that uses triangle counts as input edge weight.

scores(G)¶

Returns an edge attribute that holds for each edge the maximum parameter value such that the edge is contained in the sparsified graph.

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

class networkit.sparsification.SimmelianOverlapScore(G, triangles, maxRank)¶

Bases: EdgeScore

An implementation of the parametric variant of Simmelian Backbones. Calculates for each edge the minimum parameter value such that the edge is still contained in the sparsified graph.

Parameters:

G (networkit.Graph) – The graph to apply the Simmelian Backbone algorithm to.
triangles (list(int)) – Previously calculated edge triangle counts on G.
maxRank (int) – Maximum rank that is considered for overlap calculation.

class networkit.sparsification.SimmelianSparsifierNonParametric¶

Bases: Sparsifier

An implementation of the Non-parametric variant of the Simmelian Sparsifiers introduced by Nick et al.

scores(G)¶

Returns an edge attribute that holds for each edge the minimum jaccard filter value such that the edge is contained in the sparsified graph.

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

class networkit.sparsification.SimmelianSparsifierParametric¶

Bases: Sparsifier

An implementation of the Parametric variant of the Simmelian Sparsifiers introduced by Nick et al.

scores(G)¶

Returns an edge attribute that holds for each edge the minimum parameter value such that the edge is contained in the sparsified graph.

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

class networkit.sparsification.SimpleParameterization¶

Bases: object

A parameterization algorithm representds an algorithm that, given a graph and a sparsifier, calculates a parameter value such that a desired edge ratio is met. The SimpleParameterization strategy simply returns the input edgeRatio as parameterization result.

parameterize(algorithm, G, attribute, edgeRatio)¶

Parameterize the given sparsifier for the given input graph with the given target edge ratio. (To be implemented by derived class.)

Parameters:

algorithm (networkit.sparsification.Sparsifier) – The sparsification algorithm.
G (networkit.Graph) – The input graph.
attribute (list(float)) – An input edge attribute.
edgeRatio (float) – The target edge ratio.

class networkit.sparsification.Sparsifier¶

Bases: object

Abstract base class representing a graph sparsification algorithm that uses only one parameter to determine the degree of filtering.

getParameter(G, edgeRatio, attribute=None)¶

This is a convenience function that applies an appropriate parameterization algorithm (if available) to obtain a parameter value that yields a sparsified graph of the desired size.

Parameters:

G (networkit.Graph) – The input graph.
edgeRatio (float) – The target edge ratio.
attribute (list(float), optional) – A previously calculated edge attribute. If none is provided, we will try to calculate it. Default: None

getSparsifiedGraph(sG, parameter, attribute=None)¶

Returns a sparsified version of the given input graph.

Parameters:

G (networkit.Graph) – The input graph.
parameter (float) – A parameter value that determines the degree of sparsification
attribute (list(float), optional) – A previously calculated edge attribute. If none is provided, we will try to calculate it. Default: None

getSparsifiedGraphOfSize(G, edgeRatio, attribute=None)¶

This is a convenience function that applies an appropriate parameterization algorithm (if available) to obtain a parameter value that yields a sparsified graph of the desired size and then calls getSparsifiedGraph(…) with that parameter value.

Parameters:

G (networkit.Graph) – The input graph.
edgeRatio (float) – The target edge ratio.
attribute (list(float), optional) – A previously calculated edge attribute. If none is provided, we will try to calculate it. Default: None

Returns:

The sparsified graph.

Return type:

networkit.Graph

scores(G)¶

Returns an edge attribute.

Parameters:: G (networkit.Graph) – The input graph.
Returns:: Edge scores.
Return type:: list(float)

class networkit.sparsification.TriangleEdgeScore(G)¶

Bases: EdgeScore

Triangle counting.

Parameters:: G (networkit.Graph) – The graph to count triangles on.

class networkit.sparsification.TriangleSparsifier¶

Bases: Sparsifier

Allows for global filtering with respect to triangle counts.

scores(G)¶

Returns the triangle counts of the input graph.

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

networkit.sparsification.getRankAttribute(attribute, reverse=False)¶

Takes as input an attribute (node or edge) and returns an attribute where each node is assigned its rank among all others according to the attribute values. The node/edge with lowest input value is assigned 0, the one with second-lowest value 1, and so on.

Parameters:

attribute (list(float)) – The input node/edge attribute
reverse (bool, optional) – Reverses the ranking, if set to True. Default: False