# Social Networks and Text Analysis - Ranking algorithms


## 1. PageRank

Define a function that computes the Page Rank given an Adjacency matrix.


```python
import networkx as nx
import numpy as np
import matplotlib.pyplot as plt 
import re

#Magic functions (%) for setting up the matplotlib and increase the resolution of the plots:
%matplotlib inline
%config InlineBackend.figure_format = 'retina'
```


```python


```


```python
#Create a network:
G = nx.erdos_renyi_graph(n=100, p=0.2)
print(nx.info(G))
```

    Name: 
    Type: Graph
    Number of nodes: 100
    Number of edges: 984
    Average degree:  19.6800



```python
#Save the adjacency matrix:
Adj = nx.to_numpy_matrix(G).A
```


```python
#Plot the matrix of zeros and ones:
plt.imshow(Adj, origin='lower', interpolation='nearest')
plt.title("Adjacency - Matrix")
plt.show()
```


```python
#Create the transition probabilities function. 
#Which is the adjacency divided by the degree of each node
#In this case is the row or the column (Because is undirected and simetrical)
R = Adj/Adj.sum(axis=1)[:,None]
plt.imshow(R, origin='lower', interpolation='nearest')
plt.title("Adjacency divided by the degree - Matrix")
plt.colorbar()
plt.show()
```


```python
#Create your page rank function:
def Page_Rank(G):
    #Set the adjacency matrix
    Adj = nx.to_numpy_matrix(G).A
    
    #Divide the adjacency matrix by the degree of the node = sum of the columns by row:
    R = Adj/Adj.sum(axis=1)[:,None]
    
    #Compute the eigen values and eigenvectors for the corrected matrix
    eigen_values, eigenvectors = np.linalg.eig(R.T)
    
    #Select the largest eigenvalue
    ind = np.argmax(eigen_values)
    
    #Select the corresponding eigenvector:
    largest = np.array(eigenvectors[:, ind]).flatten().real
    
    #Normalize the vector:
    norm = float(largest.sum())
    
    #Return the values:
    return(dict(zip(G, map(float, largest / norm))))
```


```python
#Check the values:
Page_Rank(G)
```




    {0: 0.013719512195121948,
     1: 0.014227642276422757,
     2: 0.007113821138211382,
     3: 0.013211382113821134,
     4: 0.006605691056910564,
     5: 0.009654471544715446,
     6: 0.011178861788617876,
     7: 0.009146341463414644,
     8: 0.010162601626016251,
     9: 0.010670731707317074,
     10: 0.011178861788617888,
     11: 0.009654471544715437,
     12: 0.009654471544715446,
     13: 0.008130081300813012,
     14: 0.010670731707317065,
     15: 0.010162601626016265,
     16: 0.01016260162601625,
     17: 0.011178861788617885,
     18: 0.005081300813008127,
     19: 0.009146341463414628,
     20: 0.009654471544715444,
     21: 0.01067073170731707,
     22: 0.008638211382113821,
     23: 0.010670731707317065,
     24: 0.008638211382113825,
     25: 0.007113821138211386,
     26: 0.007113821138211376,
     27: 0.008130081300813012,
     28: 0.01067073170731707,
     29: 0.008638211382113826,
     30: 0.010162601626016258,
     31: 0.013211382113821137,
     32: 0.01016260162601625,
     33: 0.00965447154471545,
     34: 0.01117886178861789,
     35: 0.00914634146341463,
     36: 0.009146341463414625,
     37: 0.010162601626016258,
     38: 0.010162601626016263,
     39: 0.007113821138211378,
     40: 0.010670731707317062,
     41: 0.006097560975609755,
     42: 0.009654471544715446,
     43: 0.009146341463414623,
     44: 0.010162601626016255,
     45: 0.008130081300813012,
     46: 0.011686991869918692,
     47: 0.0076219512195121976,
     48: 0.011178861788617891,
     49: 0.00914634146341463,
     50: 0.006097560975609758,
     51: 0.012195121951219507,
     52: 0.007621951219512186,
     53: 0.009654471544715453,
     54: 0.009654471544715451,
     55: 0.012703252032520323,
     56: 0.0116869918699187,
     57: 0.011178861788617885,
     58: 0.015243902439024386,
     59: 0.008638211382113814,
     60: 0.00914634146341464,
     61: 0.011178861788617883,
     62: 0.005081300813008127,
     63: 0.009654471544715451,
     64: 0.008638211382113826,
     65: 0.00965447154471544,
     66: 0.012703252032520328,
     67: 0.013211382113821148,
     68: 0.008130081300813006,
     69: 0.008638211382113814,
     70: 0.006097560975609753,
     71: 0.010670731707317067,
     72: 0.008130081300813018,
     73: 0.008638211382113833,
     74: 0.007621951219512189,
     75: 0.011178861788617893,
     76: 0.009146341463414637,
     77: 0.00965447154471544,
     78: 0.009146341463414637,
     79: 0.010670731707317072,
     80: 0.012195121951219506,
     81: 0.011178861788617888,
     82: 0.010162601626016269,
     83: 0.013719512195121943,
     84: 0.010670731707317077,
     85: 0.010670731707317072,
     86: 0.013211382113821142,
     87: 0.010670731707317074,
     88: 0.01270325203252032,
     89: 0.009654471544715446,
     90: 0.010162601626016243,
     91: 0.00914634146341463,
     92: 0.015752032520325202,
     93: 0.012703252032520315,
     94: 0.009146341463414639,
     95: 0.011686991869918697,
     96: 0.009146341463414639,
     97: 0.009654471544715455,
     98: 0.01016260162601626,
     99: 0.0116869918699187}



