How do you specify nodes that have no edges in an edgelist for NetworKit?

Question

An edgelist can be read by networkit.graphio.EdgeListReader into a weighted, directed graph.

For example,

0 1 10
1 0 2
3 2 3
5 0 1

where each row is the origin vertex ID, the destination vertex ID, and the edge weight.

How do we represent in the edgelist a vertex which has no edges? Including it would be important for measures like algebraic connectivity.

Answer 1

One possibility is to exploit the default behavior of the NetworKit EdgeListReader [1]. The reader creates a graph with n+1 nodes where n is the highest node id in your edge list. Thus, you can introduce an isolated node x (i.e., a node with no incident edges) by creating an edge list with n nodes (n > x) and no edges incident to x.

For example, the following edge list represents a graph with 4 nodes where node 2 is isolated:

0 1 1
1 3 1

g = nk.graphio.EdgeListReader(' ', 0).read("edge_list.txt")

for u in g.iterNodes():
    print(f"Node {u} has degree {g.degree(u)}.")

# Node 0 has degree 1.
# Node 1 has degree 2.
# Node 2 has degree 0. <- Node 2 is isolated
# Node 3 has degree 1.

[1] https://networkit.github.io/dev-docs/python_api/graphio.html?highlight=edgelistreader#networkit.graphio.EdgeListReader

Edit: After reading your graph, you can insert further isolated nodes with the addNodes() function [2]:

# Let g be your graph with n nodes
g.addNodes(10)
# Now g has n+10 nodes, all nodes with id from n to n+9 are isolated.

[2] https://networkit.github.io/dev-docs/python_api/networkit.html?highlight=addnodes#networkit.Graph.addNodes