How to pick out the largest networked nodes and edges

[Atayal]

Hi,

Assume I constructed a graph with edges and nodes, and if they're not
all connected, how do I pick out the "cluster" with the most nodes?

Timothy

[Andrew Conway]

This functionality is built in

http://networkx.lanl.gov/reference/generated/networkx.connected_component_subgraphs.html#networkx.connected_component_subgraphs

___________________________________

Drew Conway

Ph.D. Candidate

Department of Politics, New York University

agc...@nyu.edu

http://homepages.nyu.edu/~agc282

[Atayal]

Thanks for your tip.

Timothy

On Dec 26, 12:41 pm, Andrew Conway <agc...@nyu.edu> wrote:
> This functionality is built in
>

> http://networkx.lanl.gov/reference/generated/networkx.connected_compo...

[Mauro Cavalcanti]

Dear ALL,

Greetings! NetworkX interfaces nicely to the Matplotlib Python
library, which includes a superb module for displaying geographic maps
in many different projections. Is there any way to display a NX graph
over a MPL/Basemap plot? The problem seems to be that of providing the
graph nodes with its geographic coordinates, but is it possible to do
this in NetworkX?

Thanks in advance for any assistance you can provide.

With best regards,

--
Dr. Mauro J. Cavalcanti
Ecoinformatics Studio
P.O. Box 46521, CEP 20551-970
Rio de Janeiro, RJ, BRASIL
E-mail: maur...@gmail.com
Web: http://studio.infobio.net
Linux Registered User #473524 * Ubuntu User #22717
"Life is complex. It consists of real and imaginary parts."

[Aric Hagberg]

On Fri, Dec 26, 2008 at 08:00:40AM -0200, Mauro Cavalcanti wrote:
>
> Dear ALL,
>
> Greetings! NetworkX interfaces nicely to the Matplotlib Python
> library, which includes a superb module for displaying geographic maps
> in many different projections. Is there any way to display a NX graph
> over a MPL/Basemap plot? The problem seems to be that of providing the
> graph nodes with its geographic coordinates, but is it possible to do
> this in NetworkX?
>

Sure - here is a hack of the Knuth "miles" example in NetworkX that
uses the Matplotlib Basemap package. The basic idea is to
set node positions in map projection coordinates. This example
is more complicated than needed to show the basic functionality but
I hope you can see how it works.

You'll also need the knuth_miles.txt.gz file from
http://networkx.lanl.gov/svn/networkx/trunk/examples/drawing/knuth_miles.txt.gz

Aric

#!/usr/bin/env python
"""
An example using networkx.Graph().

miles_graph() returns an undirected graph over the 128 US cities from
the datafile miles_dat.txt. The cities each have location and population
data. The edges are labeled with the distance betwen the two cities.

This example is described in Section 1.1 in Knuth's book [1,2].

References.
-----------

[1] Donald E. Knuth,
"The Stanford GraphBase: A Platform for Combinatorial Computing",
ACM Press, New York, 1993.
[2] http://www-cs-faculty.stanford.edu/~knuth/sgb.html

"""
__author__ = """Aric Hagberg (hag...@lanl.gov)"""
# Copyright (C) 2004-2006 by
# Aric Hagberg <hag...@lanl.gov>
# Dan Schult <dsc...@colgate.edu>
# Pieter Swart <sw...@lanl.gov>
# Distributed under the terms of the GNU Lesser General Public License
# http://www.gnu.org/copyleft/lesser.html

import networkx as nx

def miles_graph():
""" Return the cites example graph in miles_dat.txt
from the Stanford GraphBase.
"""
# open file miles_dat.txt.gz (or miles_dat.txt)
try:
try:
import gzip
fh = gzip.open('knuth_miles.txt.gz','r')
except:
fh=open("knuth_miles.txt","r")
except IOError:
raise "File knuth_miles.txt not found."

G=nx.Graph()
G.position={}
G.population={}

cities=[]
for line in fh.readlines():
if line.startswith("*"): # skip comments
continue

numfind=re.compile("^\d+")

if numfind.match(line): # this line is distances
dist=line.split()
for d in dist:
G.add_edge(city,cities[i],int(d))
i=i+1
else: # this line is a city, position, population
i=1
(city,coordpop)=line.split("[")
cities.insert(0,city)
(coord,pop)=coordpop.split("]")
(y,x)=coord.split(",")

G.add_node(city)
# assign position in decimal lon,lat
G.position[city]=(-float(x)/100.0,float(y)/100.0)
G.population[city]=float(pop)/1000.0
return G

if __name__ == '__main__':
import networkx as nx
import re
import sys

G=miles_graph()

print "Loaded miles_dat.txt containing 128 cities."
print "digraph has %d nodes with %d edges"\
%(nx.number_of_nodes(G),nx.number_of_edges(G))

# make new graph of cites, edge if less then 300 miles between them
H=nx.Graph()
for v in G:
H.add_node(v)
for (u,v,d) in G.edges(data=True):
if d < 300:
H.add_edge(u,v)

# draw with matplotlib/pylab and basemap

from matplotlib.mlab import prctile_rank
import matplotlib.pyplot as plt
from mpl_toolkits.basemap import Basemap as Basemap
m = Basemap(llcrnrlon=-125.5,llcrnrlat=20.,
urcrnrlon=-50.566,urcrnrlat=40.0,
resolution='l',area_thresh=1000.,projection='lcc',
lat_1=50.,lon_0=-107.)

cities=G.position.keys()
lons=[x for x,y in G.position.values()]
lats=[y for x,y in G.position.values()]
# convert lat and lon to map projection
mx,my=m(lons,lats)
# put map projection coordinates back in G.position dictionary
pos=zip(mx,my)
G.position.update(zip(cities,pos))
# nodes colored by degree, sized by population
nx.draw(H,G.position,
node_size=[G.population[v] for v in H],
node_color=[float(H.degree(v)) for v in H],
with_labels=False)

m.drawcoastlines()
m.drawcountries()
m.drawstates()
#m.scatter(x,y,25,colors,marker='o',edgecolors='none',zorder=10)
plt.title('City Locations colored by Population Rank')
plt.savefig("knuth_miles_basemap.png")
plt.show()

[Mauro Cavalcanti]

Dear Aric,

Thank you *very much* for the example! I am reasonable well-acquainted
with MPL/Basemap, so had not much difficulty in follow your exemple,
but will have to study and play with it in order to adapt it to my
needs.

With warmest regards,

2008/12/26 Aric Hagberg <hag...@lanl.gov>: