Handling Graphs with NetworkX¶

Python offers the library NetworkX for manipulating graphs. You can learn more here:

https://networkx.github.io/

https://networkx.github.io/documentation/stable/tutorial.html

In [168]:
import networkx as nx
import matplotlib.pyplot as plt

%matplotlib inline

Creating a graph¶

In [77]:
G = nx.Graph()

Add nodes to the graph

In [169]:
G.add_node(1)
G.add_nodes_from([2,3])
G.add_node('Alice')
G.add_node('Bob')
print(G.nodes())
[1, 2, 3, 'Alice', 'Bob', 'Charlie']

Draw the graph

In [170]:
nx.draw_networkx(G)

Add edges to the graph

In [171]:
G.add_edge(1,2)
G.add_edges_from([(1,3),('Alice','Bob')])
e = (1,'Alice')
G.add_edge(*e)
In [172]:
nx.draw_networkx(G)

Adding an edge with a new node will create the node Charlie in the graph

In [173]:
G.add_edge('Alice','Charlie')
print(G.edges())
print(G.nodes())
nx.draw_networkx(G)
[(1, 2), (1, 3), (1, 'Alice'), ('Alice', 'Bob'), ('Alice', 'Charlie')]
[1, 2, 3, 'Alice', 'Bob', 'Charlie']

Creating a graph from edges

This is the most common way to create a graph

In [174]:
G2 = nx.Graph()
G2.add_edges_from([(1,2),(1,3),('Alice','Bob'),(1,'Alice')])
print(G2.nodes())
print(G2.edges())
nx.draw_networkx(G2)
[1, 2, 3, 'Alice', 'Bob']
[(1, 2), (1, 3), (1, 'Alice'), ('Alice', 'Bob')]

Reading a graph from a file with list of edges

https://networkx.org/documentation/stable/reference/readwrite/index.html

In [175]:
#Read a graph from a list of edges
G3 = nx.read_edgelist('graph_edges.txt')
print(G3.nodes())
print(G3.edges())
nx.draw_networkx(G3)
['1', '2', '3', 'Alice', 'Bob', 'Charlie']
[('1', '2'), ('1', '3'), ('1', 'Alice'), ('2', '3'), ('Alice', 'Bob'), ('Bob', 'Charlie')]

Removing edges and nodes

In [176]:
G2.remove_edge(1,3)
G2.remove_node(3)
G2.remove_node(1)
print(G2.nodes())
print(G2.edges())
nx.draw_networkx(G2)
[2, 'Alice', 'Bob']
[('Alice', 'Bob')]

The graph object, nodes and edges¶

A graph can be thought of as a dictionary with nodes as the keys

Each node is a dictionary with the neighbors as the keys, and the edge properties as values

In [177]:
type(G)
Out[177]:
networkx.classes.graph.Graph
In [178]:
for n in G: print(n,':',G[n])
1 : {2: {}, 3: {}, 'Alice': {}}
2 : {1: {}}
3 : {1: {}}
Alice : {'Bob': {}, 1: {}, 'Charlie': {}}
Bob : {'Alice': {}}
Charlie : {'Alice': {}}
In [179]:
G[1]
Out[179]:
AtlasView({2: {}, 3: {}, 'Alice': {}})
In [180]:
print(G.nodes)
print(G.edges)
[1, 2, 3, 'Alice', 'Bob', 'Charlie']
[(1, 2), (1, 3), (1, 'Alice'), ('Alice', 'Bob'), ('Alice', 'Charlie')]
In [181]:
#For every node we can obtain the properties of the node (in this example this is empty)
print(G.nodes['Alice'])
#For every edge we can obtain the properties of the edge (in this example this is empty)
print(G.edges[(1,2)])
{}
{}

Graph attributes¶

You can assign attributes and values to the nodes of the graph

In [182]:
G3.nodes['Alice']['gender'] = 'female'
G3.nodes['Bob']['gender'] = 'male'
G3.nodes['Charlie']['gender'] = 'male'
G3.nodes['1']['value'] = 1
G3.nodes['2']['value'] = -1
G3.nodes['3']['value'] = 0
for n in G3.nodes():
    print(n,':',G3.nodes[n]) 