Define a function that computes topic specific Page Rank following the advice of Prof.  Leskovec:


```python
#Create your topic page rank function:
def Topic_Specific_Page_Rank(G, special_Set,Beta):
    #Set the adjacency matrix
    Adj = nx.to_numpy_matrix(G).A
    
    #Divide the adjacency matrix by the degree of the node = sum of the columns by row:
    R = Adj/Adj.sum(axis=1)[:,None]
    
    for i,row in enumerate(R):
        if i in special_Set:
            R[i] = Beta*row+(1-Beta)/len(special_Set)
        else:
            R[i] = Beta*row
            
    plt.imshow(R, origin='lower', interpolation='nearest')
    plt.title("Adjacency divided by the degree with the specific Set - Matrix")
    plt.xlabel('ID')
    plt.ylabel('ID')
    plt.colorbar()
    plt.show()
    #----------------------------------------
    #This part comes from the other function:
    #----------------------------------------
    #Compute the eigen values and eigenvectors for the corrected matrix
    eigen_values, eigenvectors = np.linalg.eig(R.T)
    
    #Select the largest eigenvalue
    ind = np.argmax(eigen_values)
    
    #Select the corresponding eigenvector:
    largest = np.array(eigenvectors[:, ind]).flatten().real
    
    #Normalize the vector:
    norm = float(largest.sum())
    
    #Return the values:
    return(dict(zip(G, map(float, largest / norm))))
```


```python
#Run the function and plot the matrix:
#Change the special set to random nodes!
Topic_Specific_Page_Rank(G, special_Set=list(range(5)),Beta=0.5)
```

# 2. LexRank

Define the LexRank function.  Select a piece of text (10-20 sentences) that you would like to summarize.  Thereare two parameters you can vary:

<ol>
 <li>the cosine similarity threshold determines how similar two sentences have to be in order to share and edge.</li>
 <li>the salience threshold determines how high a sentence’s PageRank has to be in order for that sentence tobe included in the summary.</li>
</ol>


Cosine similarity function for two vectors:

\begin{equation} similarity = \cos ({\theta})= {{\bf A}\cdot {\bf B} \over \|{\bf A}\| \|{\bf B}\|} = \frac{ \sum_{i=1}^{n}{{\bf A}_i{\bf B}_i} }{ \sqrt{\sum_{i=1}^{n}{({\bf A}_i)^2}} \sqrt{\sum_{i=1}^{n}{({\bf B}_i)^2}} } \end{equation}


```python
with open('Text.txt') as f: #<-- #Read the piece of text: INVISIBLE WOMEN.
    text = f.read()
#Separate the text into sentences by the dot:
List_Sentences = text.split('.')
```


```python
from collections import Counter #<-function for counting frequency in an array

#1. We need to convert the text to vector of words with the frequency of ech word.
def get_vector_of_words(text):
    Words = re.findall(r'\w+', text)
    Words_Frequency = Counter(Words)
    return(Words_Frequency)

#Example with the first sentence:
get_vector_of_words(List_Sentences[0])
```




    Counter({'When': 1,
             'Hillary': 1,
             'Clinton': 1,
             'wanted': 1,
             'to': 1,
             'speak': 1,
             'about': 1,
             'women': 1,
             's': 1,
             'rights': 1,
             'at': 1,
             'the': 1,
             '1995': 1,
             'United': 1,
             'Nations': 1,
             'Fourth': 1,
             'World': 1,
             'Conference': 1,
             'on': 1,
             'Women': 1,
             'in': 1,
             'Beijing': 1,
             'even': 1,
             'her': 1,
             'own': 1,
             'side': 1,
             'was': 1,
             'dubious': 1})




