Python NetworkX

  • http://networkx.lanl.gov
  • It is a Python language software package for the creation, manipulation, and study of the structure, dynamics, and functions of complex networks.

1) networkx 모듈 설치 및 테스트 코드

In [1]:
import networkx as nx
import matplotlib.pyplot as plt
%matplotlib inline

g = nx.Graph()
g.add_edge('a','b')
nx.draw(g, node_size=1000, with_labels=True, font_size=16)
plt.show()

2) Simple Graph Analysis

In [2]:
g = nx.Graph()
g.add_edge(1,2)
g.add_edge(1,3)
g.add_edge(1,4)
g.add_edge(2,3)
g.add_edge(3,4)
g.add_edge(4,5)
g.add_edge(4,6)
g.add_edge(5,6)
g.add_edge(5,7)
g.add_edge(5,8)
g.add_edge(6,7)
g.add_edge(6,8)
g.add_edge(7,8)
g.add_edge(7,9)
nx.draw(g, node_size=500, with_labels=True, font_size=16)
plt.show()
# plt.savefig("figure1.1.png")

- Graph Attributes

In [3]:
g.graph
Out[3]:
{}
In [4]:
g.graph['caption']='Figure 1. Simple Social Graph' 
g.graph['number of nodes']=9
In [5]:
g.graph
Out[5]:
{'caption': 'Figure 1. Simple Social Graph', 'number of nodes': 9}

- Getting Basic Information of Graph

  • multigraph
    • a graph permitted to have multiple edges that have the same end nodes, thus two vertices may be connected by more than one edge.
In [6]:
print "g.number_of_edges():", g.number_of_edges() 
print "g.size():", g.size()
print "g.number_of_nodes():", g.number_of_nodes()
print "len(g):", len(g)
print "g.is_directed():", g.is_directed()
print "g.is_multigraph():", g.is_multigraph()
print "g.has_node(1):", g.has_node(1)
print "g.has_node(10):", g.has_node(10)
print "g.has_edge(4,5):", g.has_edge(4,5)
print "g.has_edge(4,8):", g.has_edge(4,8)
print "g.nodes():", g.nodes()
print "g.edges():", g.edges()
g.number_of_edges(): 14
g.size(): 14
g.number_of_nodes(): 9
len(g): 9
g.is_directed(): False
g.is_multigraph(): False
g.has_node(1): True
g.has_node(10): False
g.has_edge(4,5): True
g.has_edge(4,8): False
g.nodes(): [1, 2, 3, 4, 5, 6, 7, 8, 9]
g.edges(): [(1, 2), (1, 3), (1, 4), (2, 3), (3, 4), (4, 5), (4, 6), (5, 8), (5, 6), (5, 7), (6, 8), (6, 7), (7, 8), (7, 9)]
In [7]:
g.adjacency_list()
Out[7]:
[[2, 3, 4],
 [1, 3],
 [1, 2, 4],
 [1, 3, 5, 6],
 [8, 4, 6, 7],
 [8, 4, 5, 7],
 [8, 9, 5, 6],
 [5, 6, 7],
 [7]]
In [8]:
g.neighbors(1)
Out[8]:
[2, 3, 4]
In [9]:
dict((x, g.neighbors(x)) for x in g.nodes())
Out[9]:
{1: [2, 3, 4],
 2: [1, 3],
 3: [1, 2, 4],
 4: [1, 3, 5, 6],
 5: [8, 4, 6, 7],
 6: [8, 4, 5, 7],
 7: [8, 9, 5, 6],
 8: [5, 6, 7],
 9: [7]}

- Graph Anlysis

- Graph generators and graph operations

  • Using a call to one of the classic small graphs
In [10]:
petersen=nx.petersen_graph()
nx.draw(petersen, node_size=500, with_labels=True, font_size=16)
In [11]:
tutte=nx.tutte_graph() 
nx.draw(tutte, node_size=300, with_labels=True, font_size=13)
In [12]:
maze=nx.sedgewick_maze_graph() 
nx.draw(maze, node_size=500, with_labels=True, font_size=16)
In [13]:
tet=nx.tetrahedral_graph()
nx.draw(tet, node_size=500, with_labels=True, font_size=16)
  • Using a (constructive) generator for a classic graph
In [14]:
k_5=nx.complete_graph(5)
nx.draw(k_5, node_size=500, with_labels=True, font_size=16)
In [15]:
k_3_5=nx.complete_bipartite_graph(3,5) 
nx.draw(k_3_5, node_size=500, with_labels=True, font_size=16)
In [16]:
barbell=nx.barbell_graph(10,10) 
nx.draw(barbell, node_size=200, with_labels=True, font_size=10)
In [17]:
lollipop=nx.lollipop_graph(10,20)
nx.draw(lollipop, node_size=300, with_labels=True, font_size=12)
  • Using a stochastic graph generator
