CODEWITHSUNDEEP
pythongraphnetworkx
Paul
Paul

Reputation: 1149

Networkx creating a graph with node attributes to determine which edges are connected

I am trying to create a connected graph where each node has some attributes that determine what other nodes it is connected to. The network is a circular space to make it easy to establish links (there are a 1000 nodes).

The way this network works is that a node has both neighbors (the ones to its immediate left/right - i.e. node 3 has neighbors 1 and 2) and also k long distance links. The way a node picks long distance links is that it just randomly picks nodes from the clockwise direction (i.e. node 25 might have 200 as its long distance link instead of 15).

Here is a sample image of what it might looks like: https://i.sstatic.net/dr7C7.png Given is a symphony network but my implementation is a simplification of that.

I partially implemented this in java(via a linked list holding an arraylist) but am lost on how to do this in NetworkX. I am especially confused on how to add these specific node attributes that say that a node will find k long links but after k will not accept any more links. Is there a specific built in graph in networkx that is suited towards this model or is any graph acceptable as long as I have the correct node attributes?

It's a simplification of a more complicated network where no node leaves and no edge dissapears.

Any help or a link to an example would be appreciated on this.

Upvotes: 1

Views: 2938

Answers (2)

daedalus
daedalus

Reputation: 10923

This approximates to your need:

import networkx as nx
import matplotlib.pyplot as plt
import random

N = 20 # number of nodes
K = 3 # number of "long" edges

G = nx.cycle_graph(N)

for node in G.nodes():
    while len(G.neighbors(node)) < K+2:
        # Add K neighbors to each node
        # (each node already has two neighbors from the cycle)
        valid_target_found = False
        while not valid_target_found:
            # CAUTION
            # This loop will not terminate
            # if K is too high relative to N
            target = random.randint(0,N-1)
            # pick a random node
            if (not target in G.neighbors(node)
                and len(G.neighbors(target)) < K+2):
                # Accept the target if (a) it is not already
                # connected to source and (b) target itself
                # has less than K long edges
                valid_target_found = True
        G.add_edge(node, target)

nx.draw_circular(G)
plt.show()

It creates the graph below. There are improvements to be made, for example, a more efficient selection of the target nodes for the long edges, but this gets you started, I hope.

Cycle graph with "long" edges

Upvotes: 1

AsTeR
AsTeR

Reputation: 7541

In NetworkX, if there's any logic about connecting your node everything should be left to you.

Nevertheless, if you want to iterate on nodes in Python (not tested):

for (nodeId, data) in yourGraph.nodes(data=True):
    // some logic here over data

    // to connect your node
    yourGraph.add_edge(nodeId, otherNodeId)

Side note: if you want to stay in Java you can also consider using Jung and Gephi.

Upvotes: 0

Related Questions