1 : {'value': 1}
2 : {'value': -1}
3 : {'value': 0}
Alice : {'gender': 'female'}
Bob : {'gender': 'male'}
Charlie : {'gender': 'male'}
In [183]:
for n in G3.nodes():
    print(n,':',G3[n])
1 : {'2': {}, '3': {}, 'Alice': {}}
2 : {'1': {}, '3': {}}
3 : {'1': {}, '2': {}}
Alice : {'Bob': {}, '1': {}}
Bob : {'Alice': {}, 'Charlie': {}}
Charlie : {'Bob': {}}
In [184]:
G3.nodes['Alice']['value'] = 1
G3.nodes['Bob']['value'] = -1
G3.nodes['Charlie']['value'] = 1
for n in G3.nodes():
    print(n+ ":" + str(G3.nodes[n]['value']))

for n in G3.nodes():
    print(n,':',G3.nodes[n])
1:1
2:-1
3:0
Alice:1
Bob:-1
Charlie:1
1 : {'value': 1}
2 : {'value': -1}
3 : {'value': 0}
Alice : {'gender': 'female', 'value': 1}
Bob : {'gender': 'male', 'value': -1}
Charlie : {'gender': 'male', 'value': 1}

You can also add attributes and values to the edges in the graph

In [185]:
G3['Alice']['Bob']['label'] = 'strong'
print(G3['Bob']['Alice'])
print(G3['Alice'])
print(G3['Bob'])
{'label': 'strong'}
{'Bob': {'label': 'strong'}, '1': {}}
{'Alice': {'label': 'strong'}, 'Charlie': {}}
In [186]:
for e in G3.edges:
    print(e,':',G3.edges[e])
('1', '2') : {}
('1', '3') : {}
('1', 'Alice') : {}
('2', '3') : {}
('Alice', 'Bob') : {'label': 'strong'}
('Bob', 'Charlie') : {}
In [187]:
print(G3.edges[('Alice','Bob')])
print(G3.edges[('Alice','Bob')]['label'])
{'label': 'strong'}
strong
In [188]:
# The method get_edge_attributes returns a dictionary with keys the edges 
#and values the values of the attribute we requested (for the edges that have it)
nx.get_edge_attributes(G3,'label')
Out[188]:
{('Alice', 'Bob'): 'strong'}
In [189]:
pos=nx.spring_layout(G3)
nx.draw_networkx(G3, pos)
my_labels = nx.get_edge_attributes(G3,'label')
print(my_labels)
nx.draw_networkx_edge_labels(G3, pos, edge_labels=my_labels)
#plt.show()
{('Alice', 'Bob'): 'strong'}
Out[189]:
{('Alice', 'Bob'): Text(-0.14520541461629888, 0.3747206779133405, 'strong')}

Weighted graphs¶

A special attribute of a an edge is the "weight". When adding weighted edges, you enter triples consisting of the two edge endpoints and the weight of the edge. This weight is stored in an attribute "weight" by default.

In [190]:
G4 = nx.Graph()
G4.add_weighted_edges_from([(1,2,0.5),(2,3,0.1),(3,4,0.7)])
for (a,b) in G4.edges():
    print (a,b,':',G4[a][b])
for (a,b,w) in G4.edges(data =True): #data=True returns weight as well
    print (str(a)+" "+ str(b) + " " + str(w['weight']))
for n in G4:
    print(n,':',G4[n])
for e in G4.edges:
    print(e,':',G4.edges[e])
