networkit.sparsification

This module contains algorithms for the sparsification, i.e. edge filtering, of networks. The methods are described in detail in the publication ` Structure-Preserving Sparsification of Social Networks` at http://arxiv.org/abs/1505.00564

class networkit.sparsification.AdamicAdarDistance

Bases: object

Calculate the adamic adar similarity.

G : Graph
The input graph.
getAttribute(self)
vector[double]
The edge attribute that contains the adamic adar similarity.
preprocess(self)
class networkit.sparsification.AlgebraicDistanceSparsifier(numberSystems=10, numberIterations=30, omega=0.5, norm=0)

Bases: networkit.sparsification.Sparsifier

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

scores(G)

Returns the inverted algebraic distance score of the input graph.

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

Bases: object

Parameterizes a sparsification algorithm using binary search.

parameterize(algorithm, G, attribute, edgeRatio)
class networkit.sparsification.ChanceCorrectedTriangleScore

Bases: _NetworKit.EdgeScore

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

G : Graph
The input graph.
triangles : vector[count]
Triangle count.
class networkit.sparsification.ChibaNishizekiQuadrangleEdgeScore

Bases: _NetworKit.EdgeScore

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

G : Graph
The graph to count quadrangles on.
class networkit.sparsification.ChibaNishizekiTriangleEdgeScore

Bases: _NetworKit.EdgeScore

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

G : 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)

parameterize(algorithm, G, attribute, edgeRatio)
class networkit.sparsification.ConstantScore(constValue=1.0)

Bases: object

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

scores(G)

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

class networkit.sparsification.DegreeMultiscaleSparsifier(degsToAttrValue)

Bases: networkit.sparsification.Sparsifier

Multiscale Sparsifier that uses node degrees (mapped to edges) 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.

Keyword arguments: G – the input graph

class networkit.sparsification.EdgeScoreAsWeight

Bases: object

Assigns an edge score as edge weight of a graph.

G : Graph
The graph to assign edge weights to.
score : vector[double]
The input edge score.
squared : bool
Edge weights will be squared if set to True.
offset : edgeweight
This offset will be added to each edge weight.
factor : edgeweight
Each edge weight will be multiplied by this factor.
getWeightedGraph(self)
Graph
The weighted result graph.
class networkit.sparsification.EdgeScoreBlender

Bases: _NetworKit.EdgeScore

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

G : Graph
The graph for which the attribute shall be blended
attribute0 : vector[double]
The first attribute (chosen for selection[eid] == false)
attribute1 : vector[double]
The second attribute (chosen for selection[eid] == true)
selection : vector[bool]
The selection vector
class networkit.sparsification.EdgeScoreLinearizer

Bases: _NetworKit.EdgeScore

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

G : Graph
The input graph.
a : vector[double]
Edge score that shall be linearized.
class networkit.sparsification.EdgeScoreNormalizer

Bases: _NetworKit.EdgeScore

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

G : Graph
The graph the edge score is defined on.
score : vector[double]
The edge score to normalize.
inverse
Set to True in order to inverse the resulting score.
lower
Lower bound of the target range.
upper
Upper bound of the target range.
class networkit.sparsification.ForestFireScore

Bases: _NetworKit.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.

G : Graph
The graph to apply the Forest Fire algorithm to.
pf : double
The probability for neighbor nodes to get burned aswell.
tebr : double
The Forest Fire will burn until tebr * numberOfEdges edges have been burnt.
class networkit.sparsification.ForestFireSparsifier(burnProbability, targetBurntRatio)

Bases: networkit.sparsification.Sparsifier

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

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.

Keyword arguments: G – the input graph

class networkit.sparsification.GeometricMeanScore

Bases: _NetworKit.EdgeScore

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

G : Graph
The input graph.
a : vector[double]
Edge attribute that shall be normalized.
class networkit.sparsification.GlobalThresholdFilter

Bases: object

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

G : Graph
The graph to sparsify.
attribute : vector[double]
The edge attribute to consider for filtering.
e : double
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(self)
class networkit.sparsification.JaccardSimilarityAttributizer

Bases: object

The Jaccard similarity measure assigns to each edge (1 - the jaccard coefficient of the neighborhoods of the two adjacent nodes).

G : Graph
The graph to calculate Jaccard similarities for.
triangles : vector[count]
Previously calculated edge triangle counts.
getAttribute(self)
class networkit.sparsification.JaccardSimilaritySparsifier

Bases: networkit.sparsification.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

class networkit.sparsification.LocalDegreeScore

Bases: _NetworKit.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.