In [18]:
er=nx.erdos_renyi_graph(100,0.15)
nx.draw(er, node_size=200, with_labels=True, font_size=10)
In [19]:
ws=nx.watts_strogatz_graph(30,3,0.1)
nx.draw(ws, node_size=200, with_labels=True, font_size=10)
In [20]:
ba=nx.barabasi_albert_graph(100,5)
nx.draw(ba, node_size=200, with_labels=True, font_size=10)
In [21]:
red=nx.random_lobster(100,0.9,0.9)
nx.draw(red, node_size=200, with_labels=True, font_size=7)

- Directed Graphs

  • “DiGraph” class provides additional methods specific to directed edges
In [22]:
dg=nx.DiGraph()
dg.add_weighted_edges_from([(1,2,0.5), (3,1,0.75), (3,2,0.1)])
nx.draw(dg, node_size=200, with_labels=True, font_size=10)
In [23]:
print dg.in_degree(2)
print dg.out_degree(3)
print dg.out_degree(1, weight='weight')
print dg.degree(1, weight='weight')
print 
print dg.predecessors(2)
print dg.predecessors(3)
print dg.successors(1)
print dg.neighbors(1) #(equivalent to dg.successors())
2
2
0.5
1.25

[1, 3]
[]
[2]
[2]

- Multigraphs

  • “MultiGraph” and “MultiDiGraph” classes allow you to add the same edge twice between any pair of nodes, possibly with different edge data.

  • These can be powerful for some applications, but many algorithms (e.g., shortest path) are not well defined on such graphs.

In [24]:
mg=nx.MultiGraph()
mg.add_weighted_edges_from([(1,2,.5), (1,2,.75), (2,3,.5), (3,1,0.1)])
print mg.degree(weight='weight')
nx.draw(mg, node_size=200, with_labels=True, font_size=10)
{1: 1.35, 2: 1.75, 3: 0.6}

- Graph Features

- Graph generators and graph operations

  • Using a call to one of the classic small graphs
In [25]:
import networkx.algorithms as algo
nx.draw(g, node_size=500, with_labels=True, font_size=16)
plt.show()

print "eccentricity(g, 5):", algo.eccentricity(g, 5)
print "radius(g):", algo.radius(g)
print "diameter(g):", algo.diameter(g)
print "center(g):", algo.center(g)
print "periphery(g):", algo.periphery(g)
eccentricity(g, 5): 3
radius(g): 3
diameter(g): 5
center(g): [4, 5, 6]
periphery(g): [2, 9]

- Node Attributes

In [26]:
g.add_node(10, time='5pm')
g.nodes()
Out[26]:
[1, 2, 3, 4, 5, 6, 7, 8, 9, 10]
In [27]:
print g.node[2]
print g.node[10]
{}
{'time': '5pm'}
In [28]:
g.add_nodes_from([11, 12, 13], time='2pm')
g.nodes()
Out[28]:
[1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13]
In [29]:
g.nodes(data=True)
Out[29]:
[(1, {}),
 (2, {}),
 (3, {}),
 (4, {}),
 (5, {}),
 (6, {}),
 (7, {}),
 (8, {}),
 (9, {}),
 (10, {'time': '5pm'}),
 (11, {'time': '2pm'}),
 (12, {'time': '2pm'}),
 (13, {'time': '2pm'})]

- Edge Attributes

In [30]:
g.add_edge(2, 9, weight=4.7)
g.add_edge(20, 21, weight=10.0)
g.add_edges_from([(3, 4),(4, 5)], color='red')
g.add_edges_from([(30, 31, {'color':'blue'}), (40, 41, {'weight':8})]) 

g.edges()
Out[30]:
[(1, 2),
 (1, 3),
 (1, 4),
 (2, 3),
 (2, 9),
 (3, 4),
 (4, 5),
 (4, 6),
 (5, 8),
 (5, 6),
 (5, 7),
 (6, 8),
 (6, 7),
 (7, 8),
 (7, 9),
 (40, 41),
 (20, 21),
 (30, 31)]
In [31]:
g.edges(data=True)
Out[31]:
[(1, 2, {}),
 (1, 3, {}),
 (1, 4, {}),
 (2, 3, {}),
 (2, 9, {'weight': 4.7}),
 (3, 4, {'color': 'red'}),
 (4, 5, {'color': 'red'}),
 (4, 6, {}),
 (5, 8, {}),
 (5, 6, {}),
 (5, 7, {}),
 (6, 8, {}),
 (6, 7, {}),
 (7, 8, {}),
 (7, 9, {}),
 (40, 41, {'weight': 8}),
 (20, 21, {'weight': 10.0}),
 (30, 31, {'color': 'blue'})]
In [32]:
g.edge[2][9]
Out[32]:
{'weight': 4.7}
In [33]:
g.edge[2][9]['weight']
Out[33]:
4.7

- Getting Degree Information

In [34]:
g = nx.Graph()
g.add_edges_from([(1,2), (1,3), (1,4), (2,3), (3,4), (4,5), (4,6), (5,6), (5,7), (5,8), (6,7), (6,8), (7,8), (7,9)])
nx.draw(g, node_size=500, with_labels=True, font_size=16)
plt.show()
In [35]:
print g.degree()
print sorted(g.degree().values())
{1: 3, 2: 2, 3: 3, 4: 4, 5: 4, 6: 4, 7: 4, 8: 3, 9: 1}
[1, 2, 3, 3, 3, 4, 4, 4, 4]
In [36]:
g.degree(1)
Out[36]:
3
In [37]:
g.degree([1, 2, 3])
Out[37]:
{1: 3, 2: 2, 3: 3}