1 2 : {'weight': 0.5}
2 3 : {'weight': 0.1}
3 4 : {'weight': 0.7}
1 2 0.5
2 3 0.1
3 4 0.7
1 : {2: {'weight': 0.5}}
2 : {1: {'weight': 0.5}, 3: {'weight': 0.1}}
3 : {2: {'weight': 0.1}, 4: {'weight': 0.7}}
4 : {3: {'weight': 0.7}}
(1, 2) : {'weight': 0.5}
(2, 3) : {'weight': 0.1}
(3, 4) : {'weight': 0.7}
In [191]:
weights = nx.get_edge_attributes(G4,'weight')
print(weights)
{(1, 2): 0.5, (2, 3): 0.1, (3, 4): 0.7}
In [192]:
pos=nx.spring_layout(G4)
nx.draw_networkx(G4, pos)
nx.draw_networkx_edge_labels(G4, pos, edge_labels=weights)
Out[192]:
{(1, 2): Text(-0.1568874759358344, -0.7526589763309715, '0.5'),
 (2, 3): Text(0.0028747654380344365, 0.013983266304825603, '0.1'),
 (3, 4): Text(0.1568874759358344, 0.7526589763309715, '0.7')}
In [193]:
print(weights)
{(1, 2): 0.5, (2, 3): 0.1, (3, 4): 0.7}

Directed Graphs¶

In [194]:
DG1=nx.DiGraph()
DG1.add_edges_from([(1,2), (2,1), (3,1), (1,4), (2,4), (4,3)])
pos=nx.spring_layout(DG1)
nx.draw_networkx(DG1,pos)
In [195]:
DG2=nx.DiGraph()
DG2.add_weighted_edges_from([(1,2,0.5), (3,1,0.75), (1,4,0.1)])
print(DG2.edges())
for n in DG2:
    print(n, DG2[n])

pos=nx.spring_layout(DG2)
nx.draw_networkx(DG2,pos)
weights = nx.get_edge_attributes(DG2,'weight')
nx.draw_networkx_edge_labels(DG2, pos, edge_labels=weights)
[(1, 2), (1, 4), (3, 1)]
1 {2: {'weight': 0.5}, 4: {'weight': 0.1}}
2 {}
3 {1: {'weight': 0.75}}
4 {}
Out[195]:
{(1, 2): Text(-0.41071094043126943, -0.03983116068898572, '0.5'),
 (1, 4): Text(0.2914365096122925, 0.435178557883492, '0.1'),
 (3, 1): Text(0.2596752269996655, -0.5249902814275222, '0.75')}

You can transform a directed graph into an undirected on using to_undirected()

In [196]:
UG1 = DG1.to_undirected()
print(UG1.edges())
for n in UG1:
    print(n, UG1[n])
nx.draw_networkx(UG1)
[(1, 2), (1, 4), (1, 3), (2, 4), (3, 4)]
1 {2: {}, 4: {}, 3: {}}
2 {1: {}, 4: {}}
3 {1: {}, 4: {}}
4 {1: {}, 2: {}, 3: {}}
In [197]:
UG2 = DG2.to_undirected()
print(UG2.edges())
for n in UG2:
    print(n, UG2[n])
nx.draw_networkx(UG2)
[(1, 2), (1, 4), (1, 3)]
1 {2: {'weight': 0.5}, 4: {'weight': 0.1}, 3: {'weight': 0.75}}
2 {1: {'weight': 0.5}}
3 {1: {'weight': 0.75}}
4 {1: {'weight': 0.1}}

Graph Operations¶

Some common graph functions and algorithms are already implemented in networkx library.

Neighbors, degrees and adjancency matrix

In [198]:
nx.draw_networkx(G)
In [199]:
A = nx.adjacency_matrix(G)
print(A) 
#the adjacency matrix is stored as a sparse matrix
print(type(A))
  (0, 1)	1
  (0, 2)	1
  (0, 3)	1
  (1, 0)	1
  (2, 0)	1
  (3, 0)	1
  (3, 4)	1
  (3, 5)	1
  (4, 3)	1
  (5, 3)	1
<class 'scipy.sparse._csr.csr_matrix'>
In [200]:
print(G.neighbors(1)) # returns the neighbors of a node
print(list(G.neighbors(1)))
for x in G.neighbors(1):
    print(x)
print('degree of 1:',G.degree(1)) # returns the degree of a node
<dict_keyiterator object at 0x000002035D61B950>
[2, 3, 'Alice']
2
3
Alice
degree of 1: 3
In [201]:
print(G4[3])
print(G4.degree(3, weight='weight'))
print(G4.degree(3))
{2: {'weight': 0.1}, 4: {'weight': 0.7}}
0.7999999999999999
2

