<jupyter_start><jupyter_text>All considered sparsification algorithm implementations rely on edge scores, so do not forget to call indexEdges() on the graph you want to work on.<jupyter_code>G = readGraph("../../input/jazz.graph", Format.METIS)
G.indexEdges()
G.size()<jupyter_output><empty_output><jupyter_text>Sparsification algorithms that leave the set of nodes intact can be split up into edge score calculation and a global filtering step. All backbone algorithm implementations in the backbones-module are based on that insight. The module provides both low-level scores and filters and high-level convenience classes which can be identified by the suffix 'Backbone'.  Example 1: Simple calculation of a sparsified graph<jupyter_code>sparsificationAlgorithm = sparsification.LocalDegreeSparsifier()<jupyter_output><empty_output><jupyter_text>In the following code piece, we need to specify a parameter value, which indirectly influences the size of the resulting graph.<jupyter_code>S = sparsificationAlgorithm.getSparsifiedGraph(G, 0.5)
S.size()<jupyter_output><empty_output><jupyter_text>In order to obtain a reduced graph of a specific size, we can use the following convenience function which applies an appropriate parameterization algorithm to obtain a parameter value first:<jupyter_code>S = sparsificationAlgorithm.getSparsifiedGraphOfSize(G, 0.5)
S.size()<jupyter_output><empty_output><jupyter_text>Note that pre-calculated edge scores can be passed to these functions as well in order to avoid unnecessary recalculations.  Example 2: Exporting a sparsification score to Gephi In order to filter edges within Gephi, we need to calculate the edge score:<jupyter_code>sparsificationAlgorithm = sparsification.LocalDegreeSparsifier()
edgeScores = sparsificationAlgorithm.scores(G)<jupyter_output><empty_output><jupyter_text>We can now export it to Gephi (start the Gephi Streaming Master server first):<jupyter_code>gephiClient = gephi.streaming.GephiStreamingClient()
gephiClient.exportGraph(G)
gephiClient.exportEdgeValues(G, edgeScores, 'myAttribute')<jupyter_output><empty_output><jupyter_text>Example 3: Listing of all implemented sparsification definitions<jupyter_code>sAlgorithms = [
    (sparsification.ForestFireSparsifier(0.15, 5), 'Forest Fire'),
    (sparsification.LocalDegreeSparsifier(), 'Local Degree'),
    (sparsification.LocalSimilaritySparsifier(), 'Local Similarity'),
    (sparsification.MultiscaleSparsifier(), 'Multiscale'),
    (sparsification.RandomEdgeSparsifier(), 'RandomEdge'),
    (sparsification.RandomNodeEdgeSparsifier(), 'RandomNodeEdge'),
    (sparsification.SimmelianSparsifierNonParametric(), 'Simmelian NonParametric'),
    (sparsification.SimmelianSparsifierParametric(10), 'Simmelian Parametric'),
    (sparsification.QuadrilateralSimmelianSparsifier(), 'Simmelian Quadrangle'),
    (sparsification.SCANSparsifier(), 'SCAN'),
]<jupyter_output><empty_output><jupyter_text>Let's calculate an edge score for each of these definitions and export them all to Gephi:<jupyter_code>gephiClient = gephi.streaming.GephiStreamingClient()
gephiClient.clearGraph()
gephiClient.exportGraph(G)
for (algorithm, name) in sAlgorithms:
    edgeScores = algorithm.scores(G)
    linearEdgeScores = sparsification.getRankAttribute(edgeScores)
    gephiClient.exportEdgeValues(G, linearEdgeScores, name)<jupyter_output><empty_output><jupyter_text>For visualization purposes, let's also calculate and export the community structure:<jupyter_code>c = community.detectCommunities(G, community.PLM(G, refine=False, par='none'))
gephiClient.exportNodeValues(G, c, 'community')<jupyter_output>PLM(none,pc) detected communities in 0.021265268325805664 [s]
solution properties:
-------------------  --------
# communities         4
min community size   21
max community size   60
avg. community size  49.5
modularity            0.44308
-------------------  --------<jupyter_text>Example 4: Using scores, filters, and parameterization In the following example, we illustrate possible usage of a sparsification score, a filter and a parameterization algorithm. Note that any of these might be exchanged.<jupyter_code>#Score calculation
sparsificationAlgorithm = sparsification.LocalDegreeSparsifier()
edgeScores = sparsificationAlgorithm.scores(G)

#Parameterization using binary search with up to 20 steps. The parameter value is in [0,1] and the size of the graph increases with increasing parameter value.
parameterization = sparsification.BinarySearchParameterization(True, 0.0, 1.0, 20)
parameter = parameterization.parameterize(sparsificationAlgorithm, G, edgeScores, 0.3) # We'd like to keep ~30% of edges

#Global filtering
globalFilter = sparsification.GlobalThresholdFilter(G, edgeScores, parameter, False) #Keep all edges with an edge attribute value below the given parameter
B = globalFilter.calculate()
B.size()<jupyter_output><empty_output><jupyter_text>Example 5: Using linearized scores with Gephi An example where it might be desireable to work with 'linear' edge score is Filtering in Gephi. By 'linear' we mean that a value close to the mean value should yield a graph with about 50% of edges. The sparsification module offers a convenience function that offers this functionality and that can be applied to both node and edge scores.<jupyter_code>sparsificationAlgorithm = sparsification.LocalSimilaritySparsifier()
edgeScores = sparsificationAlgorithm.scores(G)
linearScores = sparsification.getRankAttribute(edgeScores)
gephiClient.exportEdgeValues(G, edgeScores, 'rank')<jupyter_output><empty_output>
{'fraction_non_alphanumeric': 0.0869094843130184, 'fraction_numerical': 0.01153984853948792, 'mean_word_length': 6.588235294117647, 'pattern_counts': {'":': 0, '<': 44, '<?xml version=': 0, '>': 44, 'https://': 0, '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': '11', 'dir': 'jupyter-structured-clean-dedup', 'id': '569968', 'license': 'MIT', 'n_tokens_mistral': 1646, 'n_tokens_neox': 1535, 'n_words': 488, 'path': 'Doc/Notebooks/Sparsification.ipynb', 'repo_name': 'maxvogel/NetworKit-mirror2', 'size': '5546'}