In this notebook we present some of the dynamic algorithms in NetworKit to analyze various properties of a (dynamic) graph. See the networkit.dynamics module for a more detailed description of the algorithms used here. Dynamic algorithms can compute the result for a modified 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. Instead, update methods are provided by the DynAlgorithm base class.
[1]:
# As usual, the first step is to import NetworKit.
import networkit as nk
Note: In order to maintain consistent results, 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(...).
The 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
graphEventEdgeAdd = nk.dynamics.GraphEvent(
nk.dynamics.GraphEventType.EDGE_ADDITION, 2, 4, 2.0
)
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(graphEventEdgeAdd)
print("path lengths from source node 0 after edge addition: ", dynDijk.getDistances())
G.removeEdge(2, 4)
dynDijk.update(graphEventEdgeAdd)
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]
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]]
When multiple changes were made to the graph, the updateBatch function can be used to update the dynamic algorithm in one step. Depending on the algorithm, this batch update may be more efficient than calling update multiple times in sequence.
[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]]
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 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]
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]
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]]
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