pythonnetworkit

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


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.


Solution

  • 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