Neighbors and degrees for directed or weighted graphs

In [202]:
pos=nx.spring_layout(DG2)
nx.draw_networkx(DG2,pos)
weights = nx.get_edge_attributes(DG2,'weight')
nx.draw_networkx_edge_labels(DG2, pos, edge_labels=weights)
Out[202]:
{(1, 2): Text(-0.5049838391744116, 0.07440616425642085, '0.5'),
 (1, 4): Text(0.4089437064379942, -0.226453271208447, '0.1'),
 (3, 1): Text(-0.08607245438759417, 0.17343192430832471, '0.75')}
In [203]:
print(list(DG2.successors(1)))
print(list(DG2.neighbors(1)))
print(list(DG2.predecessors(1)))
print(DG2.out_degree(1))
print(DG2.in_degree(1))
print(DG2.out_degree(1,weight='weight'))
[2, 4]
[2, 4]
[3]
2
1
0.6

Connected components¶

In [204]:
G5 = nx.Graph()
G5.add_edges_from([(1,2),(1,3),(1,4),(2,3),('Alice','Bob'),('Bob','Charlie'),('Alice','Charlie')])
nx.draw_networkx(G5)
In [205]:
C = nx.connected_components(G5)
print(type(C))
for c in C:
    print(c)
<class 'generator'>
{1, 2, 3, 4}
{'Charlie', 'Bob', 'Alice'}

Get the connected component subgraphs

In [206]:
connected_subgraphs = [nx.subgraph(G5,c) for c in nx.connected_components(G5)]
for GC in connected_subgraphs:
    print('Connected Component')
    print(GC.nodes())
    print(GC.edges())
    print(len(GC))
Connected Component
[1, 2, 3, 4]
[(1, 2), (1, 3), (1, 4), (2, 3)]
4
Connected Component
['Charlie', 'Bob', 'Alice']
[('Charlie', 'Bob'), ('Charlie', 'Alice'), ('Bob', 'Alice')]
3

Get the largest connected component

In [207]:
# Get the nodes

largest_cc = max(nx.connected_components(G5), key=len)
print(largest_cc)
{1, 2, 3, 4}
In [208]:
#Get the subgraph

largest_cc = max(nx.connected_components(G5), key=len)
print(largest_cc)
CC_max = nx.subgraph(G5,largest_cc)
nx.draw_networkx(CC_max)
{1, 2, 3, 4}

Strongly Connected Components¶

In [209]:
DG = nx.DiGraph()
DG.add_edges_from([(1,2),(2,3),(3,4),(4,2),(4,3),(4,5)])
nx.draw_networkx(DG)
In [210]:
largest_SCC = max(nx.strongly_connected_components(DG), key=len)
#print(largest_SCC)
SCC_max = nx.subgraph(DG,largest_SCC)
nx.draw_networkx(SCC_max)

Shortest paths¶

