Dynamics¶

In this notebook we present some of NetworKit dynamic algorithms to analyze properties of a (dynamic) graph. See the networkit.dynamics module for a more detailed description. Dynamic algorithms can compute the result for the adapted graph directly from the previous result, without the need to re-run the entire algorithm.

Note: The run() method does not need to be called in order to adapt the result.

[1]:

# As usual, the first step is to import NetworKit.
import networkit as nk

The Graph and Graph Events¶

Note: In order to maintain consistent result, both the Graph and the Dynamic Algorithm need to be adjusted.
- The graph needs to be changed by using the graph manipulation function equivalent to the desired result - like G.addEdge(...) or G.removeEdge(...).
- Dynamic Algorithm needs to be changed, using graph events and calling the functions update(...) or updateBatch(...).

[2]:

# Initialize graph
def initializeGraph():
    G = nk.Graph(5, True)
    G.addEdge(0,1, 0.5)
    G.addEdge(1,2, 1.5)
    return G

# Initialize graph events
graph_event_edge_add = nk.dynamics.GraphEvent(nk.dynamics.GraphEventType.EDGE_ADDITION, 2,4, 2.0)

DynDijkstra¶

The Dynamic Dijkstra algorithm computes the shortest paths to all nodes from a given source node, just like Dikstra’s Algorithm. The dynamic version is able to handle adding and removing edges in the graph (note that both graph and the dynamic algorithm needs to be updated).

[3]:

# Run Dijsktra algorithm on the initial graph
G = initializeGraph()
sourceNode = 0
dynDijk = nk.distance.DynDijkstra(G, sourceNode)
dynDijk.run()
print("path lengths from source node 0 for initial graph: ", dynDijk.getDistances())

path lengths from source node 0 for initial graph:  [0.0, 0.5, 2.0, 1.7976931348623157e+308, 1.7976931348623157e+308]

[4]:

# Update the result of the dynamic algorithm
G.addEdge(2,4, 2.0)
dynDijk.update(nk.dynamics.GraphEvent(nk.dynamics.GraphEventType.EDGE_ADDITION, 2,4, 2.0))
print("path lengths from source node 0 after edge addition: ", dynDijk.getDistances())

G.removeEdge(2,4)
dynDijk.update(nk.dynamics.GraphEvent(nk.dynamics.GraphEventType.EDGE_REMOVAL, 2,4, 2.0))
print("path lengths from source node 0 after edge removal: ", dynDijk.getDistances())

path lengths from source node 0 after edge addition:  [0.0, 0.5, 2.0, 1.7976931348623157e+308, 4.0]
path lengths from source node 0 after edge removal:  [0.0, 0.5, 2.0, 1.7976931348623157e+308, 1.7976931348623157e+308]

DynAPSP¶

Similar to the Dynamic Dijkstra algorithm, there exists a variant of Dynamic All Pairs Shortest Path, which computes the shortest path for each node to all other nodes. It can handle graph events of the types EDGE_ADDITION and EDGE_WEIGHT_INCREMENT with a negative value.

[5]:

# Run APSP algorithm on the initial graph
G = initializeGraph()
dynAPSP = nk.distance.DynAPSP(G)
dynAPSP.run()
print("path lengths from all nodes for initial graph: ", dynAPSP.getDistances())

path lengths from all nodes for initial graph:  [[0.0, 0.5, 2.0, 1.7976931348623157e+308, 1.7976931348623157e+308], [0.5, 0.0, 1.5, 1.7976931348623157e+308, 1.7976931348623157e+308], [2.0, 1.5, 0.0, 1.7976931348623157e+308, 1.7976931348623157e+308], [1.7976931348623157e+308, 1.7976931348623157e+308, 1.7976931348623157e+308, 0.0, 1.7976931348623157e+308], [1.7976931348623157e+308, 1.7976931348623157e+308, 1.7976931348623157e+308, 1.7976931348623157e+308, 0.0]]

[6]:

# Batchwise update the result of the dynamic algorithm
G.addEdge(1,3, 1.5)
G.addEdge(2,4, 2.0)
G.addEdge(0,4, 1.5)
batch = [nk.dynamics.GraphEvent(nk.dynamics.GraphEventType.EDGE_ADDITION, 1,3, 1.5),
        nk.dynamics.GraphEvent(nk.dynamics.GraphEventType.EDGE_ADDITION, 2,4, 2.0),
        nk.dynamics.GraphEvent(nk.dynamics.GraphEventType.EDGE_ADDITION, 0,4, 1.5)]
