CODEWITHSUNDEEP
pythonpython-3.xnumpynetworkxgraph-theory
sjhaque14
sjhaque14

Reputation: 113

Calculate the Laplacian matrix of a graph object in NetworkX

I am writing my own function that calculates the Laplacian matrix for any directed graph, and am struggling with filling the diagonal entries of the resulting matrix. The following equation is what I use to calculate entries of the Laplacian matrix, where e_ij represents an edge from node i to node j.

Laplacian eqn

I am creating graph objects with NetworkX (https://networkx.org/). I know NetworkX has its own Laplacian function for directed graphs, but I want to be 100% sure I am using a function that carries out the correct computation for my purposes. The code I have developed thus far is shown below, for the following example graph:

3 state graph

# Create a simple example of a directed weighted graph

G = nx.DiGraph()
G.add_nodes_from([1, 2, 3])
G.add_weighted_edges_from([(1, 2, 1), (1, 3, 1), (2, 1, 1), (2, 3, 1), (3, 1, 1), (3, 2, 1)])

# Put node, edge, and weight information into Python lists

node_list = []

for item in G.nodes():
    node_list.append(item)

edge_list = []
weight_list = []

for item in G.edges():
    weight_list.append(G.get_edge_data(item[0],item[1])['weight'])
    item = (item[0]-1,item[1]-1)
    edge_list.append(item)

print(edge_list)
> [(0, 1), (0, 2), (1, 0), (1, 2), (2, 0), (2, 1)]

# Fill in the non-diagonal entries of the Laplacian

num_nodes = len(node_list)
num_edges = len(edge_list)

J = np.zeros(shape = (num_nodes,num_nodes))

for x in range(num_edges):
    i = edge_list[x][0]
    j = edge_list[x][1]
    
    J[i,j] = weight_list[x]

I am struggling to figure out how to fill in the diagonal entries. edge_list is a list of tuples. To perform the computation in the above equation for L(G), I need to loop through the second entries of each tuple, store the first entry into a temporary list, sum over all the elements of that temporary list, and finally store the negative of the sum in the correct diagonal entry of L(G).

Any suggestions would be greatly appreciated, especially if there are steps above that can be done more efficiently or elegantly.

Upvotes: 1

Views: 4345

Answers (3)

Lith
Lith

Reputation: 803

I will deviate a little from your method, since I prefer to work with Numpy if possible :P.

In the following snippet, I generate test data for a network of n=10 nodes; that is, I generate an array of tuples V to populate with random nodes, and also a (n,n) array A with the values of the edges between nodes. Hopefully the code is somewhat self-explanatory and is correct (let me know otherwise):

from random import sample
import numpy as np

# Number and list of nodes
n = 10
nodes = list(np.arange(n))      # random.sample needs list

# Test array of linked nodes
# V[i] is a tuple with all nodes the i-node connects to.
V = np.zeros(n, dtype = tuple)
for i in range(n):
    nv = np.random.randint(5)  # Random number of edges from node i
    # To avoid self-loops (do not know if it is your case - comment out if necessary)
    itself = True
    while itself:    
        cnodes = sample(nodes, nv)  # samples nv elements from the nodes list w/o repetition
        itself = i in cnodes
    V[i] = cnodes

# Test matrix of weighted edges (from i-node to j-node)
A = np.zeros((n,n))
for i in range(n):
    for j in range(n):
        if j in V[i]:
            A[i,j] = np.random.random()*5             
        
# Laplacian of network
J = np.copy(A)      # This already sets the non-diagonal elements
for i in range(n):
    J[i,i] = - np.sum(A[:,i]) - A[i,i]

Upvotes: 1

sjhaque14
sjhaque14

Reputation: 113

Thank you all for your suggestions! I agree that numpy is the way to go. As a rudimentary solution that I will optimize later, this is what I came up with:

def Laplacian_all(edge_list,weight_list,num_nodes,num_edges):
    
    J = np.zeros(shape = (num_nodes,num_nodes))
    
    for x in range(num_edges):
        i = edge_list[x][0]
        j = edge_list[x][1]

        J[i,j] = weight_list[x]
    
    for i in range(num_nodes):
        temp = []
        for x in range(num_edges):
            if i == edge_list[x][1]:
                temp.append(weight_list[x])
        temp_sum = -1*sum(temp)
        J[i,i] = temp_sum
    
    return J

I have yet to test this on different graphs, but this was what I was hoping to figure out for my immediate purposes.

Upvotes: 0

Sparky05
Sparky05

Reputation: 4892

I adjusted networkx.laplacian_matrix function for undirected graphs a little bit

import networkx as nx
import scipy.sparse

G = nx.DiGraph()
G.add_nodes_from([1, 2, 3])
G.add_weighted_edges_from([(1, 2, 1), (1, 3, 1), (2, 1, 1), (2, 3, 1), (3, 1, 1), (3, 2, 1)])

nodelist = list(G)
A = nx.to_scipy_sparse_matrix(G, nodelist=nodelist, weight="weight", format="csr")
n, m = A.shape
diags = A.sum(axis=0)  # 1 = outdegree, 0 = indegree
D = scipy.sparse.spdiags(diags.flatten(), [0], m, n, format="csr")

print((A - D).todense())
# [[-2  1  1]
#  [ 1 -2  1]
#  [ 1  1 -2]]

Upvotes: 1

Related Questions