<jupyter_start><jupyter_text>NetworKit Sparsification Tutorial This notebook covers the NetworKit sparsification module, which provides algorithms to compute edge scores and to sparsify an input graph.Sparsification algorithms rely on edge scores, therefore graph edges must be indexed. Call the [indexEdges()](https://networkit.github.io/dev-docs/python_api/networkit.html?highlight=indexedgesnetworkit.Graph.indexEdges) function to do so. Every sparsification algorithm computing edge scores in NetworKit provides a `scores()` function that returns the edge attributes maximum parameter value such that the edge is contained in the sparsified graph.The [getSparsifiedGraph(G, parameter, attribute)](https://networkit.github.io/dev-docs/python_api/sparsification.html?highlight=getsparsifnetworkit.sparsification.Sparsifier.getSparsifiedGraph) or [getSparsifiedGraphOfSize(G, edgeRatio, attribute)](https://networkit.github.io/dev-docs/python_api/sparsification.html?highlight=getsparsifnetworkit.sparsification.Sparsifier.getSparsifiedGraphOfSize) functions return the sparsified graph. `parameter` determines the degree of sparsification, while `edgeRatio` is the target edge ratio of the specified graph. `attribute` is an optional parameter representing a previously calculated edge attribute.<jupyter_code>import networkit as nk
G = nk.readGraph("../input/jazz.graph", nk.Format.METIS)
G.indexEdges()
G.numberOfNodes(), G.numberOfEdges()<jupyter_output><empty_output><jupyter_text>All sparsification algorithms need an `edgeRatio` parameter. We use the same `edgeRatio` in all our examples.<jupyter_code>targetRatio = 0.2<jupyter_output><empty_output><jupyter_text>Forest Fire  The Forest Fire sparsifier implements a variant of the Forest Fire sparsification approach that is based on random walks.  Edge Scores The [ForestFireScore(G, pf, tebr)]() constructor expects as inputs a graph, the probability `pf` that the neighbor nodes will burn as well, and the target burn ratio which states that forest fire will burn until `tebr * m` edges have been burnt (where `m` is the number of edges of `G`).<jupyter_code># Initialize the algorithm
ffs = nk.sparsification.ForestFireScore(G, 0.6, 5.0)

# Run
ffs.run()

# Get edge scores
attributes = ffs.scores()
for attribute in attributes[:5]:
    print("{:.3f}".format(attribute))<jupyter_output><empty_output><jupyter_text>Sparsification The [ForestFireSparsifier(burnProbability, targetBurntRatio)]() constructor expects as inputs the probability `burnProbability` that the neighbor nodes will burn as well, and the target burn ratio which states that forest fire will burn until `targetBurntRatio * m` edges have been burnt.<jupyter_code># Initialize the algorithm
fireSparsifier = nk.sparsification.ForestFireSparsifier(0.6, 5.0)

# Get sparsified graph
fireGraph = fireSparsifier.getSparsifiedGraphOfSize(G, targetRatio)
G.numberOfEdges(), fireGraph.numberOfEdges()<jupyter_output><empty_output><jupyter_text>Global Threshold Filter  The Global Threshold Filter calculates a sparsified graph by filtering globally using a constant threshold value and a given edge attribute.The [GlobalThresholdFilter(G, attribute, e, above)](https://networkit.github.io/dev-docs/python_api/sparsification.html?highlight=globalthnetworkit.sparsification.GlobalThresholdFilter) constructor expects as inputs a graph, a list of edge attributes, a threshold value `e` and a boolean value `above`. If `above` is set to `True`, all edges with an attribute value greater than or equal `e` will be kept in the sparsified graph. The `calculate` method returns the sparsified graph.  Sparsification<jupyter_code># Initialize the algorithm
gtf = nk.sparsification.GlobalThresholdFilter(G, attributes, 0.2, False)

# Run
newG = gtf.calculate()
G.numberOfEdges(), newG.numberOfEdges()<jupyter_output><empty_output><jupyter_text>Local Degree The local degree sparsification strategy is based on the idea of hub nodes. For each edge of the graph, it determines the maximum parameter value such that the edge is still contained in the sparsified graph.  Edge Scores The [LocalDegreeScore(G)](https://networkit.github.io/dev-docs/python_api/sparsification.html?highlight=local%20degreenetworkit.sparsification.LocalDegreeScore) constructor expects a graph as input.<jupyter_code># Initialize the algorithm
lds = nk.sparsification.LocalDegreeScore(G)

# Run
lds.run()

# Get edge scores
ldsScores = lds.scores()
for score in ldsScores[:5]:
    print("{:.3f}".format(score))<jupyter_output><empty_output><jupyter_text>Sparsification<jupyter_code># Initialize the algorithm
localDegSparsifier = nk.sparsification.LocalDegreeSparsifier()

# Get sparsified graph
localDegGraph = localDegSparsifier.getSparsifiedGraphOfSize(G, targetRatio)
G.numberOfEdges(), localDegGraph.numberOfEdges()<jupyter_output><empty_output><jupyter_text>Local Similarity  Edge Scores The [LocalSimilarityScore(G, triangles)](https://networkit.github.io/dev-docs/python_api/sparsification.html?highlight=localnetworkit.sparsification.LocalSimilarityScore) constructor expects a graph and previously calculated edge triangle counts of the graph.The edge triangles can be computed using the [TriangleEdgeScore(G)](https://networkit.github.io/dev-docs/python_api/sparsification.html?highlight=trianglenetworkit.sparsification.TriangleEdgeScore) algorithm.<jupyter_code># Compute triangles in G
e_triangles = nk.sparsification.TriangleEdgeScore(G)
e_triangles.run()
triangles = e_triangles.scores()
# Initialize the algorithm
lss = nk.sparsification.LocalSimilarityScore(G, triangles)

# Run
lss.run()

# Get edge scores
scores = lss.scores()
for score in scores[:5]:
    print("{:.3f}".format(score))<jupyter_output><empty_output><jupyter_text>Sparsification<jupyter_code># Initialize the algorithm
similaritySparsifier = nk.sparsification.LocalSimilaritySparsifier()

# Get sparsified graph
similarityGraph = similaritySparsifier.getSparsifiedGraphOfSize(G, targetRatio)
G.numberOfEdges(), similarityGraph.numberOfEdges()<jupyter_output><empty_output><jupyter_text>Random Edge Score This strategy assigns to each edge a random value in [0,1].  Edge Scores The [RandomEdgeScore(G)](https://networkit.github.io/dev-docs/python_api/sparsification.html?highlight=randomedgenetworkit.sparsification.RandomEdgeScore) constructor expects a graph as input.<jupyter_code># Initialize
res = nk.sparsification.RandomEdgeScore(G)

# Run
res.run()

# Get edge scores
randomEdgeScores = res.scores()
for score in randomEdgeScores[:5]:
    print("{:.3f}".format(score))<jupyter_output><empty_output><jupyter_text>Sparsification<jupyter_code># Initialize the algorithm
randomEdgeSparsifier = nk.sparsification.RandomEdgeSparsifier()

# Get sparsified graph
randomGraph = randomEdgeSparsifier.getSparsifiedGraphOfSize(G, targetRatio)
G.numberOfEdges(), randomGraph.numberOfEdges()<jupyter_output><empty_output><jupyter_text>Random Node Edge Score This attributizer returns edge attributes where each value is selected uniformly at random from [0,1].  Edge Scores The [RandomNodeEdgeScore(G)](https://networkit.github.io/dev-docs/python_api/sparsification.html?highlight=randomnodenetworkit.sparsification.RandomNodeEdgeScore) constructor expects a graph as input.<jupyter_code># Initialize
rn = nk.sparsification.RandomNodeEdgeScore(G)

# Run
rn.run()

# Get edge scores
randomNodeScores = rn.scores()
for score in randomNodeScores[:5]:
    print("{:.3f}".format(score))<jupyter_output><empty_output><jupyter_text>Sparsification<jupyter_code># Initialize the algorithm
randomNodeEdgeSparsifier = nk.sparsification.RandomNodeEdgeSparsifier()

# Get sparsified graph
randomNodeGraph = randomNodeEdgeSparsifier.getSparsifiedGraphOfSize(G, targetRatio)
G.numberOfEdges(), randomNodeGraph.numberOfEdges()<jupyter_output><empty_output><jupyter_text>SCAN Structural Similarity Score This algorithm is a Structural Clustering Algorithm for Networks (SCAN) whose goal is to find clusters, hubs, and outliers in large networks.  Edge Scores The [SCANStructuralSimilarityScore(G, triangles)](https://networkit.github.io/dev-docs/python_api/sparsification.html?highlight=scannetworkit.sparsification.SCANStructuralSimilarityScore) constructor expects as inputs a graph and previously calculated edge triangle counts of the graph.<jupyter_code># Initialize the algorithm
scan = nk.sparsification.SCANStructuralSimilarityScore(G, triangles)

# Run
scan.run()

# Get edge scores
scanScores = scan.scores()
for score in scanScores[:5]:
    print("{:.3f}".format(score))<jupyter_output><empty_output><jupyter_text>Sparsification<jupyter_code># Initialize
scanSparsifier = nk.sparsification.SCANSparsifier()

# Get sparsified graph
scanGraph = scanSparsifier.getSparsifiedGraphOfSize(G, targetRatio)
G.numberOfEdges(), scanGraph.numberOfEdges()<jupyter_output><empty_output><jupyter_text>Simmelian Overlap Score This is an implementation of the parametric variant of Simmelian Backbones. It calculates for each edge the minimum parameter value such that the edge is still contained in the sparsified graph.   Edge Scores The [SimmelianOverlapScore(G, triangles, maxRank)](https://networkit.github.io/dev-docs/python_api/sparsification.html?highlight=simmeliannetworkit.sparsification.SimmelianOverlapScore) constructor expects as inputs a graph, triangles and the maximum rank that is considered for overlap calculation.<jupyter_code># Initialize the algorithm
sos = nk.sparsification.SimmelianOverlapScore(G, triangles, 5)

# Run
sos.run()

# Get edge scores
sosScores = sos.scores()
for score in sosScores[:5]:
    print("{:.3f}".format(score))<jupyter_output><empty_output><jupyter_text>Sparsification<jupyter_code># Initialize the algorithm
simmelianSparsifier = nk.sparsification.SimmelianSparsifierNonParametric()

# Get sparsified graph
simmelieanGraph = simmelianSparsifier.getSparsifiedGraphOfSize(G, targetRatio)
G.numberOfEdges(), simmelieanGraph.numberOfEdges()<jupyter_output><empty_output>
{'fraction_non_alphanumeric': 0.08985041662483687, 'fraction_numerical': 0.0033129203895191244, 'mean_word_length': 7.595340811044004, 'pattern_counts': {'":': 0, '<': 69, '<?xml version=': 0, '>': 69, 'https://': 11, 'lorem ipsum': 0, 'www.': 0, 'xml': 0}, 'pii_count': 0, 'substrings_counts': 0, 'word_list_counts': {'cursed_substrings.json': 0, 'profanity_word_list.json': 0, 'sexual_word_list.json': 0, 'zh_pornsignals.json': 0}}
{'chain_length': '17', 'dir': 'jupyter-structured-clean-dedup', 'id': '506196', 'license': 'MIT', 'n_tokens_mistral': 3092, 'n_tokens_neox': 2957, 'n_words': 783, 'path': 'notebooks/Sparsification.ipynb', 'repo_name': 'danielw2904/networkit', 'size': '9961'}