dynAPSP.updateBatch(batch)
print("path lengths from all nodes after batch of edge additions: ", dynAPSP.getDistances())

# Decreasing edge weights
G.increaseWeight(1,2, -0.5) # Weight decrementation is implemented as negative weight increment
dynAPSP.update(nk.dynamics.GraphEvent(nk.dynamics.GraphEventType.EDGE_WEIGHT_INCREMENT, 1,2, -0.5))
print("path lengths from all nodes after edge weight decrement: ", dynAPSP.getDistances())

path lengths from all nodes after batch of edge additions:  [[0.0, 0.5, 2.0, 2.0, 1.5], [0.5, 0.0, 1.5, 1.5, 2.0], [2.0, 1.5, 0.0, 3.0, 2.0], [2.0, 1.5, 3.0, 0.0, 3.5], [1.5, 2.0, 2.0, 3.5, 0.0]]
path lengths from all nodes after edge weight decrement:  [[0.0, 0.5, 1.5, 2.0, 1.5], [0.5, 0.0, 1.0, 1.5, 2.0], [1.5, 1.0, 0.0, 2.5, 2.0], [2.0, 1.5, 2.5, 0.0, 3.5], [1.5, 2.0, 2.0, 3.5, 0.0]]

DynBetweenness¶

The Dynamic Betweenness algorithm computes the betweenness centrality of a graph. It can handle graph events of the types EDGE_ADDITION and EDGE_WEIGHT_INCREMENT with a negative value and adjusts the result without re-running the entire algorithm over again.

[7]:

# Run Betweenness algorithm on the initial graph
G = initializeGraph()
dynBet = nk.centrality.DynBetweenness(G)
dynBet.run()
print("betweenness scores of initial graph: ",dynBet.scores())

betweenness scores of initial graph:  [0.0, 2.0, 0.0, 0.0, 0.0]

[8]:

# Updating the graph and dynamic algorithm
G.increaseWeight(2,4, -1.0) # Weight decrementation is implemented as negative weight increment
dynBet.update(nk.dynamics.GraphEvent(nk.dynamics.GraphEventType.EDGE_WEIGHT_INCREMENT, 2,4, -1.0))
print("betweenness scores of updated graph: ",dynBet.scores())

betweenness scores of updated graph:  [0.0, 2.0, 2.0, 0.0, 0.0]

DynTopHarmonicCloseness¶

The Dynamic Top Harmonic Closeness algorithm returns the Harmonic Closeness score for the k nodes with highest value.

[9]:

# Run Betweenness algorithm on the initial graph
G = initializeGraph()
dynHC = nk.centrality.DynTopHarmonicCloseness(G, 3)
dynHC.run()
print("betweenness scores of initial graph: ",dynHC.topkScoresList())

betweenness scores of initial graph:  [2.0, 1.5, 1.5]

[10]:

# Updating the graph and dynamic algorithm
G.addEdge(2,4) # Weight decrementation is implemented as negative weight increment
dynHC.update(nk.dynamics.GraphEvent(nk.dynamics.GraphEventType.EDGE_ADDITION, 2,4, 1.0))
print("betweenness scores of updated graph: ",dynHC.topkScoresList())

betweenness scores of updated graph:  [2.5, 2.5, 1.8333333333333333]

DynConnectedComponents¶

The Dynamic Connected Component algorithm returns the Connected Components of an undirected graph.

[11]:

# Run Connected Components algorithm on the initial graph
G = initializeGraph()
dynCC = nk.components.DynConnectedComponents(G)
dynCC.run()
print("connected components of initial graph: ",dynCC.getComponents())

connected components of initial graph:  [[0, 1, 2], [3], [4]]

[12]:

# Updating the graph and dynamic algorithm
G.addEdge(1,3)
dynCC.update(nk.dynamics.GraphEvent(nk.dynamics.GraphEventType.EDGE_ADDITION, 1,3, 1.0))
print("connected components of updated graph: ",dynCC.getComponents())

connected components of updated graph:  [[0, 1, 2, 3], [4]]

Other Dynamic Algorithms and Data Structures¶

NetworKit does also include different types of dynamic algorithms and data structures that do not inherit from DynAlgorithm which means that they have a different usage: - DynamicMatrix - DynamicGenerators - DynamicNMIDistance