

In [1]:

    
from networkit import *

All considered sparsification algorithm implementations rely on edge scores, so do not forget to call indexEdges() on the graph you want to work on.



In [4]:

    
G = readGraph("../../input/jazz.graph", Format.METIS)
G.indexEdges()
G.size()









    Out[4]:





(198, 2742)

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



In [5]:

    
sparsificationAlgorithm = sparsification.LocalDegreeSparsifier()

In the following code piece, we need to specify a parameter value, which indirectly influences the size of the resulting graph.



In [6]:

    
S = sparsificationAlgorithm.getSparsifiedGraph(G, 0.5)
S.size()









    Out[6]:





(198, 850)

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:



In [7]:

    
S = sparsificationAlgorithm.getSparsifiedGraphOfSize(G, 0.5)
S.size()









    Out[7]:





(198, 1372)

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:



In [8]:

    
sparsificationAlgorithm = sparsification.LocalDegreeSparsifier()
edgeScores = sparsificationAlgorithm.scores(G)

We can now export it to Gephi (start the Gephi Streaming Master server first):



In [9]:

    
gephiClient = gephi.streaming.GephiStreamingClient()
gephiClient.exportGraph(G)
gephiClient.exportEdgeValues(G, edgeScores, 'myAttribute')

Example 3: Listing of all implemented sparsification definitions



In [10]:

    
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'),
]

Let's calculate an edge score for each of these definitions and export them all to Gephi:



In [11]:

    
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)

For visualization purposes, let's also calculate and export the community structure:



In [12]:

    
c = community.detectCommunities(G, community.PLM(G, refine=False, par='none'))
gephiClient.exportNodeValues(G, c, 'community')









    



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

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.



In [13]:

    
#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()









    Out[13]:





(198, 1911)

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.



In [14]:

    
sparsificationAlgorithm = sparsification.LocalSimilaritySparsifier()
edgeScores = sparsificationAlgorithm.scores(G)
linearScores = sparsification.getRankAttribute(edgeScores)
gephiClient.exportEdgeValues(G, edgeScores, 'rank')