CODEWITHSUNDEEP
python-2.7graphnetworkx
sato
sato

Reputation: 862

Counting multiple edges in graph (python)

I am generating a network of size N with a power-law degree distribution using the so-called configuration_model algorithm. The resulting graph allows multiple edges, I have to count them but I cannot figure out how. Here is a possible solution:

import networkx as nx
import numpy as np
from networkx.utils import (powerlaw_sequence, create_degree_sequence)

deg_sequence = create_degree_sequence(num, powerlaw_sequence, exponent=2.2)
graph=nx.configuration_model(deg_sequence)

num_par = sum(len(graph[node][neigh]) for node in graph for neigh in graph.neighbors_iter(node)) // 2
print ('Graph has %d multi-links' %num_par)

self_loops=len(graph.selfloop_edges())
print ('Graph has %d self-loops' %self_loops)

edges=len(graph.edges())
print edges

I borrowed the sixth line of code somewhere on the internet but frankly I can't quite understand how it works. In particular I can't understand what is (graph[node][neigh]) of which it calculates the length. To me, it does not seem like a list either, but I am sure it's me not getting the idea here. Btw as a result of this code I get a very high percentage of multiple edges, more than 98% of the total number of links, and it does not seem very good to me. Is this way of calculating parallel edges correct? If so, would you explain me how it works? Do you know any other way of doing it?

Upvotes: 3

Views: 2015

Answers (1)

Paul Brodersen
Paul Brodersen

Reputation: 13031

If you write out line 6 in for-loops instead of list expressions, you arrive at the following: 

num_par = 0
for node in graph:
    for neigh in graph.neighbors(node):
        num_par += len(graph[node][neigh]) / 2.

I am not sure what that line is counting; I am sure that it is not calculating the number of multi-edges correctly.

If you just plot the graph as an array (num = 100), you can immediately see that there are very few multi-edges:

arr = nx.to_numpy_matrix(graph)
plt.imshow(arr, interpolation='nearest', cmap='gray'); plt.show()

enter image description here

The number of multi-edges is easily calculated with

num_multiedges = np.sum(arr>=2) / 2 # divide by two as graph is undirected

Upvotes: 3

Related Questions