- Connected Components

In [38]:
g.add_node(100)
for components in nx.connected_components(g):
    print components
[1, 2, 3, 4, 5, 6, 7, 8, 9]
[100]
In [39]:
g.remove_node(100)

- Clustering Coefficients

In [40]:
nx.clustering(g)
Out[40]:
{1: 0.6666666666666666,
 2: 1.0,
 3: 0.6666666666666666,
 4: 0.3333333333333333,
 5: 0.6666666666666666,
 6: 0.6666666666666666,
 7: 0.5,
 8: 1.0,
 9: 0.0}

- Shortest Path vs. Dijkstra Path

  • The shortest path between two nodes
In [41]:
nx.draw(g, node_size=500, with_labels=True, font_size=16)
In [42]:
import networkx.algorithms as algo
algo.shortest_path(g,1,9)
Out[42]:
[1, 4, 5, 7, 9]
In [43]:
print ([p for p in algo.all_shortest_paths(g,1,9)])
[[1, 4, 5, 7, 9], [1, 4, 6, 7, 9]]
In [44]:
algo.average_shortest_path_length(g)
Out[44]:
2.111111111111111
In [45]:
algo.all_pairs_shortest_path(g)
algo.all_pairs_shortest_path_length(g)
algo.all_pairs_shortest_path_length(g)[2]
Out[45]:
{1: 1, 2: 0, 3: 1, 4: 2, 5: 3, 6: 3, 7: 4, 8: 4, 9: 5}
  • Get node pairs
In [46]:
import itertools
list(itertools.combinations(g.nodes(), 2))
Out[46]:
[(1, 2),
 (1, 3),
 (1, 4),
 (1, 5),
 (1, 6),
 (1, 7),
 (1, 8),
 (1, 9),
 (2, 3),
 (2, 4),
 (2, 5),
 (2, 6),
 (2, 7),
 (2, 8),
 (2, 9),
 (3, 4),
 (3, 5),
 (3, 6),
 (3, 7),
 (3, 8),
 (3, 9),
 (4, 5),
 (4, 6),
 (4, 7),
 (4, 8),
 (4, 9),
 (5, 6),
 (5, 7),
 (5, 8),
 (5, 9),
 (6, 7),
 (6, 8),
 (6, 9),
 (7, 8),
 (7, 9),
 (8, 9)]
In [47]:
nn = g.nodes()
nn[:5]
Out[47]:
[1, 2, 3, 4, 5]
  • Compare the two paths
In [48]:
for pair in itertools.combinations(nn[:6], 2):
    print algo.shortest_path(g, *pair), algo.dijkstra_path(g, *pair)
[1, 2] [1, 2]
[1, 3] [1, 3]
[1, 4] [1, 4]
[1, 4, 5] [1, 4, 5]
[1, 4, 6] [1, 4, 6]
[2, 3] [2, 3]
[2, 1, 4] [2, 1, 4]
[2, 1, 4, 5] [2, 1, 4, 5]
[2, 1, 4, 6] [2, 1, 4, 6]
[3, 4] [3, 4]
[3, 4, 5] [3, 4, 5]
[3, 4, 6] [3, 4, 6]
[4, 5] [4, 5]
[4, 6] [4, 6]
[5, 6] [5, 6]
  • Get weighted graph
In [49]:
from random import choice
ee = g.edges()
new_edges = [x + (choice(range(100)),) for x in ee]
new_edges
Out[49]:
[(1, 2, 64),
 (1, 3, 56),
 (1, 4, 64),
 (2, 3, 4),
 (3, 4, 41),
 (4, 5, 17),
 (4, 6, 88),
 (5, 8, 40),
 (5, 6, 77),
 (5, 7, 72),
 (6, 8, 47),
 (6, 7, 28),
 (7, 8, 5),
 (7, 9, 8)]
In [50]:
g.clear()
g.add_weighted_edges_from(new_edges)
  • Compare the two paths
In [51]:
for pair in itertools.combinations(nn[:6], 2):
    print algo.shortest_path(g, *pair), algo.dijkstra_path(g, *pair)
[1, 2] [1, 3, 2]
[1, 3] [1, 3]
[1, 4] [1, 4]
[1, 4, 5] [1, 4, 5]
[1, 4, 6] [1, 4, 6]
[2, 3] [2, 3]
[2, 1, 4] [2, 3, 4]
[2, 1, 4, 5] [2, 3, 4, 5]
[2, 1, 4, 6] [2, 3, 4, 6]
[3, 4] [3, 4]
[3, 4, 5] [3, 4, 5]
[3, 4, 6] [3, 4, 6]
[4, 5] [4, 5]
[4, 6] [4, 6]
[5, 6] [5, 8, 7, 6]