You are currently looking at version 1.2 of this notebook. To download notebooks and datafiles, as well as get help on Jupyter notebooks in the Coursera platform, visit the Jupyter Notebook FAQ course resource.


Assignment 4

In [1]:
import networkx as nx
import pandas as pd
import numpy as np
import pickle

Part 1 - Random Graph Identification

For the first part of this assignment you will analyze randomly generated graphs and determine which algorithm created them.

In [2]:
P1_Graphs = pickle.load(open('A4_graphs','rb'))
for graph in P1_Graphs:
    print(nx.info(graph))
Name: barabasi_albert_graph(1000,2)
Type: Graph
Number of nodes: 1000
Number of edges: 1996
Average degree:   3.9920
Name: watts_strogatz_graph(1000,10,0.05)
Type: Graph
Number of nodes: 1000
Number of edges: 5000
Average degree:  10.0000
Name: watts_strogatz_graph(750,5,0.075)
Type: Graph
Number of nodes: 750
Number of edges: 1500
Average degree:   4.0000
Name: barabasi_albert_graph(750,4)
Type: Graph
Number of nodes: 750
Number of edges: 2984
Average degree:   7.9573
Name: watts_strogatz_graph(750,4,1)
Type: Graph
Number of nodes: 750
Number of edges: 1500
Average degree:   4.0000


P1_Graphs is a list containing 5 networkx graphs. Each of these graphs were generated by one of three possible algorithms:

  • Preferential Attachment ('PA')
  • Small World with low probability of rewiring ('SW_L')
  • Small World with high probability of rewiring ('SW_H')

Anaylze each of the 5 graphs and determine which of the three algorithms generated the graph.

The graph_identification function should return a list of length 5 where each element in the list is either 'PA', 'SW_L', or 'SW_H'.

In [3]:
def graph_identification():
    
    # Your Code Here
    return ['PA', 'SW_L', 'SW_L', 'PA', 'SW_H'] # Your Answer Here

graph_identification()
Out[3]:
['PA', 'SW_L', 'SW_L', 'PA', 'SW_H']

Part 2 - Company Emails

For the second part of this assignment you will be workking with a company's email network where each node corresponds to a person at the company, and each edge indicates that at least one email has been sent between two people.

The network also contains the node attributes Department and ManagementSalary.

Department indicates the department in the company which the person belongs to, and ManagementSalary indicates whether that person is receiving a management position salary.

In [4]:
G = nx.read_gpickle('email_prediction.txt')
print(nx.info(G))
Name: 
Type: Graph
Number of nodes: 1005
Number of edges: 16706
Average degree:  33.2458

Part 2A - Salary Prediction

Using network G, identify the people in the network with missing values for the node attribute ManagementSalary and predict whether or not these individuals are receiving a management position salary.

To accomplish this, you will need to create a matrix of node features using networkx, train a sklearn classifier on nodes that have ManagementSalary data, and predict a probability of the node receiving a management salary for nodes where ManagementSalary is missing.

Your predictions will need to be given as the probability that the corresponding employee is receiving a management position salary.

The evaluation metric for this assignment is the Area Under the ROC Curve (AUC).

Your grade will be based on the AUC score computed for your classifier. A model which with an AUC of 0.88 or higher will receive full points, and with an AUC of 0.82 or higher will pass (get 80% of the full points).

Using your trained classifier, return a series of length 252 with the data being the probability of receiving management salary, and the index being the node id.

Example:

    1       1.0
    2       0.0
    5       0.8
    8       1.0
        ...
    996     0.7
    1000    0.5
    1001    0.0
    Length: 252, dtype: float64
In [5]:
def salary_predictions():
    
    # Your Code Here
    global G
    # Initialize the dataframe, using the nodes as the index
    df = pd.DataFrame(index=G.nodes())
    # Read in ManagementSalary 
    df['ManagementSalary'] = pd.Series(nx.get_node_attributes(G, 'ManagementSalary'))
    # Calculate link prediction indicators
    df['degree'] = pd.Series(nx.degree(G))
    df['degCent'] = pd.Series(nx.degree_centrality(G))
    df['closeCent'] = pd.Series(nx.closeness_centrality(G))
    df['btwnCent'] = pd.Series(nx.betweenness_centrality(G, normalized = True, endpoints = False, k = 10))
    df['pagRank'] = pd.Series(nx.pagerank(G, alpha=0.8))
    # Code for machine learning
    from sklearn.model_selection import train_test_split
    from sklearn.preprocessing import MinMaxScaler

    # Create model and predict dataframes
    df_model = df.query('ManagementSalary == 0 or ManagementSalary == 1')
    df_predict = df.query('ManagementSalary != 0 and ManagementSalary != 1')
    X = df_model.drop('ManagementSalary', axis=1)
    y = df_model['ManagementSalary']
    X_predict = df_predict.drop('ManagementSalary', axis=1)
    
    # Split and scale test and train
    X_train, X_test, y_train, y_test = train_test_split(X, y, random_state=1)
    scaler = MinMaxScaler()
    X_train_scaled = scaler.fit_transform(X_train)
    X_test_scaled = scaler.transform(X_test)
    X_predict_scaled = scaler.transform(X_predict)

    # Train classifier
    from sklearn.linear_model import LogisticRegression
    clf = LogisticRegression(C=100)
    clf.fit(X_train_scaled, y_train)
    accuracy = clf.score(X_test_scaled, y_test)
    y_predict = clf.predict(X_test_scaled)
    X_predict['proba_clf'] = [x[1] for x in clf.predict_proba(X_predict_scaled)]

    return X_predict['proba_clf'] # Your Answer Here