In [221]:
G6 = nx.Graph()
G6.add_edges_from([(1,2),(1,3),(1,4),(2,3),(1,'Alice'),('Alice','Bob'),('Alice','Charlie'),('Bob','Charlie')])
nx.draw_networkx(G6)
sp = nx.shortest_path(G6,3,'Bob')
print(sp)
print(len(sp)-1)
print(nx.shortest_path_length(G6,3,'Bob'))
[3, 1, 'Alice', 'Bob']
3
3
In [222]:
SP1 = nx.single_source_shortest_path(G6,1)
print(SP1)
#print(nx.single_source_shortest_path_length(G3,'1'))
{1: [1], 2: [1, 2], 3: [1, 3], 4: [1, 4], 'Alice': [1, 'Alice'], 'Bob': [1, 'Alice', 'Bob'], 'Charlie': [1, 'Alice', 'Charlie']}
In [223]:
SP = nx.all_pairs_shortest_path(G6)
print(type(SP))
SP = dict(SP)
print(dict(SP))
<class 'generator'>
{1: {1: [1], 2: [1, 2], 3: [1, 3], 4: [1, 4], 'Alice': [1, 'Alice'], 'Bob': [1, 'Alice', 'Bob'], 'Charlie': [1, 'Alice', 'Charlie']}, 2: {2: [2], 1: [2, 1], 3: [2, 3], 4: [2, 1, 4], 'Alice': [2, 1, 'Alice'], 'Bob': [2, 1, 'Alice', 'Bob'], 'Charlie': [2, 1, 'Alice', 'Charlie']}, 3: {3: [3], 1: [3, 1], 2: [3, 2], 4: [3, 1, 4], 'Alice': [3, 1, 'Alice'], 'Bob': [3, 1, 'Alice', 'Bob'], 'Charlie': [3, 1, 'Alice', 'Charlie']}, 4: {4: [4], 1: [4, 1], 2: [4, 1, 2], 3: [4, 1, 3], 'Alice': [4, 1, 'Alice'], 'Bob': [4, 1, 'Alice', 'Bob'], 'Charlie': [4, 1, 'Alice', 'Charlie']}, 'Alice': {'Alice': ['Alice'], 1: ['Alice', 1], 'Bob': ['Alice', 'Bob'], 'Charlie': ['Alice', 'Charlie'], 2: ['Alice', 1, 2], 3: ['Alice', 1, 3], 4: ['Alice', 1, 4]}, 'Bob': {'Bob': ['Bob'], 'Alice': ['Bob', 'Alice'], 'Charlie': ['Bob', 'Charlie'], 1: ['Bob', 'Alice', 1], 2: ['Bob', 'Alice', 1, 2], 3: ['Bob', 'Alice', 1, 3], 4: ['Bob', 'Alice', 1, 4]}, 'Charlie': {'Charlie': ['Charlie'], 'Alice': ['Charlie', 'Alice'], 'Bob': ['Charlie', 'Bob'], 1: ['Charlie', 'Alice', 1], 2: ['Charlie', 'Alice', 1, 2], 3: ['Charlie', 'Alice', 1, 3], 4: ['Charlie', 'Alice', 1, 4]}}
In [224]:
print(SP1['Bob'])
print(SP[1]['Bob'])
[1, 'Alice', 'Bob']
[1, 'Alice', 'Bob']

Link Analysis¶

https://networkx.github.io/documentation/stable/reference/algorithms/link_analysis.html

In [215]:
DG2 = nx.DiGraph()
DG2.add_edges_from([(1,2),(1,3),(3,2),(2,5),(4,1),(4,2),(4,3),(5,1),(5,4)])
nx.draw_networkx(DG2)

Pagerank¶

The result of the Pagerank algorithm is a dictionary with the node ids as keys, and the pagerank values as values.

In [225]:
pr = nx.pagerank(DG2)
print(pr)
print('\n')
pr = nx.pagerank(G6)
print(pr)
{1: 0.18064505060873784, 2: 0.27131643087724033, 3: 0.14665711544131713, 5: 0.26061906832422166, 4: 0.140762334748483}


{1: 0.2420308196543696, 2: 0.12671382905463274, 3: 0.12671382905463274, 4: 0.07286059991932929, 'Alice': 0.17987731223897474, 'Bob': 0.12590180503903042, 'Charlie': 0.12590180503903042}

HITS¶

In [217]:
[h,a] = nx.hits(DG2)
print(h)
print(a)
print(a[2])
{1: 0.3028419093958839, 2: -1.1622198651869745e-17, 3: 0.16745199268671332, 5: 0.12544122612673908, 4: 0.4042648717906636}
{1: 0.23681287910395024, 2: 0.39098432508292885, 3: 0.3161224561036187, 5: -2.7136717951052335e-17, 4: 0.056080339709502096}
0.39098432508292885

Pesronalized Pagerank¶

We will see the example we presented in class

In [218]:
G7 = nx.read_edgelist('graph-example.txt')
nx.draw_networkx(G7)

To define the personalized Pagerank, we will use the "personalization" parameter, were we define the jump vector as a dictionary, with node ids as the keys, and the jump probability to each node as the values