```python
#2. Compute the cosine similarity:
def Cosine_Similarity(vec_1, vec_2):
    #Get the bag words with all the words:
    Bag_words = set(set(vec_1.keys()).union(set(vec_2.keys())))
    
    #Multiply the number of times that the words appear in both texts:
    Dot_multiplication = sum([vec_1[w]*vec_2[w] for w in Bag_words if w in vec_1 and w in vec_2])
    
    
    #Multiply the norms of each vector:
    Sum_Vec_1 = np.sqrt(sum([vec_1[w]**2 for w in vec_1.keys()]))
    Sum_Vec_2 = np.sqrt(sum([vec_2[w]**2 for w in vec_2.keys()]))
    Norm_multiplication = Sum_Vec_1*Sum_Vec_2
    if Norm_multiplication != 0:
        return(Dot_multiplication/Norm_multiplication)
    else:
        return(np.nan)
    
```


```python
#Example for the first two sentences:
vec_1 = get_vector_of_words(List_Sentences[1])
vec_2 = get_vector_of_words(List_Sentences[0])
Cosine_Similarity(vec_1, vec_2)
```




    0.27940948018117095




```python
#3. Create the Lex-Rank function:
def LexRank(List_Sentences, c_t, s_t):
    #Create the empty network:
    G = nx.Graph()
    
    #Iterate over all the sentences:
    for n1 in range(len(List_Sentences)):
        for n2 in range(len(List_Sentences)):
            
            #Avoid overwrite links and create loops:
            if n1 != n2 and (n1,n2) not in G.edges():
                
                #Compute the cosine similarity:
                vec_1 = get_vector_of_words(List_Sentences[n1])
                vec_2 = get_vector_of_words(List_Sentences[n2])
                Cos_Sim = Cosine_Similarity(vec_1, vec_2)
                
                #Add the edge just if the cosine similarity is larger than the threshold:
                if Cos_Sim > c_t:
                    G.add_edge(n1,n2, weight =Cos_Sim)
                    
                    for node in [n1,n2]:
                        if 'Sentence' not in G.nodes[node].keys():
                            G.nodes[node]['Sentence'] = List_Sentences[node]
    print(nx.info(G))
    
    #Compute the pagerank of the network.
    #Select the nodes in the threshold for the summary:
    PR = nx.pagerank(G)
    #Select the nodes that overpass the threshold:
    Selected_Nodes = {u:v for u,v in PR.items() if v>s_t}
    print('')
    print('Selected nodes by Page-Rank:')
    print(Selected_Nodes)
    print({i: G.nodes[i]['Sentence'] for i in Selected_Nodes})
    
    #Draw the network and highlight in red the selected nodes:
    color = ['darkred' if n in Selected_Nodes.keys() else 'darkblue' for n in G.nodes()]
    pos = nx.fruchterman_reingold_layout(G)
    nx.draw_networkx(G,pos=pos, node_color = color, alpha=0.8, edge_color='white', font_color='white')
    nx.draw_networkx_edges(G, pos=pos, alpha=0.5)
    plt.show()
```


```python
# 3. Set the threshold:
Cosine_Threshold = 0.2
Salience_Threshold = 0.1
LexRank(List_Sentences, Cosine_Threshold, Salience_Threshold)
```


```python

```


```python

```

f7e5cb959680c9d48f6bed26fcd01c1507f1d828
ipynb
Jupyter Notebook
Practice/P7_ranking_algo.ipynb
ganesh0211/social-network-analysis
dfb677a571c855d49ccb4cb760e1a445c465e767
Unlicense
2021-04-26T23:07:51.000Z
2021-05-31T13:38:16.000Z
Practice/P7_ranking_algo.ipynb
ganesh0211/social-network-analysis
dfb677a571c855d49ccb4cb760e1a445c465e767
Unlicense
Practice/P7_ranking_algo.ipynb
ganesh0211/social-network-analysis
dfb677a571c855d49ccb4cb760e1a445c465e767
Unlicense
Qwen/Qwen-72B
1. YES
2. YES