salary_predictions().head()
Out[5]:
1     0.208041
2     0.574523
5     0.970786
8     0.147921
14    0.388995
Name: proba_clf, dtype: float64

Part 2B - New Connections Prediction

For the last part of this assignment, you will predict future connections between employees of the network. The future connections information has been loaded into the variable future_connections. The index is a tuple indicating a pair of nodes that currently do not have a connection, and the Future Connection column indicates if an edge between those two nodes will exist in the future, where a value of 1.0 indicates a future connection.

In [6]:
future_connections = pd.read_csv('Future_Connections.csv', index_col=0, converters={0: eval})
future_connections.head()
Out[6]:
Future Connection
(6, 840) 0.0
(4, 197) 0.0
(620, 979) 0.0
(519, 872) 0.0
(382, 423) 0.0

Using network G and future_connections, identify the edges in future_connections with missing values and predict whether or not these edges will have a future connection.

To accomplish this, you will need to create a matrix of features for the edges found in future_connections using networkx, train a sklearn classifier on those edges in future_connections that have Future Connection data, and predict a probability of the edge being a future connection for those edges in future_connections where Future Connection is missing.

Your predictions will need to be given as the probability of the corresponding edge being a future connection.

The evaluation metric for this assignment is the Area Under the ROC Curve (AUC).

Your grade will be based on the AUC score computed for your classifier. A model which with an AUC of 0.88 or higher will receive full points, and with an AUC of 0.82 or higher will pass (get 80% of the full points).

Using your trained classifier, return a series of length 122112 with the data being the probability of the edge being a future connection, and the index being the edge as represented by a tuple of nodes.

Example:

    (107, 348)    0.35
    (542, 751)    0.40
    (20, 426)     0.55
    (50, 989)     0.35
              ...
    (939, 940)    0.15
    (555, 905)    0.35
    (75, 101)     0.65
    Length: 122112, dtype: float64
In [7]:
def new_connections_predictions():
    
    # Your Code Here
    global G, future_connections
    # Calculate link prediction indicators
    comNei = [(x, y, (len(list(nx.common_neighbors(G, x, y))))) for x, y in future_connections.index]
    future_connections['comNei'] = pd.Series([c for a, b, c in comNei], index=[(a,b) for a, b, c in comNei])
    jacCoe = list(nx.jaccard_coefficient(G))
    future_connections['jacCoe'] = pd.Series([c for a, b, c in jacCoe], index=[(a,b) for a, b, c in jacCoe])
    resAll = list(nx.resource_allocation_index(G))
    future_connections['resAll'] = pd.Series([c for a, b, c in resAll], index=[(a,b) for a, b, c in resAll])
    accAda = list(nx.adamic_adar_index(G))
    future_connections['accAda'] = pd.Series([c for a, b, c in accAda], index=[(a,b) for a, b, c in accAda])
    preAtt = list(nx.preferential_attachment(G))
    future_connections['preAtt'] = pd.Series([c for a, b, c in preAtt], index=[(a,b) for a, b, c in preAtt])
    comCom = list(nx.cn_soundarajan_hopcroft(G, community='Department'))
    future_connections['comCom'] = pd.Series([c for a, b, c in comCom], index=[(a,b) for a, b, c in comCom])
    comRes = list(nx.ra_index_soundarajan_hopcroft(G, community='Department'))
    future_connections['comRes'] = pd.Series([c for a, b, c in comRes], index=[(a,b) for a, b, c in comRes])

    # Code for machine learning
    from sklearn.model_selection import train_test_split
    from sklearn.preprocessing import MinMaxScaler

    # Create model and predict dataframes
    df_model = future_connections[future_connections['Future Connection'].notnull()]
    df_predict = future_connections[future_connections['Future Connection'].isnull()]
    X = df_model.drop('Future Connection', axis=1)
    y = df_model['Future Connection']
    X_predict = df_predict.drop('Future Connection', axis=1)

    # Split and scale test and train
    X_train, X_test, y_train, y_test = train_test_split(X, y, random_state=2)
    scaler = MinMaxScaler()
    X_train_scaled = scaler.fit_transform(X_train)
    X_test_scaled = scaler.transform(X_test)
    X_predict_scaled = scaler.transform(X_predict)

    # Train classifier
    from sklearn.linear_model import LogisticRegression
    clf = LogisticRegression(C=1000)
    clf.fit(X_train_scaled, y_train)
    accuracy = clf.score(X_test_scaled, y_test)
    y_predict = clf.predict(X_test_scaled)
    X_predict['proba_clf'] = [x[1] for x in clf.predict_proba(X_predict_scaled)]

    return X_predict['proba_clf'] # Your Answer Here

new_connections_predictions().head()
Out[7]:
(107, 348)    0.027314
(542, 751)    0.010554
(20, 426)     0.581542
(50, 989)     0.010615
(942, 986)    0.010682
Name: proba_clf, dtype: float64
In [ ]: