Using the graph from figure 10.1 from the textbook (http://infolab.stanford.edu/~ullman/mmds/book.pdf) to demonstrate



In [3]:

    
#Example Small social newtork as a connection matrix
sc1 = ([(0, 1, 1, 0, 0, 0, 0), 
        (1, 0, 1, 1, 0, 0, 0),
        (1, 1, 0, 0, 0, 0, 0),
        (0, 1, 0, 0, 1, 1, 1),
        (0, 0, 0, 1, 0, 1, 0),
        (0, 0, 0, 1, 1, 0, 1),
        (0, 0, 0, 1, 0, 1, 0)])

http://networkx.github.io/documentation/latest/install.html

pip install networkx

to install networkx into your python modules

pip install networkx --upgrade

to upgrade you previously installed version

You may have to restart your ipython engine to pick up the new module Test your installation by running the new box locally

A full tutorial is available at: http://networkx.github.io/documentation/latest/tutorial/index.html

There are other packages for graph manipulation for python: python-igraph, (http://igraph.org/python/#pydoc1) Graph-tool, (https://graph-tool.skewed.de)

I picked networkx because it took little effort to install.



In [4]:

    
import networkx as nx
G1 = nx.Graph()



In [5]:

    
G1.add_nodes_from(['A','B','C','D','E','F','G'])
G1.nodes()









    Out[5]:





['A', 'C', 'B', 'E', 'D', 'G', 'F']



In [6]:

    
G1.add_edges_from([('A','B'),('A','C')])
G1.add_edges_from([('B','C'),('B','D')])
G1.add_edges_from([('D','E'),('D','F'),('D','G')])
G1.add_edges_from([('E','F')])
G1.add_edges_from([('F','G')])



In [7]:

    
G1.number_of_edges()









    Out[7]:





9



In [8]:

    
G1.edges()









    Out[8]:





[('A', 'C'),
 ('A', 'B'),
 ('C', 'B'),
 ('B', 'D'),
 ('E', 'D'),
 ('E', 'F'),
 ('D', 'G'),
 ('D', 'F'),
 ('G', 'F')]



In [9]:

    
G1.neighbors('D')









    Out[9]:





['B', 'E', 'G', 'F']



In [10]:

    
import matplotlib.pyplot as plt
#drawing the graph
%matplotlib inline



In [14]:

    
nx.draw(G1)



In [32]:

    
pos=nx.spring_layout(G1)
nx.draw(G1,pos,node_color='y', edge_color='r', node_size=600, width=3.0)
nx.draw_networkx_labels(G1,pos,color='W',font_size=20,font_family='sans-serif')
#https://networkx.github.io/documentation/latest/reference/generated/networkx.drawing.nx_pylab.draw_networkx.html
#Some parameters to play with









    Out[32]:





{'A': <matplotlib.text.Text at 0xe7d20b8>,
 'B': <matplotlib.text.Text at 0xe7d2e80>,
 'C': <matplotlib.text.Text at 0xe7d2588>,
 'D': <matplotlib.text.Text at 0xe4e92b0>,
 'E': <matplotlib.text.Text at 0xe4e9128>,
 'F': <matplotlib.text.Text at 0xe7c6f98>,
 'G': <matplotlib.text.Text at 0xe4e9278>}

Let's play with some algorithms in class: https://networkx.github.io/documentation/latest/reference/algorithms.html

Social Graph analysis algorithms

Betweenness: https://networkx.github.io/documentation/latest/reference/algorithms.centrality.html#betweenness

EigenVector centrality https://networkx.github.io/documentation/latest/reference/algorithms.centrality.html#eigenvector

Clustering per node https://networkx.github.io/documentation/latest/reference/generated/networkx.algorithms.cluster.clustering.html

All Shortest Paths https://networkx.github.io/documentation/latest/reference/generated/networkx.algorithms.shortest_paths.generic.all_shortest_paths.html

Laplacian matrix https://networkx.github.io/documentation/latest/reference/generated/networkx.linalg.laplacianmatrix.laplacian_matrix.html#networkx.linalg.laplacianmatrix.laplacian_matrix

Each of the students pair up and work on demonstrating a networkx algorithm Create a new ipython page and submit it



In [42]:

    
#Enumeration of all cliques
list(nx.enumerate_all_cliques(G1))









    Out[42]:





[['A'],
 ['C'],
 ['B'],
 ['E'],
 ['D'],
 ['G'],
 ['F'],
 ['A', 'C'],
 ['A', 'B'],
 ['C', 'B'],
 ['B', 'D'],
 ['E', 'D'],
 ['E', 'F'],
 ['D', 'G'],
 ['D', 'F'],
 ['G', 'F'],
 ['A', 'C', 'B'],
 ['E', 'D', 'F'],
 ['D', 'G', 'F']]



In [38]:

    
list(nx.cliques_containing_node(G1,'A'))









    Out[38]:





[['A', 'C', 'B']]



In [39]:

    
list(nx.cliques_containing_node(G1,'D'))









    Out[39]:





[['D', 'B'], ['D', 'F', 'E'], ['D', 'F', 'G']]