Sorting a list of nodes based on their degree

[Francesc Segura]

Hello,

This is my first time working with Python and Networkx, and I'm having
problems with sorting nodes.
First of all I have an edge list based on the air traffic routes
around the world, I can read it and obtain the degree distribution,
but now i want to obtain the 25 nodes with highest degree. I use
"print GN.degree()" and obtain a large list of nodes and degrees, but
it's quite dirty doing it this way and I've thought to sort the nodes
in order of their degree and after that printing the first 25 on the
screen but I cannot do it. Anyone can give me a suggestion? I copy
here the code that I already have:

import networkx as nx

print 'llegim les dades de la xarxa global d aeroports '
print


GN=nx.read_edgelist("global-net.txt")

print 'calculem algunes propietats generals'
print
print nx.info(GN)
print
print 'distribucio de grauss: '
print nx.degree_histogram(GN)
print
print 'grau maxim: '
print len(nx.degree_histogram(GN))-1
print
print 'grau mig calculat programant-ho'

degs=nx.degree(GN).values()

avgdegGN=0
for i in range(0,GN.order()):
avgdegGN = avgdegGN+degs[i]


print
print 'el grau mig calculat es:'
print (avgdegGN*1.0)/GN.order()
print
print '(compareu amb abans - aqui hi ha mes decimals - ) '

print
print 'El clustering coeficient promig esta implementat '
print 'pero tambe el podem calcular com es veu aqui'


###################################################################################################
# CLUSTERING COEFFICIENT

ClustC=nx.clustering(GN).values()

sumClust=0
maxCC=0
minCC=9

for i in range(1,GN.order()):
sumClust = sumClust + ClustC[i]
if ClustC[i]>maxCC:
maxCC= ClustC[i]
if ClustC[i]<minCC:
minCC=ClustC[i]

print
print 'Avg Clust Coeff. NetworkX = %-6.4f ' %
(nx.average_clustering(GN))
print
print 'Avg Clust Coeff. Calculat = %-6.4f ' % (sumClust/GN.order())
print
print '(minClust, maxClust) = (%-6.4f' % minCC,'- %-6.6f'% maxCC,')'
print


################################################################################
# FIND NODES WITH HIGHER DEGREE
print
'************************************************************************'
print
#print GN.degree()
sorted(GN.degree().values())
##print("Grau dels 25 mes grans")
##b = nx.degree(GN).values
##for v in range (0,24):
## print("%0.2d5.3f"%(v,b[v]))


Thank you all.

[Aric Hagberg]

On Wed, May 4, 2011 at 4:43 AM, Francesc Segura <frse...@gmail.com> wrote:
> Hello,
>
> This is my first time working with Python and Networkx, and I'm having
> problems with sorting nodes.
> First of all I have an edge list based on the air traffic routes
> around the world, I can read it and obtain the degree distribution,
> but now i want to obtain the 25 nodes with highest degree.  I use
> "print GN.degree()" and obtain a large list of nodes and degrees, but
> it's quite dirty doing it this way and I've thought to sort the nodes
> in order of their degree and after that printing the first 25 on the
> screen but I cannot do it.  Anyone can give me a suggestion?  I copy
> here the code that I already have:

You can use G.degree_iter() to give (node,degree) tuples and sort
those by degree using itemgetter to specify the sort key as the second
item:

In [1]: import networkx as nx

In [2]: G=nx.gnp_random_graph(10,0.3)

In [3]: from operator import itemgetter

In [4]: sorted(G.degree_iter(),key=itemgetter(1),reverse=True)
Out[4]:
[(7, 4),
(8, 4),
(5, 3),
(1, 2),
(2, 2),
(4, 2),
(9, 2),
(0, 1),
(3, 1),
(6, 1)]

Aric

[Francesc Segura]

Thanks a lot, it worket but it supposed so much calculation and
printing time, anyhow to only show the 25 high-grade nodes?


On 4 mayo, 15:12, Aric Hagberg <ahagb...@gmail.com> wrote:

[Aric Hagberg]

On Thu, May 5, 2011 at 5:16 AM, Francesc Segura <frse...@gmail.com> wrote:
> Thanks a lot, it worket but it supposed so much calculation and
> printing time, anyhow to only show the 25 high-grade nodes?

It should be very fast. e.g. for a 100000 node graph getting the nodes
with the largest 25 degrees takes about 150ms on my machine:

In [1]: import networkx as nx

In [2]: from operator import itemgetter

In [3]: G=nx.fast_gnp_random_graph(100000,0.0001)

In [4]: %timeit nd=sorted(G.degree_iter(),key=itemgetter(1),reverse=True)[0:25]
10 loops, best of 3: 156 ms per loop

Aric