In [135]:
print(nx.pagerank(G7))
print(nx.pagerank(G7, personalization = {'1':1}))
print(nx.pagerank(G7, personalization = {'6':1}))
{'1': 0.12755099866537586, '2': 0.18232887836414127, '3': 0.2394858218322733, '4': 0.18433868256410274, '5': 0.1326787034099837, '6': 0.13361691516412283}
{'1': 0.2583391334031776, '2': 0.20094608623757965, '3': 0.24190126489812175, '4': 0.14028792201015408, '5': 0.0833530743914921, '6': 0.07517251905947459}
{'1': 0.07517273333798744, '2': 0.12532699696556127, '3': 0.1866533325726192, '4': 0.18958031704255388, '5': 0.15407113246217508, '6': 0.26919548761910295}

We will now change the jump probability. To change the jump probability we will set the parameter alpha.

Attention: The parameter alpha is not the jump probability as we have described in class, but the probability of following an out-link. The jump probability is 1-alpha.

In [136]:
print(nx.pagerank(G7, alpha = 0.5))
print(nx.pagerank(G7, alpha = 0.5, personalization = {'1':1}))
print(nx.pagerank(G7, alpha = 0.5, personalization = {'6':1}))
{'1': 0.1390335398088414, '2': 0.1741686298166486, '3': 0.2133752383994728, '4': 0.17643097727782997, '5': 0.14740281022602297, '6': 0.14958880447118414}
{'1': 0.5510064790190851, '2': 0.16964493982349704, '3': 0.18185949066208873, '4': 0.054964764048023335, '5': 0.026690643658381363, '6': 0.015833682788924434}
{'1': 0.015833407896886878, '2': 0.039357701756408944, '3': 0.07419162031220411, '4': 0.15675161523961573, '5': 0.150192049257395, '6': 0.5636736055374894}

Betweeness¶

In [137]:
BC = nx.edge_betweenness_centrality(G6)
print(BC)
{('1', '2'): 0.23809523809523808, ('1', '3'): 0.23809523809523808, ('1', '4'): 0.2857142857142857, ('1', 'Alice'): 0.5714285714285714, ('2', '3'): 0.047619047619047616, ('Alice', 'Bob'): 0.23809523809523808, ('Alice', 'Charlie'): 0.23809523809523808, ('Bob', 'Charlie'): 0.047619047619047616}

Drawing Graphs¶

https://networkx.org/documentation/stable/reference/drawing.html

In [138]:
nx.draw_networkx(G6)
In [139]:
nx.draw(G6, with_labels = True)
In [140]:
nx.draw_circular(G6)
In [226]:
nx.draw_spectral(G6, with_labels=True)
In [142]:
nx.draw_spring(G6)
In [143]:
nx.draw_spring(DG2)

An example¶

In [144]:
karate=nx.read_gml("karate.gml",label='id')
nx.draw_networkx(karate)
In [145]:
nx.draw_spring(karate,with_labels=True)

Change the size of the nodes depending on their pagerank value

In [146]:
pr = nx.pagerank(karate)
nx.draw_networkx(karate,node_size=[10000*pr[x] for x in pr])

A PageRank implementation¶

We will now do our own implementation of Pagerank. Pagerank values for node $i$ are computed by iterating the following formula:

$$p_i = 0.85\sum_{j\rightarrow i}\frac{p_j}{d_{out}(j)} +0.15\frac 1n$$

We will associate each node with two values: the old pagerank in the previous step and the new one that is currently computed. We initialize the old pagerank to $1/n$

In [147]:
for x in karate.nodes:
    karate.nodes[x]['old_pr'] = 1/len(karate.nodes)
    karate.nodes[x]['pr'] = 0

The algorithm goes over the edges in the graph, and for each edge (x,y) transfers a fraction of the Pagerank of x to y (and vice versa since the graph is undirected).

For convergece check we want the maximum difference between old and new Pagerank values to be less than eps.

