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 모듈 설치 및 테스트 코드

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

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

g.graph

{}

g.graph['caption']='Figure 1. Simple Social Graph' 
g.graph['number of nodes']=9

g.graph

{'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.

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)]

g.adjacency_list()

[[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]]

g.neighbors(1)

[2, 3, 4]

dict((x, g.neighbors(x)) for x in g.nodes())

{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

petersen=nx.petersen_graph()
nx.draw(petersen, node_size=500, with_labels=True, font_size=16)

tutte=nx.tutte_graph() 
nx.draw(tutte, node_size=300, with_labels=True, font_size=13)

maze=nx.sedgewick_maze_graph() 
nx.draw(maze, node_size=500, with_labels=True, font_size=16)

tet=nx.tetrahedral_graph()
nx.draw(tet, node_size=500, with_labels=True, font_size=16)

• Using a (constructive) generator for a classic graph

k_5=nx.complete_graph(5)
nx.draw(k_5, node_size=500, with_labels=True, font_size=16)

k_3_5=nx.complete_bipartite_graph(3,5) 
nx.draw(k_3_5, node_size=500, with_labels=True, font_size=16)

barbell=nx.barbell_graph(10,10) 
nx.draw(barbell, node_size=200, with_labels=True, font_size=10)

lollipop=nx.lollipop_graph(10,20)
nx.draw(lollipop, node_size=300, with_labels=True, font_size=12)

• Using a stochastic graph generator

er=nx.erdos_renyi_graph(100,0.15)
nx.draw(er, node_size=200, with_labels=True, font_size=10)

ws=nx.watts_strogatz_graph(30,3,0.1)
nx.draw(ws, node_size=200, with_labels=True, font_size=10)

ba=nx.barabasi_albert_graph(100,5)
nx.draw(ba, node_size=200, with_labels=True, font_size=10)

red=nx.random_lobster(100,0.9,0.9)
nx.draw(red, node_size=200, with_labels=True, font_size=7)

See also http://networkx.lanl.gov/reference/generators.html

- Directed Graphs

• “DiGraph” class provides additional methods specific to directed edges

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)

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.

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

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

g.add_node(10, time='5pm')
g.nodes()

[1, 2, 3, 4, 5, 6, 7, 8, 9, 10]

print g.node[2]
print g.node[10]

{}
{'time': '5pm'}

g.add_nodes_from([11, 12, 13], time='2pm')
g.nodes()

[1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13]

g.nodes(data=True)

[(1, {}),
 (2, {}),
 (3, {}),
 (4, {}),
 (5, {}),
 (6, {}),
 (7, {}),
 (8, {}),
 (9, {}),
 (10, {'time': '5pm'}),
 (11, {'time': '2pm'}),
 (12, {'time': '2pm'}),
 (13, {'time': '2pm'})]

- Edge Attributes

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()

[(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)]

g.edges(data=True)

[(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'})]

g.edge[2][9]

{'weight': 4.7}

g.edge[2][9]['weight']

4.7

- Getting Degree Information

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()

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]

g.degree(1)

3

g.degree([1, 2, 3])

{1: 3, 2: 2, 3: 3}

- Connected Components

g.add_node(100)
for components in nx.connected_components(g):
    print components

[1, 2, 3, 4, 5, 6, 7, 8, 9]
[100]

g.remove_node(100)

- Clustering Coefficients

nx.clustering(g)

{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

nx.draw(g, node_size=500, with_labels=True, font_size=16)

import networkx.algorithms as algo
algo.shortest_path(g,1,9)

[1, 4, 5, 7, 9]

print ([p for p in algo.all_shortest_paths(g,1,9)])

[[1, 4, 5, 7, 9], [1, 4, 6, 7, 9]]

algo.average_shortest_path_length(g)

2.111111111111111

algo.all_pairs_shortest_path(g)
algo.all_pairs_shortest_path_length(g)
algo.all_pairs_shortest_path_length(g)[2]

{1: 1, 2: 0, 3: 1, 4: 2, 5: 3, 6: 3, 7: 4, 8: 4, 9: 5}

• Get node pairs

import itertools
list(itertools.combinations(g.nodes(), 2))

[(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)]

nn = g.nodes()
nn[:5]

[1, 2, 3, 4, 5]

• Compare the two paths

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

from random import choice
ee = g.edges()
new_edges = [x + (choice(range(100)),) for x in ee]
new_edges

[(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)]

g.clear()
g.add_weighted_edges_from(new_edges)

• Compare the two paths

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]