G : Graph
The graph to apply the Local Degree algorithm to.
class networkit.sparsification.LocalDegreeSparsifier

Bases: networkit.sparsification.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.

Keyword arguments: G – the input graph

class networkit.sparsification.LocalFilterScore

Bases: _NetworKit.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.

G : Graph
The input graph
a : list
The input attribute according to which the edges shall be fitlered locally.
logarithmic : bool
If the score shall be logarithmic in the rank (then d^e edges are kept). Linear otherwise.
class networkit.sparsification.LocalSimilarityScore

Bases: _NetworKit.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.

G : Graph
The graph to apply the Local Similarity algorithm to.
triangles : vector[count]
Previously calculated edge triangle counts.
class networkit.sparsification.LocalSimilaritySparsifier

Bases: networkit.sparsification.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.

Keyword arguments: G – the input graph

class networkit.sparsification.LocalSparsifier(sparsifier)

Bases: networkit.sparsification.Sparsifier

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.

Note that - like for all sparsifiers - edges with the highest score are the most important ones.

Keyword arguments: G – the input graph

class networkit.sparsification.ModularityPartitionScore

Bases: object

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.

Keyword arguments: G – the input graph

class networkit.sparsification.MultiscaleScore

Bases: _NetworKit.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.

G : Graph
The graph to apply the Multiscale algorithm to.
attribute : vector[double]
The edge attribute the Multiscale algorithm is to be applied to.
class networkit.sparsification.MultiscaleSparsifier

Bases: networkit.sparsification.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.

Keyword arguments: G – the input graph

class networkit.sparsification.PrefixJaccardScore

Bases: _NetworKit.EdgeScore

class networkit.sparsification.QuadrilateralSimmelianSparsifier

Bases: networkit.sparsification.Sparsifier

An implementation of the Simmelian Sparsifiers based on quadrangles.

scores(G)

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

Keyword arguments: G – the input graph

class networkit.sparsification.RandomEdgeScore

Bases: _NetworKit.EdgeScore

[todo]

G : Graph
The graph to calculate the Random Edge attribute for.
class networkit.sparsification.RandomEdgeSparsifier

Bases: networkit.sparsification.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.

Keyword arguments: G – the input graph

class networkit.sparsification.RandomNodeEdgeScore

Bases: _NetworKit.EdgeScore

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

G : Graph
The graph to calculate the Random Edge attribute for.
class networkit.sparsification.RandomNodeEdgeSparsifier(above=True)

Bases: networkit.sparsification.Sparsifier

[TODO not yet documented]

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.

Keyword arguments: G – the input graph

class networkit.sparsification.SCANSparsifier

Bases: networkit.sparsification.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.

Keyword arguments: G – the input graph

class networkit.sparsification.SCANStructuralSimilarityScore

Bases: _NetworKit.EdgeScore

class networkit.sparsification.SimmelianMultiscaleSparsifier

Bases: networkit.sparsification.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.

Keyword arguments: G – the input graph

class networkit.sparsification.SimmelianOverlapScore

Bases: _NetworKit.EdgeScore

class networkit.sparsification.SimmelianSparsifierNonParametric

Bases: networkit.sparsification.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.

Keyword arguments: G – the input graph

class networkit.sparsification.SimmelianSparsifierParametric(maxRank)

Bases: networkit.sparsification.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.

Keyword arguments: G – 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.)

Keyword arguments: algorithm – the sparsification algorithm G – the input graph attribute – precalculated edge attribute edgeRatio – target edge ratio the resulting parameter value should yield

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.

getSparsifiedGraph(G, parameter, attribute=None)

Returns a sparsified version of the given input graph.

Keyword arguments: G – the input graph parameter – a parameter value that determines the degree of sparsification attribute – (optional) a previously calculated edge attribute. If none is provided, we will try to calculate it.

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.

Keyword arguments: G – the input graph edgeRatio – the target edge ratio attribute – (optional) a previously calculated edge attribute. If none is provided, we will try to calculate it.

scores(G)

Returns an edge attribute. (To be implemented by derived class)

Keyword arguments: G – the input graph

class networkit.sparsification.TriangleEdgeScore

Bases: _NetworKit.EdgeScore

Triangle counting.

G : Graph
The graph to count triangles on.
class networkit.sparsification.TriangleSparsifier

Bases: networkit.sparsification.Sparsifier

Allows for global filtering with respect to triangle counts.

scores(G)

Returns the triangle counts of 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.

Keyword arguments: attribute – the input node/edge attribute reverse – reverses the ranking, if set to True