In [148]:
eps = 0.0000001
while (True):
    for (x,y) in karate.edges:
        karate.nodes[y]['pr'] += karate.nodes[x]['old_pr']/karate.degree(x)
        karate.nodes[x]['pr'] += karate.nodes[y]['old_pr']/karate.degree(y)

    diff = 0
    for x in karate.nodes:
        karate.nodes[x]['pr'] = karate.nodes[x]['pr']*0.85 + 0.15/len(karate.nodes)
        diff = max(diff, abs(karate.nodes[x]['pr'] - karate.nodes[x]['old_pr']))
    if diff < eps: break
        
    for x in karate.nodes:
        karate.nodes[x]['old_pr'] = karate.nodes[x]['pr']
        karate.nodes[x]['pr'] = 0
        
print({x:karate.nodes[x]['pr'] for x in karate.nodes})
{1: 0.09699746639416912, 2: 0.05287697716512755, 3: 0.05707850530246944, 4: 0.03585989886187514, 5: 0.02197802085797975, 6: 0.02911125727906845, 7: 0.02911125727906845, 8: 0.024490521601363044, 9: 0.029766036239543145, 10: 0.014309384124315726, 11: 0.02197802085797975, 12: 0.009564757473502347, 13: 0.014644911694305714, 14: 0.029536468425771824, 15: 0.014535968166646367, 16: 0.014535968166646367, 17: 0.016784065326985863, 18: 0.014558694786535084, 19: 0.014535968166646367, 20: 0.019604641610943857, 21: 0.014535968166646367, 22: 0.014558694786535084, 23: 0.014535968166646367, 24: 0.03152244833588808, 25: 0.021075999887935973, 26: 0.02100616170212189, 27: 0.01504401086799329, 28: 0.0256397267700412, 29: 0.019573438474829792, 30: 0.02628848291686834, 31: 0.024590131585182876, 32: 0.037158037426708354, 33: 0.07169310822672904, 34: 0.10091903290492975}

We got essentially the same values as for the Pagerank vector.

In [149]:
pr
Out[149]:
{1: 0.09700181758983706,
 2: 0.052878391037427,
 3: 0.05707842304763673,
 4: 0.035860643223064786,
 5: 0.021979406974834498,
 6: 0.02911334166344221,
 7: 0.029113341663442205,
 8: 0.02449075803950918,
 9: 0.029765339186167028,
 10: 0.014308950284462798,
 11: 0.021979406974834494,
 12: 0.009564916863537146,
 13: 0.014645186487916188,
 14: 0.02953631497720298,
 15: 0.014535161524273824,
 16: 0.014535161524273824,
 17: 0.016785378110253487,
 18: 0.01455885977424349,
 19: 0.014535161524273824,
 20: 0.01960441671193729,
 21: 0.014535161524273824,
 22: 0.01455885977424349,
 23: 0.014535161524273824,
 24: 0.03152091531163227,
 25: 0.021075455001162945,
 26: 0.02100562817474579,
 27: 0.015043395360629753,
 28: 0.025638803528350497,
 29: 0.019572960509438537,
 30: 0.026287262837112076,
 31: 0.024589336534292478,
 32: 0.037156635922679405,
 33: 0.07169213006588289,
 34: 0.1009179167487121}

Pagerank implementation using matrix operations

In [244]:
import numpy as np
A = nx.adjacency_matrix(karate)
d = np.array([karate.degree(n) for n in karate.nodes])
D = np.diag(1/d)
P = D@A
N = len(karate.nodes)
u = np.ones(N)/N
p = p_old = u
while(True):
    p = (0.85*p_old.T@P+0.15*u.T).T
    if np.linalg.norm(p-p_old) < eps: break
    p_old = p
In [245]:
p
Out[245]:
array([0.09699741, 0.05287696, 0.05707851, 0.03585989, 0.021978  ,
       0.02911123, 0.02911123, 0.02449052, 0.02976604, 0.01430939,
       0.021978  , 0.00956476, 0.01464491, 0.02953647, 0.01453598,
       0.01453598, 0.01678405, 0.01455869, 0.01453598, 0.01960464,
       0.01453598, 0.01455869, 0.01453598, 0.03152247, 0.02107601,
       0.02100617, 0.01504402, 0.02563974, 0.01957344, 0.0262885 ,
       0.02459014, 0.03715806, 0.07169312, 0.10091905])