Social network Graph Link Prediction - Facebook Challenge
","metadata":{"id":"_ngfVeOrX7If"}},{"cell_type":"markdown","source":"### Problem statement: \nGiven a directed social graph, have to predict missing links to recommend users (Link Prediction in graph)","metadata":{"id":"BIdTcywoX7Ih"}},{"cell_type":"markdown","source":"### Data Overview\nTaken data from facebook's recruting challenge on kaggle https://www.kaggle.com/c/FacebookRecruiting \ndata contains two columns source and destination eac edge in graph \n - Data columns (total 2 columns): \n - source_node int64 \n - destination_node int64 ","metadata":{"id":"EKXSOWj3X7Ii"}},{"cell_type":"markdown","source":"### Mapping the problem into supervised learning problem:\n- Generated training samples of good and bad links from given directed graph and for each link got some features like no of followers, is he followed back, page rank, katz score, adar index, some svd fetures of adj matrix, some weight features etc. and trained ml model based on these features to predict link. \n- Some reference papers and videos : \n - https://www.cs.cornell.edu/home/kleinber/link-pred.pdf\n - https://www3.nd.edu/~dial/publications/lichtenwalter2010new.pdf\n - https://kaggle2.blob.core.windows.net/forum-message-attachments/2594/supervised_link_prediction.pdf\n - https://www.youtube.com/watch?v=2M77Hgy17cg","metadata":{"id":"frIBf5F2X7Ij"}},{"cell_type":"markdown","source":"### Business objectives and constraints: \n- No low-latency requirement.\n- Probability of prediction is useful to recommend ighest probability links","metadata":{"id":"zej3Dqi7X7Ik"}},{"cell_type":"markdown","source":"### Performance metric for supervised learning: \n- Both precision and recall is important so F1 score is good choice\n- Confusion matrix","metadata":{"id":"fSW6zbsHX7Il"}},{"cell_type":"code","source":"#Importing Libraries\n# please do go through this python notebook: \nimport warnings\nwarnings.filterwarnings(\"ignore\")\n\nimport csv\nimport pandas as pd#pandas to create small dataframes \nimport datetime #Convert to unix time\nimport time #Convert to unix time\n# if numpy is not installed already : pip3 install numpy\nimport numpy as np#Do aritmetic operations on arrays\n# matplotlib: used to plot graphs\nimport matplotlib\nimport matplotlib.pylab as plt\nimport seaborn as sns#Plots\nfrom matplotlib import rcParams#Size of plots \nfrom sklearn.cluster import MiniBatchKMeans, KMeans#Clustering\nimport math\nimport pickle\nimport os\n# to install xgboost: pip3 install xgboost\nimport xgboost as xgb\n\nimport warnings\nimport networkx as nx\nimport pdb\nimport pickle\nfrom pandas import HDFStore,DataFrame\nfrom pandas import read_hdf\nfrom scipy.sparse.linalg import svds, eigs\nimport gc\nfrom tqdm import tqdm","metadata":{"id":"jGe4BKx9X7Im","execution":{"iopub.status.busy":"2024-01-01T19:50:22.980779Z","iopub.execute_input":"2024-01-01T19:50:22.981127Z","iopub.status.idle":"2024-01-01T19:50:22.989627Z","shell.execute_reply.started":"2024-01-01T19:50:22.981091Z","shell.execute_reply":"2024-01-01T19:50:22.988261Z"},"trusted":true},"execution_count":null,"outputs":[]},{"cell_type":"code","source":"# đọc đồ thị\nif not os.path.isfile('/kaggle/working/train_woheader.csv'):\n traincsv = pd.read_csv('/kaggle/input/FacebookRecruiting/train.csv')\n print(traincsv[traincsv.isna().any(1)])\n print(traincsv.info())\n print(\"Number of diplicate entries: \",sum(traincsv.duplicated()))\n traincsv.to_csv('/kaggle/working/train_woheader.csv',header=False,index=False)\n print(\"saved the graph into file\")\nelse:\n g=nx.read_edgelist('/kaggle/working/train_woheader.csv',delimiter=',',create_using=nx.DiGraph(),nodetype=int)\n print(nx.info(g))","metadata":{"id":"OOi4aONAX7Iv","outputId":"b413d19f-8322-43df-c9da-d88a60d5fe1c","execution":{"iopub.status.busy":"2024-01-01T19:50:23.020665Z","iopub.execute_input":"2024-01-01T19:50:23.021048Z","iopub.status.idle":"2024-01-01T19:51:30.268865Z","shell.execute_reply.started":"2024-01-01T19:50:23.021012Z","shell.execute_reply":"2024-01-01T19:51:30.267848Z"},"trusted":true},"execution_count":null,"outputs":[]},{"cell_type":"markdown","source":"> Đồ thị được đọc từ file **train_woheader.csv** là đồ thị có hướng có 1862220 nút và 9437519 cạnh, trung bình indegree và outdegree là 5.0679.","metadata":{}},{"cell_type":"markdown","source":"> Hiển thị một đồ thị con với mẫu 50 dữ liệu trong đồ thị gốc","metadata":{"id":"ba1XVmouX7I2"}},{"cell_type":"code","source":"if not os.path.isfile('train_woheader_sample.csv'):\n pd.read_csv('/kaggle/input/FacebookRecruiting/train.csv', nrows=50).to_csv('train_woheader_sample.csv',header=False,index=False)\n \nsubgraph=nx.read_edgelist('train_woheader_sample.csv',delimiter=',',create_using=nx.DiGraph(),nodetype=int)\n# https://stackoverflow.com/questions/9402255/drawing-a-huge-graph-with-networkx-and-matplotlib\n\npos=nx.spring_layout(subgraph)\nnx.draw(subgraph,pos,node_color='#A0CBE2',edge_color='#00bb5e',width=1,edge_cmap=plt.cm.Blues,with_labels=True)\nplt.savefig(\"graph_sample.pdf\")\nprint(nx.info(subgraph))","metadata":{"id":"rvhGErEXX7I3","outputId":"3211434c-3826-4d98-af7e-949329c2906a","execution":{"iopub.status.busy":"2024-01-01T19:51:30.271097Z","iopub.execute_input":"2024-01-01T19:51:30.271445Z","iopub.status.idle":"2024-01-01T19:51:30.910281Z","shell.execute_reply.started":"2024-01-01T19:51:30.271405Z","shell.execute_reply":"2024-01-01T19:51:30.909599Z"},"trusted":true},"execution_count":null,"outputs":[]},{"cell_type":"markdown","source":"# 1. Exploratory Data Analysis","metadata":{"id":"QirDnZ-FX7I8"}},{"cell_type":"code","source":"# No of Unique persons \nprint(\"The number of unique persons\",len(g.nodes()))","metadata":{"id":"gdlTIj97X7I9","outputId":"2e956d78-2d25-45be-e390-fa64bd98225c","execution":{"iopub.status.busy":"2024-01-01T19:51:30.911253Z","iopub.execute_input":"2024-01-01T19:51:30.911562Z","iopub.status.idle":"2024-01-01T19:51:30.915455Z","shell.execute_reply.started":"2024-01-01T19:51:30.911537Z","shell.execute_reply":"2024-01-01T19:51:30.914934Z"},"trusted":true},"execution_count":null,"outputs":[]},{"cell_type":"markdown","source":"> Số lượng nút trong đồ thị tương đương với số người trong mạng là 1862220","metadata":{}},{"cell_type":"markdown","source":"## 1.1 No of followers for each person","metadata":{"id":"BdvJPYMHX7JC"}},{"cell_type":"code","source":"indegree_dist = list(dict(g.in_degree()).values())\nindegree_dist.sort()\nplt.figure(figsize=(10,6))\nplt.plot(indegree_dist)\nplt.xlabel('Index No')\nplt.ylabel('No Of Followers')\nplt.show()","metadata":{"id":"4fFEbqiSX7JD","outputId":"d4aab961-ab7b-44c8-a6b0-de6c9ed04691","execution":{"iopub.status.busy":"2024-01-01T19:51:30.916201Z","iopub.execute_input":"2024-01-01T19:51:30.916513Z","iopub.status.idle":"2024-01-01T19:51:32.643955Z","shell.execute_reply.started":"2024-01-01T19:51:30.916489Z","shell.execute_reply":"2024-01-01T19:51:32.641603Z"},"trusted":true},"execution_count":null,"outputs":[]},{"cell_type":"markdown","source":"> Tìm hiểu về số lượng người theo dõi trong mạng xã hội facebook của mỗi cá nhân ta thấy số lượng này giao động trong khoảng từ 0 đến khoảng 500 người.","metadata":{}},{"cell_type":"code","source":"indegree_dist = list(dict(g.in_degree()).values())\nindegree_dist.sort()\nplt.figure(figsize=(10,6))\nplt.plot(indegree_dist[0:1500000])\nplt.xlabel('Index No')\nplt.ylabel('No Of Followers')\nplt.show()","metadata":{"id":"CZPczewbX7JL","outputId":"ef79e2c1-ccc2-4d11-915d-01bee576f0a2","execution":{"iopub.status.busy":"2024-01-01T19:51:32.647816Z","iopub.execute_input":"2024-01-01T19:51:32.648193Z","iopub.status.idle":"2024-01-01T19:51:34.345160Z","shell.execute_reply.started":"2024-01-01T19:51:32.648160Z","shell.execute_reply":"2024-01-01T19:51:34.343531Z"},"trusted":true},"execution_count":null,"outputs":[]},{"cell_type":"code","source":"plt.boxplot(indegree_dist)\nplt.ylabel('No Of Followers')\nplt.show()","metadata":{"id":"Wqf9qkr_X7JS","outputId":"6e880aa0-6fe3-4d22-e813-85141dab0678","execution":{"iopub.status.busy":"2024-01-01T19:51:34.347814Z","iopub.execute_input":"2024-01-01T19:51:34.348105Z","iopub.status.idle":"2024-01-01T19:51:34.711050Z","shell.execute_reply.started":"2024-01-01T19:51:34.348076Z","shell.execute_reply":"2024-01-01T19:51:34.709869Z"},"trusted":true},"execution_count":null,"outputs":[]},{"cell_type":"code","source":"### 90-100 percentile\nfor i in range(0,11):\n print(90+i,'percentile value is',np.percentile(indegree_dist,90+i))","metadata":{"id":"5q9wSyvGX7JY","outputId":"54a2deaa-d1f0-487d-d6ab-84d1645be6ed","execution":{"iopub.status.busy":"2024-01-01T19:51:34.712129Z","iopub.execute_input":"2024-01-01T19:51:34.712361Z","iopub.status.idle":"2024-01-01T19:51:36.181139Z","shell.execute_reply.started":"2024-01-01T19:51:34.712335Z","shell.execute_reply":"2024-01-01T19:51:36.179486Z"},"trusted":true},"execution_count":null,"outputs":[]},{"cell_type":"markdown","source":"> 99% người dùng có số lượng người theo dõi chỉ với 40 người.\n> Số lượng người theo dõi tối đa của một người dùng là 522.","metadata":{"id":"9HvreJYlX7Jf"}},{"cell_type":"code","source":"### 99-100 percentile\nfor i in range(10,110,10):\n print(99+(i/100),'percentile value is',np.percentile(indegree_dist,99+(i/100)))","metadata":{"id":"mt8DA-MmX7Jg","outputId":"0ac13b00-ca01-4baf-cb93-fc50efc2959b","execution":{"iopub.status.busy":"2024-01-01T19:51:36.183072Z","iopub.execute_input":"2024-01-01T19:51:36.183452Z","iopub.status.idle":"2024-01-01T19:51:37.552069Z","shell.execute_reply.started":"2024-01-01T19:51:36.183412Z","shell.execute_reply":"2024-01-01T19:51:37.550694Z"},"trusted":true},"execution_count":null,"outputs":[]},{"cell_type":"markdown","source":"> Con số người theo dõi tăng lên 112 người với 99.9% người dùng.","metadata":{}},{"cell_type":"code","source":"%matplotlib inline\nsns.set_style('ticks')\nfig, ax = plt.subplots()\nfig.set_size_inches(11.7, 8.27)\nsns.distplot(indegree_dist, color='#16A085')\nplt.xlabel('PDF of Indegree')\nsns.despine()\n#plt.show()","metadata":{"id":"hZQed_RqX7Jk","outputId":"bb5921e4-c9f5-48b8-c0d7-963d86cc9f99","execution":{"iopub.status.busy":"2024-01-01T19:51:37.553265Z","iopub.execute_input":"2024-01-01T19:51:37.553529Z","iopub.status.idle":"2024-01-01T19:51:38.073857Z","shell.execute_reply.started":"2024-01-01T19:51:37.553499Z","shell.execute_reply":"2024-01-01T19:51:38.072628Z"},"trusted":true},"execution_count":null,"outputs":[]},{"cell_type":"markdown","source":"## 1.2 No of people each person is following","metadata":{"id":"F_rfNRYCX7Jx"}},{"cell_type":"code","source":"outdegree_dist = list(dict(g.out_degree()).values())\noutdegree_dist.sort()\nplt.figure(figsize=(10,6))\nplt.plot(outdegree_dist)\nplt.xlabel('Index No')\nplt.ylabel('No Of people each person is following')\nplt.show()","metadata":{"id":"L-2plpMuX7Jy","outputId":"1355b363-1079-44e5-d062-ee352036d126","execution":{"iopub.status.busy":"2024-01-01T19:51:38.075382Z","iopub.execute_input":"2024-01-01T19:51:38.075702Z","iopub.status.idle":"2024-01-01T19:51:39.732629Z","shell.execute_reply.started":"2024-01-01T19:51:38.075667Z","shell.execute_reply":"2024-01-01T19:51:39.731195Z"},"trusted":true},"execution_count":null,"outputs":[]},{"cell_type":"markdown","source":"> Số lượng người mà mỗi người dùng theo dõi giao động trong khoảng từ 0 - 1600 người","metadata":{}},{"cell_type":"code","source":"outdegree_dist = list(dict(g.out_degree()).values())\noutdegree_dist.sort()\nplt.figure(figsize=(10,6))\nplt.plot(outdegree_dist[0:1500000])\nplt.xlabel('Index No')\nplt.ylabel('No Of people each person is following')\nplt.show()","metadata":{"id":"aNaQeE5cX7J2","outputId":"c59a155f-c894-4600-9daf-35a45f7c8d4d","execution":{"iopub.status.busy":"2024-01-01T19:51:39.734160Z","iopub.execute_input":"2024-01-01T19:51:39.734657Z","iopub.status.idle":"2024-01-01T19:51:41.376356Z","shell.execute_reply.started":"2024-01-01T19:51:39.734588Z","shell.execute_reply":"2024-01-01T19:51:41.374952Z"},"trusted":true},"execution_count":null,"outputs":[]},{"cell_type":"code","source":"plt.boxplot(outdegree_dist)\nplt.ylabel('No Of people each person is following')\nplt.show()","metadata":{"id":"HVYdHvLAX7J7","outputId":"da8978d6-76fe-400c-ff7d-ff60d2303efb","execution":{"iopub.status.busy":"2024-01-01T19:51:41.378047Z","iopub.execute_input":"2024-01-01T19:51:41.378356Z","iopub.status.idle":"2024-01-01T19:51:41.773764Z","shell.execute_reply.started":"2024-01-01T19:51:41.378322Z","shell.execute_reply":"2024-01-01T19:51:41.772529Z"},"trusted":true},"execution_count":null,"outputs":[]},{"cell_type":"code","source":"### 90-100 percentile\nfor i in range(0,11):\n print(90+i,'percentile value is',np.percentile(outdegree_dist,90+i))","metadata":{"id":"FVGmz09xX7KB","outputId":"e2058803-7251-4836-df99-28075908ae99","execution":{"iopub.status.busy":"2024-01-01T19:51:41.775241Z","iopub.execute_input":"2024-01-01T19:51:41.775593Z","iopub.status.idle":"2024-01-01T19:51:43.125621Z","shell.execute_reply.started":"2024-01-01T19:51:41.775553Z","shell.execute_reply":"2024-01-01T19:51:43.124348Z"},"trusted":true},"execution_count":null,"outputs":[]},{"cell_type":"markdown","source":"> 99% người dùng theo dõi chỉ 40 người.\n\n> Tối đa là 1566 người.","metadata":{}},{"cell_type":"code","source":"### 99-100 percentile\nfor i in range(10,110,10):\n print(99+(i/100),'percentile value is',np.percentile(outdegree_dist,99+(i/100)))","metadata":{"id":"zcNoTvuzX7KF","outputId":"b74b3bc9-146e-4106-b3df-af5f2a8938a0","execution":{"iopub.status.busy":"2024-01-01T19:51:43.128634Z","iopub.execute_input":"2024-01-01T19:51:43.128996Z","iopub.status.idle":"2024-01-01T19:51:44.346685Z","shell.execute_reply.started":"2024-01-01T19:51:43.128946Z","shell.execute_reply":"2024-01-01T19:51:44.345348Z"},"trusted":true},"execution_count":null,"outputs":[]},{"cell_type":"markdown","source":" > Con số người được theo dõi tăng 123 người đối với 99.9% người dùng.","metadata":{}},{"cell_type":"code","source":"sns.set_style('ticks')\nfig, ax = plt.subplots()\nfig.set_size_inches(11.7, 8.27)\nsns.distplot(outdegree_dist, color='#16A085')\nplt.xlabel('PDF of Outdegree')\nsns.despine()","metadata":{"id":"27t51jOjX7KK","outputId":"9655f989-f453-47db-be7b-732351ee3db3","execution":{"iopub.status.busy":"2024-01-01T19:51:44.347945Z","iopub.execute_input":"2024-01-01T19:51:44.348221Z","iopub.status.idle":"2024-01-01T19:51:44.869664Z","shell.execute_reply.started":"2024-01-01T19:51:44.348191Z","shell.execute_reply":"2024-01-01T19:51:44.868268Z"},"trusted":true},"execution_count":null,"outputs":[]},{"cell_type":"code","source":"print('No of persons those are not following anyone are' ,sum(np.array(outdegree_dist)==0),'and % is',\n sum(np.array(outdegree_dist)==0)*100/len(outdegree_dist) )","metadata":{"id":"9LOGY_CyX7KT","outputId":"eb5a2706-7829-4f99-c46d-84b0f7d03328","execution":{"iopub.status.busy":"2024-01-01T19:51:44.871450Z","iopub.execute_input":"2024-01-01T19:51:44.871764Z","iopub.status.idle":"2024-01-01T19:51:52.177669Z","shell.execute_reply.started":"2024-01-01T19:51:44.871730Z","shell.execute_reply":"2024-01-01T19:51:52.175868Z"},"trusted":true},"execution_count":null,"outputs":[]},{"cell_type":"markdown","source":"> Số người dùng không theo dõi ai là 274512 người chiếm gần 15% tổng số dữ liệu.","metadata":{}},{"cell_type":"code","source":"print('No of persons having zero followers are' ,sum(np.array(indegree_dist)==0),'and % is',\n sum(np.array(indegree_dist)==0)*100/len(indegree_dist) )","metadata":{"id":"hi30e3RmX7KX","outputId":"f2feffac-585d-42ed-937f-5b61e1023040","execution":{"iopub.status.busy":"2024-01-01T19:51:52.179088Z","iopub.execute_input":"2024-01-01T19:51:52.179378Z","iopub.status.idle":"2024-01-01T19:51:59.418106Z","shell.execute_reply.started":"2024-01-01T19:51:52.179343Z","shell.execute_reply":"2024-01-01T19:51:59.416331Z"},"trusted":true},"execution_count":null,"outputs":[]},{"cell_type":"markdown","source":"> Số người dùng không có người theo dõi là 188043 người chiếm 10% tổng dữ liệu.","metadata":{}},{"cell_type":"code","source":"count=0\nfor i in g.nodes():\n if len(list(g.predecessors(i)))==0 :\n if len(list(g.successors(i)))==0:\n count+=1\nprint('No of persons those are not not following anyone and also not having any followers are',count)","metadata":{"id":"rzX8vbh5X7Kc","outputId":"0fa6651f-4449-478f-a480-e289b9706afd","execution":{"iopub.status.busy":"2024-01-01T19:51:59.419466Z","iopub.execute_input":"2024-01-01T19:51:59.419746Z","iopub.status.idle":"2024-01-01T19:52:02.775608Z","shell.execute_reply.started":"2024-01-01T19:51:59.419699Z","shell.execute_reply":"2024-01-01T19:52:02.774337Z"},"trusted":true},"execution_count":null,"outputs":[]},{"cell_type":"markdown","source":"> Không có người dùng nào không theo dõi ai và cũng không ai theo dõi ","metadata":{}},{"cell_type":"markdown","source":"## 1.3 both followers + following ","metadata":{"id":"J7tiBqS3X7Kh"}},{"cell_type":"code","source":"from collections import Counter\ndict_in = dict(g.in_degree())\ndict_out = dict(g.out_degree())\nd = Counter(dict_in) + Counter(dict_out)\nin_out_degree = np.array(list(d.values()))","metadata":{"id":"MNu7k3-FX7Kj","execution":{"iopub.status.busy":"2024-01-01T19:52:02.777271Z","iopub.execute_input":"2024-01-01T19:52:02.777570Z","iopub.status.idle":"2024-01-01T19:52:07.018443Z","shell.execute_reply.started":"2024-01-01T19:52:02.777536Z","shell.execute_reply":"2024-01-01T19:52:07.016656Z"},"trusted":true},"execution_count":null,"outputs":[]},{"cell_type":"code","source":"in_out_degree_sort = sorted(in_out_degree)\nplt.figure(figsize=(10,6))\nplt.plot(in_out_degree_sort)\nplt.xlabel('Index No')\nplt.ylabel('No Of people each person is following + followers')\nplt.show()","metadata":{"id":"ARCqfS9TX7Kn","outputId":"44fe1bc9-a591-4cff-89aa-e36c0f7165e5","execution":{"iopub.status.busy":"2024-01-01T19:52:07.019762Z","iopub.execute_input":"2024-01-01T19:52:07.020077Z","iopub.status.idle":"2024-01-01T19:52:08.446575Z","shell.execute_reply.started":"2024-01-01T19:52:07.020041Z","shell.execute_reply":"2024-01-01T19:52:08.445801Z"},"trusted":true},"execution_count":null,"outputs":[]},{"cell_type":"markdown","source":"> Số người theo dõi và số lượt được theo dõi của một người dùng giao động từ 0 - 1600 người. Hầu hết các giá trị nằm trong khoảng 80-100 người.","metadata":{}},{"cell_type":"code","source":"in_out_degree_sort = sorted(in_out_degree)\nplt.figure(figsize=(10,6))\nplt.plot(in_out_degree_sort[0:1500000])\nplt.xlabel('Index No')\nplt.ylabel('No Of people each person is following + followers')\nplt.show()","metadata":{"id":"jVlgsM8hX7Ku","outputId":"28758bec-8303-4a93-f4a9-b637cb14efe0","execution":{"iopub.status.busy":"2024-01-01T19:52:08.447584Z","iopub.execute_input":"2024-01-01T19:52:08.447858Z","iopub.status.idle":"2024-01-01T19:52:09.942000Z","shell.execute_reply.started":"2024-01-01T19:52:08.447832Z","shell.execute_reply":"2024-01-01T19:52:09.940838Z"},"trusted":true},"execution_count":null,"outputs":[]},{"cell_type":"code","source":"### 90-100 percentile\nfor i in range(0,11):\n print(90+i,'percentile value is',np.percentile(in_out_degree_sort,90+i))","metadata":{"id":"4YpW20YEX7Kz","outputId":"ba104e55-fae4-4a81-b2b6-887c804e6c6a","execution":{"iopub.status.busy":"2024-01-01T19:52:09.943213Z","iopub.execute_input":"2024-01-01T19:52:09.943486Z","iopub.status.idle":"2024-01-01T19:52:14.821237Z","shell.execute_reply.started":"2024-01-01T19:52:09.943453Z","shell.execute_reply":"2024-01-01T19:52:14.819865Z"},"trusted":true},"execution_count":null,"outputs":[]},{"cell_type":"markdown","source":"> 99% người dùng có tổng số lượt theo dõi và số lượt được theo dõi là 79 lượt.","metadata":{}},{"cell_type":"code","source":"### 99-100 percentile\nfor i in range(10,110,10):\n print(99+(i/100),'percentile value is',np.percentile(in_out_degree_sort,99+(i/100)))","metadata":{"id":"LclmrhGbX7K3","outputId":"43440486-b332-476b-a769-43e43e23600d","execution":{"iopub.status.busy":"2024-01-01T19:52:14.822750Z","iopub.execute_input":"2024-01-01T19:52:14.823029Z","iopub.status.idle":"2024-01-01T19:52:19.220329Z","shell.execute_reply.started":"2024-01-01T19:52:14.822997Z","shell.execute_reply":"2024-01-01T19:52:19.219339Z"},"trusted":true},"execution_count":null,"outputs":[]},{"cell_type":"markdown","source":"> Con số tổng cộng này tăng lên là 221 lượt với 99.9% người dùng.","metadata":{}},{"cell_type":"code","source":"print('Min of no of followers + following is',in_out_degree.min())\nprint(np.sum(in_out_degree==in_out_degree.min()),' persons having minimum no of followers + following')","metadata":{"id":"XqErF9SRX7K8","outputId":"11746c24-4d22-4466-f2bf-8dae306ee408","execution":{"iopub.status.busy":"2024-01-01T19:52:19.221298Z","iopub.execute_input":"2024-01-01T19:52:19.221529Z","iopub.status.idle":"2024-01-01T19:52:19.232440Z","shell.execute_reply.started":"2024-01-01T19:52:19.221502Z","shell.execute_reply":"2024-01-01T19:52:19.231133Z"},"trusted":true},"execution_count":null,"outputs":[]},{"cell_type":"code","source":"print('Max of no of followers + following is',in_out_degree.max())\nprint(np.sum(in_out_degree==in_out_degree.max()),' persons having maximum no of followers + following')","metadata":{"id":"4rjy0p8-X7LA","outputId":"e3d20325-27e8-44f3-f0ea-18aa395e687c","execution":{"iopub.status.busy":"2024-01-01T19:52:19.233470Z","iopub.execute_input":"2024-01-01T19:52:19.233698Z","iopub.status.idle":"2024-01-01T19:52:19.245691Z","shell.execute_reply.started":"2024-01-01T19:52:19.233665Z","shell.execute_reply":"2024-01-01T19:52:19.244728Z"},"trusted":true},"execution_count":null,"outputs":[]},{"cell_type":"code","source":"print('No of persons having followers + following less than 10 are',np.sum(in_out_degree<10))","metadata":{"id":"2vkQHuVgX7LE","outputId":"c4bd961f-a5a9-45b7-d700-f8f368d6772d","execution":{"iopub.status.busy":"2024-01-01T19:52:19.246916Z","iopub.execute_input":"2024-01-01T19:52:19.247216Z","iopub.status.idle":"2024-01-01T19:52:19.254694Z","shell.execute_reply.started":"2024-01-01T19:52:19.247182Z","shell.execute_reply":"2024-01-01T19:52:19.253775Z"},"trusted":true},"execution_count":null,"outputs":[]},{"cell_type":"code","source":"print('No of weakly connected components',len(list(nx.weakly_connected_components(g))))\ncount=0\nfor i in list(nx.weakly_connected_components(g)):\n if len(i)==2:\n count+=1\nprint('weakly connected components wit 2 nodes',count)","metadata":{"id":"9YXunWI-X7LI","outputId":"00c2e979-fcfc-412f-8a02-26bac9c912ff","execution":{"iopub.status.busy":"2024-01-01T19:52:19.255979Z","iopub.execute_input":"2024-01-01T19:52:19.256334Z","iopub.status.idle":"2024-01-01T19:52:46.788370Z","shell.execute_reply.started":"2024-01-01T19:52:19.256296Z","shell.execute_reply":"2024-01-01T19:52:46.787793Z"},"trusted":true},"execution_count":null,"outputs":[]},{"cell_type":"markdown","source":"> Min của tổng lượt theo dõi và lượt được theo dõi của một người là 1 và số người sở hữu min này là 334291.\n\n> Max của tổng lượt theo dõi và lượt được theo dõi của một người là 1579 và số người sở hữu max này là 1.\n\n> Số người có tổng lượt theo dõi và lượt được theo dõi ít hơn 10 là 1320326 người.\n\n> Số lượng các thành phần liên kết yếu trong mạng là 45558.\n\n> Có 32195 thành phần liên kết yếu với 2 nút.","metadata":{}},{"cell_type":"markdown","source":"# 2. Posing a problem as classification problem ","metadata":{"id":"RiPVIlFUX7LQ"}},{"cell_type":"markdown","source":"## 2.1 Generating some edges which are not present in graph for supervised learning \n\nTạo ra các \"bad links\" là các cạnh không có trong đồ thị và có độ dài đường đi ngắn nhất lớn hơn 2. Số lượng các cạnh bị thiếu được lựa chọn là 9467519 cạnh. \n\nCụ thể hơn, ta đang tạo một từ điển trong đó một cặp nút sẽ là khóa và giá trị sẽ là '1' nếu tồn tại liên kết giữa chúng và '-1' nếu ngược lại.\n\nTa đang chạy vòng lặp while để chọn chính xác 9437519 số cạnh bị thiếu và thêm chúng vào một tập hợp có tên 'missing_edges'.\n\nBây giờ, hãy xem câu lệnh if. Trước tiên, chọn ngẫu nhiên hai nút từ dữ liệu và kiểm tra xem cạnh giữa chúng có xuất hiện trong từ điển mà ta đã tạo hay không và kiểm tra xem hai nút được chọn ngẫu nhiên có phải là cùng một nút hay không (a nút không thể được liên kết với chính nó).\n\nBây giờ, ta kiểm tra xem đường đi ngắn nhất giữa hai nút có lớn hơn hai hay không và nếu có, chúng tôi sẽ thêm chúng vào tập hợp còn thiếu.","metadata":{"id":"TpDCmJroX7LS"}},{"cell_type":"code","source":"%%time\n###generating bad edges from given graph\nimport random\nif not os.path.isfile('missing_edges_final.p'):\n #getting all set of edges\n r = csv.reader(open('/kaggle/working/train_woheader.csv','r'))\n edges = dict()\n for edge in r:\n edges[(edge[0], edge[1])] = 1\n \n \n missing_edges = set([])\n while (len(missing_edges)<9437519):\n a=random.randint(1, 1862220)\n b=random.randint(1, 1862220)\n tmp = edges.get((a,b),-1)\n if tmp == -1 and a!=b:\n try:\n if nx.shortest_path_length(g,source=a,target=b) > 2: \n\n missing_edges.add((a,b))\n else:\n continue \n except: \n missing_edges.add((a,b)) \n else:\n continue\n pickle.dump(missing_edges,open('missing_edges_final.p','wb'))\nelse:\n missing_edges = pickle.load(open('missing_edges_final.p','rb'))","metadata":{"id":"3K2YQD6ZX7LT","outputId":"03656e72-53e4-4239-8227-c0ffe9f535d1","execution":{"iopub.status.busy":"2024-01-01T19:52:46.789299Z","iopub.execute_input":"2024-01-01T19:52:46.789625Z","iopub.status.idle":"2024-01-01T23:34:08.900559Z","shell.execute_reply.started":"2024-01-01T19:52:46.789592Z","shell.execute_reply":"2024-01-01T23:34:08.899420Z"},"trusted":true},"execution_count":null,"outputs":[]},{"cell_type":"code","source":"len(missing_edges)","metadata":{"id":"vrjL2UAmX7LX","outputId":"8596ad2d-6c45-4c14-e377-3c06850b661d","execution":{"iopub.status.busy":"2024-01-01T23:34:08.902060Z","iopub.execute_input":"2024-01-01T23:34:08.902332Z","iopub.status.idle":"2024-01-01T23:34:08.908828Z","shell.execute_reply.started":"2024-01-01T23:34:08.902299Z","shell.execute_reply":"2024-01-01T23:34:08.907802Z"},"trusted":true},"execution_count":null,"outputs":[]},{"cell_type":"markdown","source":"## 2.2 Training and Test data split: \nChia dữ liệu train và test cho bài toán phân loại dựa trên đồ thị. Chia tập dữ liệu train và test đối với cả hai bộ dữ liệu các cạnh âm và dương sau đó nối lần lượt các tập train trên hai bộ dữ liệu và tập test trên hai bộ dữ liệu với nhau . ","metadata":{"id":"LA2GGc3lX7Lb"}},{"cell_type":"code","source":"from sklearn.model_selection import train_test_split\nif (not os.path.isfile('train_pos_after_eda.csv')) and (not os.path.isfile('test_pos_after_eda.csv')):\n #reading total data df\n df_pos = pd.read_csv('/kaggle/input/FacebookRecruiting/train.csv')\n df_neg = pd.DataFrame(list(missing_edges), columns=['source_node', 'destination_node'])\n \n print(\"Number of nodes in the graph with edges\", df_pos.shape[0])\n print(\"Number of nodes in the graph without edges\", df_neg.shape[0])\n \n #Train test split \n #Spiltted data into 80-20 \n #positive links and negative links seperatly because we need positive training data only for creating graph \n #and for feature generation\n X_train_pos, X_test_pos, y_train_pos, y_test_pos = train_test_split(df_pos,np.ones(len(df_pos)),test_size=0.2, random_state=9)\n X_train_neg, X_test_neg, y_train_neg, y_test_neg = train_test_split(df_neg,np.zeros(len(df_neg)),test_size=0.2, random_state=9)\n \n print('='*60)\n print(\"Number of nodes in the train data graph with edges\", X_train_pos.shape[0],\"=\",y_train_pos.shape[0])\n print(\"Number of nodes in the train data graph without edges\", X_train_neg.shape[0],\"=\", y_train_neg.shape[0])\n print('='*60)\n print(\"Number of nodes in the test data graph with edges\", X_test_pos.shape[0],\"=\",y_test_pos.shape[0])\n print(\"Number of nodes in the test data graph without edges\", X_test_neg.shape[0],\"=\",y_test_neg.shape[0])\n\n #removing header and saving\n X_train_pos.to_csv('train_pos_after_eda.csv',header=False, index=False)\n X_test_pos.to_csv('test_pos_after_eda.csv',header=False, index=False)\n X_train_neg.to_csv('train_neg_after_eda.csv',header=False, index=False)\n X_test_neg.to_csv('test_neg_after_eda.csv',header=False, index=False)\nelse:\n #Graph from Traing data only \n del missing_edges","metadata":{"id":"hmcOk-nkX7Lb","outputId":"891d417c-069b-4236-e3ba-35b2bbfc252d","execution":{"iopub.status.busy":"2024-01-01T23:34:08.910208Z","iopub.execute_input":"2024-01-01T23:34:08.910469Z","iopub.status.idle":"2024-01-01T23:34:46.547512Z","shell.execute_reply.started":"2024-01-01T23:34:08.910437Z","shell.execute_reply":"2024-01-01T23:34:46.546069Z"},"trusted":true},"execution_count":null,"outputs":[]},{"cell_type":"markdown","source":"Vì dữ liệu cuối cùng đã được chuẩn bị và lưu trong bốn tệp csv, hãy thử trực quan hóa dữ liệu cuối cùng bằng thư viện networkX và nêu bật một số đặc điểm của nó.","metadata":{}},{"cell_type":"code","source":"if (os.path.isfile('train_pos_after_eda.csv')) and (os.path.isfile('test_pos_after_eda.csv')): \n train_graph=nx.read_edgelist('train_pos_after_eda.csv',delimiter=',',create_using=nx.DiGraph(),nodetype=int)\n test_graph=nx.read_edgelist('test_pos_after_eda.csv',delimiter=',',create_using=nx.DiGraph(),nodetype=int)\n print(nx.info(train_graph))\n print(nx.info(test_graph))\n\n # finding the unique nodes in the both train and test graphs\n train_nodes_pos = set(train_graph.nodes())\n test_nodes_pos = set(test_graph.nodes())\n\n trY_teY = len(train_nodes_pos.intersection(test_nodes_pos))\n trY_teN = len(train_nodes_pos - test_nodes_pos)\n teY_trN = len(test_nodes_pos - train_nodes_pos)\n\n print('no of people common in train and test -- ',trY_teY)\n print('no of people present in train but not present in test -- ',trY_teN)\n\n print('no of people present in test but not present in train -- ',teY_trN)\n print(' % of people not there in Train but exist in Test in total Test data are {} %'.format(teY_trN/len(test_nodes_pos)*100))","metadata":{"id":"Wj9OwIX6X7Lh","outputId":"8a11e605-e133-4b3d-c2d2-585021be9cdc","execution":{"iopub.status.busy":"2024-01-01T23:34:46.549139Z","iopub.execute_input":"2024-01-01T23:34:46.549429Z","iopub.status.idle":"2024-01-01T23:36:24.597148Z","shell.execute_reply.started":"2024-01-01T23:34:46.549397Z","shell.execute_reply":"2024-01-01T23:36:24.595814Z"},"trusted":true},"execution_count":null,"outputs":[]},{"cell_type":"markdown","source":"81000 người có mặt trong tập test nhưng không có trong tập train, đây là một sự cố cold start.\n\nBây giờ, hãy ghép các cạnh dương và âm lại với nhau rồi lưu dữ liệu train và test cuối cùng.","metadata":{"id":"OhpyrSuiX7Ll"}},{"cell_type":"code","source":"#final train and test data sets\nif (not os.path.isfile('train_after_eda.csv')) and \\\n(not os.path.isfile('test_after_eda.csv')) and \\\n(not os.path.isfile('train_y.csv')) and \\\n(not os.path.isfile('test_y.csv')) and \\\n(os.path.isfile('train_pos_after_eda.csv')) and \\\n(os.path.isfile('test_pos_after_eda.csv')) and \\\n(os.path.isfile('train_neg_after_eda.csv')) and \\\n(os.path.isfile('test_neg_after_eda.csv')):\n \n X_train_pos = pd.read_csv('train_pos_after_eda.csv', names=['source_node', 'destination_node'])\n X_test_pos = pd.read_csv('test_pos_after_eda.csv', names=['source_node', 'destination_node'])\n X_train_neg = pd.read_csv('train_neg_after_eda.csv', names=['source_node', 'destination_node'])\n X_test_neg = pd.read_csv('test_neg_after_eda.csv', names=['source_node', 'destination_node'])\n\n print('='*60)\n print(\"Number of nodes in the train data graph with edges\", X_train_pos.shape[0])\n print(\"Number of nodes in the train data graph without edges\", X_train_neg.shape[0])\n print('='*60)\n print(\"Number of nodes in the test data graph with edges\", X_test_pos.shape[0])\n print(\"Number of nodes in the test data graph without edges\", X_test_neg.shape[0])\n\n X_train = X_train_pos.append(X_train_neg,ignore_index=True)\n y_train = np.concatenate((y_train_pos,y_train_neg))\n X_test = X_test_pos.append(X_test_neg,ignore_index=True)\n y_test = np.concatenate((y_test_pos,y_test_neg)) \n \n X_train.to_csv('train_after_eda.csv',header=False,index=False)\n X_test.to_csv('test_after_eda.csv',header=False,index=False)\n pd.DataFrame(y_train.astype(int)).to_csv('train_y.csv',header=False,index=False)\n pd.DataFrame(y_test.astype(int)).to_csv('test_y.csv',header=False,index=False)","metadata":{"id":"onultUqjX7Lm","outputId":"795b2bac-18da-4540-9343-bb69f30a6f00","execution":{"iopub.status.busy":"2024-01-01T23:36:24.742746Z","iopub.execute_input":"2024-01-01T23:36:24.743043Z","iopub.status.idle":"2024-01-01T23:37:02.784046Z","shell.execute_reply.started":"2024-01-01T23:36:24.743017Z","shell.execute_reply":"2024-01-01T23:37:02.782751Z"},"trusted":true},"execution_count":null,"outputs":[]},{"cell_type":"code","source":"print(\"Data points in train data\",X_train.shape)\nprint(\"Data points in test data\",X_test.shape)\nprint(\"Shape of target variable in train\",y_train.shape)\nprint(\"Shape of target variable in test\", y_test.shape)","metadata":{"id":"DB_sXaqZX7Lt","outputId":"6c5b1dcf-a7ff-420d-80fc-84a4fb6566fb","execution":{"iopub.status.busy":"2024-01-01T23:37:02.786409Z","iopub.execute_input":"2024-01-01T23:37:02.786664Z","iopub.status.idle":"2024-01-01T23:37:02.794866Z","shell.execute_reply.started":"2024-01-01T23:37:02.786637Z","shell.execute_reply":"2024-01-01T23:37:02.793801Z"},"trusted":true},"execution_count":null,"outputs":[]},{"cell_type":"markdown","source":"# 1. Reading Data\n\n> Đọc dữ liệu và tạo đồ thị","metadata":{"id":"1znHayNeVFFt"}},{"cell_type":"code","source":"if os.path.isfile('train_pos_after_eda.csv'):\n train_graph=nx.read_edgelist('train_pos_after_eda.csv',delimiter=',',create_using=nx.DiGraph(),nodetype=int)\n print(nx.info(train_graph))\nelse:\n print(\"please run the FB_EDA.ipynb or download the files from drive\")","metadata":{"id":"Uq9HbHwEVFFv","outputId":"b2aa525a-93d3-47c3-8216-416a811bc812","execution":{"iopub.status.busy":"2024-01-01T23:37:02.796048Z","iopub.execute_input":"2024-01-01T23:37:02.796272Z","iopub.status.idle":"2024-01-01T23:38:12.443390Z","shell.execute_reply.started":"2024-01-01T23:37:02.796247Z","shell.execute_reply":"2024-01-01T23:38:12.441742Z"},"trusted":true},"execution_count":null,"outputs":[]},{"cell_type":"markdown","source":"# 2. Similarity measures\n\n> Tạo ra các độ đo tương đồng","metadata":{"id":"HmlUa64tVFF7"}},{"cell_type":"markdown","source":"## 2.1 Jaccard Distance:\nhttp://www.statisticshowto.com/jaccard-index/","metadata":{"id":"ivVMUMiWVFF9"}},{"cell_type":"markdown","source":"\\begin{equation}\nj = \\frac{|X\\cap Y|}{|X \\cup Y|} \n\\end{equation}","metadata":{"id":"NoWCYuRBVFF_"}},{"cell_type":"code","source":"#for followees\ndef jaccard_for_followees(a,b):\n try:\n if len(set(train_graph.successors(a))) == 0 | len(set(train_graph.successors(b))) == 0:\n return 0\n sim = (len(set(train_graph.successors(a)).intersection(set(train_graph.successors(b)))))/\\\n (len(set(train_graph.successors(a)).union(set(train_graph.successors(b)))))\n except:\n return 0\n return sim","metadata":{"id":"Seo4z5SnVFGB","execution":{"iopub.status.busy":"2024-01-01T23:38:12.445392Z","iopub.execute_input":"2024-01-01T23:38:12.445876Z","iopub.status.idle":"2024-01-01T23:38:12.453933Z","shell.execute_reply.started":"2024-01-01T23:38:12.445831Z","shell.execute_reply":"2024-01-01T23:38:12.452491Z"},"trusted":true},"execution_count":null,"outputs":[]},{"cell_type":"code","source":"#one test case\nprint(jaccard_for_followees(273084,1505602))","metadata":{"id":"Oa9FMlS8VFGF","outputId":"426a6833-1631-4024-c24a-d21ae7686472","execution":{"iopub.status.busy":"2024-01-01T23:38:12.455422Z","iopub.execute_input":"2024-01-01T23:38:12.456274Z","iopub.status.idle":"2024-01-01T23:38:12.471080Z","shell.execute_reply.started":"2024-01-01T23:38:12.456198Z","shell.execute_reply":"2024-01-01T23:38:12.470121Z"},"trusted":true},"execution_count":null,"outputs":[]},{"cell_type":"code","source":"#node 1635354 not in graph \nprint(jaccard_for_followees(273084,1505602))","metadata":{"id":"Gf8njOv6VFGK","outputId":"8ba07727-a0ab-498e-819f-0d310876191c","execution":{"iopub.status.busy":"2024-01-01T23:38:12.472093Z","iopub.execute_input":"2024-01-01T23:38:12.472381Z","iopub.status.idle":"2024-01-01T23:38:12.485513Z","shell.execute_reply.started":"2024-01-01T23:38:12.472347Z","shell.execute_reply":"2024-01-01T23:38:12.483884Z"},"trusted":true},"execution_count":null,"outputs":[]},{"cell_type":"code","source":"#for followers\ndef jaccard_for_followers(a,b):\n try:\n if len(set(train_graph.predecessors(a))) == 0 | len(set(g.predecessors(b))) == 0:\n return 0\n sim = (len(set(train_graph.predecessors(a)).intersection(set(train_graph.predecessors(b)))))/\\\n (len(set(train_graph.predecessors(a)).union(set(train_graph.predecessors(b)))))\n return sim\n except:\n return 0","metadata":{"id":"LO-a5ZkKVFGO","execution":{"iopub.status.busy":"2024-01-01T23:38:12.487070Z","iopub.execute_input":"2024-01-01T23:38:12.487325Z","iopub.status.idle":"2024-01-01T23:38:12.496483Z","shell.execute_reply.started":"2024-01-01T23:38:12.487298Z","shell.execute_reply":"2024-01-01T23:38:12.495084Z"},"trusted":true},"execution_count":null,"outputs":[]},{"cell_type":"code","source":"print(jaccard_for_followers(273084,470294))","metadata":{"id":"DlbX2t0jVFGQ","outputId":"7e4b4536-442a-4b0c-ae02-fb442c1955db","execution":{"iopub.status.busy":"2024-01-01T23:38:12.498402Z","iopub.execute_input":"2024-01-01T23:38:12.498810Z","iopub.status.idle":"2024-01-01T23:38:12.510899Z","shell.execute_reply.started":"2024-01-01T23:38:12.498765Z","shell.execute_reply":"2024-01-01T23:38:12.508936Z"},"trusted":true},"execution_count":null,"outputs":[]},{"cell_type":"code","source":"#node 1635354 not in graph \nprint(jaccard_for_followees(669354,1635354))","metadata":{"id":"OgeBW2LMVFGU","outputId":"1e12fabe-d990-4506-bb6b-c86b01d1b0af","execution":{"iopub.status.busy":"2024-01-01T23:38:12.512475Z","iopub.execute_input":"2024-01-01T23:38:12.513308Z","iopub.status.idle":"2024-01-01T23:38:12.524154Z","shell.execute_reply.started":"2024-01-01T23:38:12.513251Z","shell.execute_reply":"2024-01-01T23:38:12.523198Z"},"trusted":true},"execution_count":null,"outputs":[]},{"cell_type":"markdown","source":"## 2.2 Cosine distance","metadata":{"id":"MnH2my2UVFGX"}},{"cell_type":"markdown","source":"\\begin{equation}\nCosineDistance = \\frac{|X\\cap Y|}{|X|\\cdot|Y|} \n\\end{equation}","metadata":{"id":"XNvdBGS2VFGY"}},{"cell_type":"code","source":"#for followees\ndef cosine_for_followees(a,b):\n try:\n if len(set(train_graph.successors(a))) == 0 | len(set(train_graph.successors(b))) == 0:\n return 0\n sim = (len(set(train_graph.successors(a)).intersection(set(train_graph.successors(b)))))/\\\n (math.sqrt(len(set(train_graph.successors(a)))*len((set(train_graph.successors(b))))))\n return sim\n except:\n return 0","metadata":{"id":"Iznz67EdVFGZ","execution":{"iopub.status.busy":"2024-01-01T23:38:12.525504Z","iopub.execute_input":"2024-01-01T23:38:12.525920Z","iopub.status.idle":"2024-01-01T23:38:12.538681Z","shell.execute_reply.started":"2024-01-01T23:38:12.525877Z","shell.execute_reply":"2024-01-01T23:38:12.536875Z"},"trusted":true},"execution_count":null,"outputs":[]},{"cell_type":"code","source":"print(cosine_for_followees(273084,1505602))","metadata":{"id":"H55ALjkMVFGc","outputId":"531fceba-60f4-4e6b-97f4-f37733dc468f","execution":{"iopub.status.busy":"2024-01-01T23:38:12.540686Z","iopub.execute_input":"2024-01-01T23:38:12.541301Z","iopub.status.idle":"2024-01-01T23:38:12.552219Z","shell.execute_reply.started":"2024-01-01T23:38:12.541251Z","shell.execute_reply":"2024-01-01T23:38:12.551306Z"},"trusted":true},"execution_count":null,"outputs":[]},{"cell_type":"code","source":"print(cosine_for_followees(273084,1635354))","metadata":{"id":"q0RGKgJFVFGf","outputId":"41202fc6-f4aa-4a1d-d8f6-84f960a3fbba","execution":{"iopub.status.busy":"2024-01-01T23:38:12.553867Z","iopub.execute_input":"2024-01-01T23:38:12.554696Z","iopub.status.idle":"2024-01-01T23:38:12.566658Z","shell.execute_reply.started":"2024-01-01T23:38:12.554653Z","shell.execute_reply":"2024-01-01T23:38:12.565491Z"},"trusted":true},"execution_count":null,"outputs":[]},{"cell_type":"code","source":"def cosine_for_followers(a,b):\n try:\n \n if len(set(train_graph.predecessors(a))) == 0 | len(set(train_graph.predecessors(b))) == 0:\n return 0\n sim = (len(set(train_graph.predecessors(a)).intersection(set(train_graph.predecessors(b)))))/\\\n (math.sqrt(len(set(train_graph.predecessors(a))))*(len(set(train_graph.predecessors(b)))))\n return sim\n except:\n return 0","metadata":{"id":"KJ_yGxA0VFGj","execution":{"iopub.status.busy":"2024-01-01T23:38:12.568102Z","iopub.execute_input":"2024-01-01T23:38:12.568460Z","iopub.status.idle":"2024-01-01T23:38:12.578286Z","shell.execute_reply.started":"2024-01-01T23:38:12.568418Z","shell.execute_reply":"2024-01-01T23:38:12.577045Z"},"trusted":true},"execution_count":null,"outputs":[]},{"cell_type":"code","source":"print(cosine_for_followers(2,470294))","metadata":{"id":"75QrFJb6VFGm","outputId":"f01e0558-f1e3-465f-ab14-0e4ca764f4aa","execution":{"iopub.status.busy":"2024-01-01T23:38:12.579669Z","iopub.execute_input":"2024-01-01T23:38:12.580104Z","iopub.status.idle":"2024-01-01T23:38:12.595775Z","shell.execute_reply.started":"2024-01-01T23:38:12.580066Z","shell.execute_reply":"2024-01-01T23:38:12.594865Z"},"trusted":true},"execution_count":null,"outputs":[]},{"cell_type":"code","source":"print(cosine_for_followers(669354,1635354))","metadata":{"id":"-ut4k_F0VFGq","outputId":"8bc9607a-7262-43e2-9de8-f71d276762fc","execution":{"iopub.status.busy":"2024-01-01T23:38:12.597161Z","iopub.execute_input":"2024-01-01T23:38:12.598007Z","iopub.status.idle":"2024-01-01T23:38:12.606650Z","shell.execute_reply.started":"2024-01-01T23:38:12.597592Z","shell.execute_reply":"2024-01-01T23:38:12.605105Z"},"trusted":true},"execution_count":null,"outputs":[]},{"cell_type":"markdown","source":"## 3. Ranking Measures","metadata":{"id":"DaIHhWh6VFGv"}},{"cell_type":"markdown","source":"https://networkx.github.io/documentation/networkx-1.10/reference/generated/networkx.algorithms.link_analysis.pagerank_alg.pagerank.html\n\nPageRank computes a ranking of the nodes in the graph G based on the structure of the incoming links.\n\n\nMathematical PageRanks for a simple network, expressed as percentages. (Google uses a logarithmic scale.) Page C has a higher PageRank than Page E, even though there are fewer links to C; the one link to C comes from an important page and hence is of high value. If web surfers who start on a random page have an 85% likelihood of choosing a random link from the page they are currently visiting, and a 15% likelihood of jumping to a page chosen at random from the entire web, they will reach Page E 8.1% of the time. (The 15% likelihood of jumping to an arbitrary page corresponds to a damping factor of 85%.) Without damping, all web surfers would eventually end up on Pages A, B, or C, and all other pages would have PageRank zero. In the presence of damping, Page A effectively links to all pages in the web, even though it has no outgoing links of its own.","metadata":{"id":"6nfV1SprVFGx"}},{"cell_type":"code","source":"new_dir_path = '/kaggle/working/fea_sample'\n\nos.mkdir(new_dir_path)","metadata":{"execution":{"iopub.status.busy":"2024-01-01T23:38:12.608560Z","iopub.execute_input":"2024-01-01T23:38:12.608911Z","iopub.status.idle":"2024-01-01T23:38:12.617009Z","shell.execute_reply.started":"2024-01-01T23:38:12.608877Z","shell.execute_reply":"2024-01-01T23:38:12.615626Z"},"trusted":true},"execution_count":null,"outputs":[]},{"cell_type":"markdown","source":"## 3.1 Page Ranking\n\nhttps://en.wikipedia.org/wiki/PageRank\n","metadata":{"id":"GkkfYYZ6VFGy"}},{"cell_type":"code","source":"if not os.path.isfile('/kaggle/working/fea_sample/page_rank.p'):\n pr = nx.pagerank(train_graph, alpha=0.85)\n pickle.dump(pr,open('/kaggle/working/fea_sample/page_rank.p','wb'))\nelse:\n pr = pickle.load(open('/kaggle/working/fea_sample/page_rank.p','rb'))","metadata":{"id":"AtvqwZ34VFGy","execution":{"iopub.status.busy":"2024-01-01T23:38:12.619971Z","iopub.execute_input":"2024-01-01T23:38:12.620491Z","iopub.status.idle":"2024-01-01T23:39:58.101154Z","shell.execute_reply.started":"2024-01-01T23:38:12.620447Z","shell.execute_reply":"2024-01-01T23:39:58.099198Z"},"trusted":true},"execution_count":null,"outputs":[]},{"cell_type":"code","source":"print('min',pr[min(pr, key=pr.get)])\nprint('max',pr[max(pr, key=pr.get)])\nprint('mean',float(sum(pr.values())) / len(pr))","metadata":{"id":"lXGKYYf6VFG2","outputId":"bb3d1b7a-81f9-44ab-dbe7-3214ccd47179","execution":{"iopub.status.busy":"2024-01-01T23:39:58.103200Z","iopub.execute_input":"2024-01-01T23:39:58.103539Z","iopub.status.idle":"2024-01-01T23:39:59.909486Z","shell.execute_reply.started":"2024-01-01T23:39:58.103503Z","shell.execute_reply":"2024-01-01T23:39:59.908011Z"},"trusted":true},"execution_count":null,"outputs":[]},{"cell_type":"code","source":"#for imputing to nodes which are not there in Train data\nmean_pr = float(sum(pr.values())) / len(pr)\nprint(mean_pr)","metadata":{"id":"5xwlah4oVFG4","outputId":"992fdfad-7ff6-4626-c9ee-d9bce220a680","execution":{"iopub.status.busy":"2024-01-01T23:39:59.910431Z","iopub.execute_input":"2024-01-01T23:39:59.910706Z","iopub.status.idle":"2024-01-01T23:40:00.011495Z","shell.execute_reply.started":"2024-01-01T23:39:59.910677Z","shell.execute_reply":"2024-01-01T23:40:00.009622Z"},"trusted":true},"execution_count":null,"outputs":[]},{"cell_type":"markdown","source":"# 4. Other Graph Features\n\n> Tạo các đặc trưng khác cho đồ thị","metadata":{"id":"HhPbSL1tVFG7"}},{"cell_type":"markdown","source":"## 4.1 Shortest path:","metadata":{"id":"AgsorCl7VFG8"}},{"cell_type":"markdown","source":"Lấy đường đi ngắn nhất giữa hai nút, nếu các nút được nối trực tiếp thì ta sẽ loại bỏ cạnh đó và tính toán đường đi.","metadata":{"id":"E7teH2LCVFG9"}},{"cell_type":"code","source":"#if has direct edge then deleting that edge and calculating shortest path\ndef compute_shortest_path_length(a,b):\n p=-1\n try:\n if train_graph.has_edge(a,b):\n train_graph.remove_edge(a,b)\n p= nx.shortest_path_length(train_graph,source=a,target=b)\n train_graph.add_edge(a,b)\n else:\n p= nx.shortest_path_length(train_graph,source=a,target=b)\n return p\n except:\n return -1","metadata":{"id":"RA076ovzVFG9","execution":{"iopub.status.busy":"2024-01-01T23:40:00.013475Z","iopub.execute_input":"2024-01-01T23:40:00.013892Z","iopub.status.idle":"2024-01-01T23:40:00.028990Z","shell.execute_reply.started":"2024-01-01T23:40:00.013843Z","shell.execute_reply":"2024-01-01T23:40:00.026861Z"},"trusted":true},"execution_count":null,"outputs":[]},{"cell_type":"code","source":"#testing\ncompute_shortest_path_length(77697, 826021)","metadata":{"id":"AxnKId11VFG_","outputId":"15ca223a-6a04-4549-d010-54619b472a9e","execution":{"iopub.status.busy":"2024-01-01T23:40:00.032925Z","iopub.execute_input":"2024-01-01T23:40:00.033261Z","iopub.status.idle":"2024-01-01T23:40:00.051603Z","shell.execute_reply.started":"2024-01-01T23:40:00.033226Z","shell.execute_reply":"2024-01-01T23:40:00.049973Z"},"trusted":true},"execution_count":null,"outputs":[]},{"cell_type":"code","source":"#testing\ncompute_shortest_path_length(669354,1635354)","metadata":{"id":"0huWCNtRVFHC","outputId":"6debfa4f-2067-48bc-84b3-ab86e2d9dea6","execution":{"iopub.status.busy":"2024-01-01T23:40:00.053310Z","iopub.execute_input":"2024-01-01T23:40:00.053652Z","iopub.status.idle":"2024-01-01T23:40:00.066842Z","shell.execute_reply.started":"2024-01-01T23:40:00.053618Z","shell.execute_reply":"2024-01-01T23:40:00.065400Z"},"trusted":true},"execution_count":null,"outputs":[]},{"cell_type":"markdown","source":"## 4.2 Checking for same community\n\n> Kiểm tra liệu hai nút có thuộc cùng một cộng đồng hay không?","metadata":{"id":"baE_95bzVFHF"}},{"cell_type":"code","source":"#getting weekly connected edges from graph \nwcc=list(nx.weakly_connected_components(train_graph))\ndef belongs_to_same_wcc(a,b):\n index = []\n if train_graph.has_edge(b,a):\n return 1\n if train_graph.has_edge(a,b):\n for i in wcc:\n if a in i:\n index= i\n break\n if (b in index):\n train_graph.remove_edge(a,b)\n if compute_shortest_path_length(a,b)==-1:\n train_graph.add_edge(a,b)\n return 0\n else:\n train_graph.add_edge(a,b)\n return 1\n else:\n return 0\n else:\n for i in wcc:\n if a in i:\n index= i\n break\n if(b in index):\n return 1\n else:\n return 0","metadata":{"id":"15CIQqAbVFHG","execution":{"iopub.status.busy":"2024-01-01T23:40:00.068517Z","iopub.execute_input":"2024-01-01T23:40:00.069185Z","iopub.status.idle":"2024-01-01T23:40:14.366595Z","shell.execute_reply.started":"2024-01-01T23:40:00.069137Z","shell.execute_reply":"2024-01-01T23:40:14.365256Z"},"trusted":true},"execution_count":null,"outputs":[]},{"cell_type":"code","source":"belongs_to_same_wcc(861, 1659750)","metadata":{"id":"fAzOHtCFVFHI","outputId":"2b043a87-b460-42bf-f37e-4c04bbed6586","execution":{"iopub.status.busy":"2024-01-01T23:40:14.367731Z","iopub.execute_input":"2024-01-01T23:40:14.367988Z","iopub.status.idle":"2024-01-01T23:40:14.379591Z","shell.execute_reply.started":"2024-01-01T23:40:14.367961Z","shell.execute_reply":"2024-01-01T23:40:14.377920Z"},"trusted":true},"execution_count":null,"outputs":[]},{"cell_type":"code","source":"belongs_to_same_wcc(669354,1635354)","metadata":{"id":"HMdYpPuGVFHK","outputId":"2005e22c-b60f-48d7-839b-650bf97cae35","execution":{"iopub.status.busy":"2024-01-01T23:40:14.381647Z","iopub.execute_input":"2024-01-01T23:40:14.382252Z","iopub.status.idle":"2024-01-01T23:40:14.397110Z","shell.execute_reply.started":"2024-01-01T23:40:14.382203Z","shell.execute_reply":"2024-01-01T23:40:14.396028Z"},"trusted":true},"execution_count":null,"outputs":[]},{"cell_type":"markdown","source":"## 4.3 Adamic/Adar Index:\nAdamic/Adar measures is defined as inverted sum of degrees of common neighbours for given two vertices.\n$$A(x,y)=\\sum_{u \\in N(x) \\cap N(y)}\\frac{1}{log(|N(u)|)}$$","metadata":{"id":"q74nth0OVFHN"}},{"cell_type":"code","source":"#adar index\ndef calc_adar_in(a,b):\n sum=0\n try:\n n=list(set(train_graph.successors(a)).intersection(set(train_graph.successors(b))))\n if len(n)!=0:\n for i in n:\n sum=sum+(1/np.log10(len(list(train_graph.predecessors(i)))))\n return sum\n else:\n return 0\n except:\n return 0","metadata":{"id":"CeS98LI5VFHO","execution":{"iopub.status.busy":"2024-01-01T23:40:14.398371Z","iopub.execute_input":"2024-01-01T23:40:14.398690Z","iopub.status.idle":"2024-01-01T23:40:14.409255Z","shell.execute_reply.started":"2024-01-01T23:40:14.398659Z","shell.execute_reply":"2024-01-01T23:40:14.407840Z"},"trusted":true},"execution_count":null,"outputs":[]},{"cell_type":"code","source":"calc_adar_in(1,189226)","metadata":{"id":"KezFeRmyVFHQ","outputId":"2f9c0e11-02d9-4f28-d67a-65e3d4943e99","execution":{"iopub.status.busy":"2024-01-01T23:40:14.410607Z","iopub.execute_input":"2024-01-01T23:40:14.410961Z","iopub.status.idle":"2024-01-01T23:40:14.425066Z","shell.execute_reply.started":"2024-01-01T23:40:14.410929Z","shell.execute_reply":"2024-01-01T23:40:14.423910Z"},"trusted":true},"execution_count":null,"outputs":[]},{"cell_type":"code","source":"calc_adar_in(669354,1635354)","metadata":{"id":"vj_m89bBVFHV","outputId":"68a0a099-2954-402f-c80f-6d436ffa1aba","execution":{"iopub.status.busy":"2024-01-01T23:40:14.426639Z","iopub.execute_input":"2024-01-01T23:40:14.427301Z","iopub.status.idle":"2024-01-01T23:40:14.437953Z","shell.execute_reply.started":"2024-01-01T23:40:14.427257Z","shell.execute_reply":"2024-01-01T23:40:14.436462Z"},"trusted":true},"execution_count":null,"outputs":[]},{"cell_type":"markdown","source":"## 4.4 Is person was following back:\n\n> Kiểm tra hai người dùng có theo dõi lẫn nhau không?","metadata":{"id":"pBUudhFAVFHY"}},{"cell_type":"code","source":"def follows_back(a,b):\n if train_graph.has_edge(b,a):\n return 1\n else:\n return 0","metadata":{"id":"j_mwmopLVFHZ","execution":{"iopub.status.busy":"2024-01-01T23:40:14.439228Z","iopub.execute_input":"2024-01-01T23:40:14.439516Z","iopub.status.idle":"2024-01-01T23:40:14.447816Z","shell.execute_reply.started":"2024-01-01T23:40:14.439486Z","shell.execute_reply":"2024-01-01T23:40:14.446830Z"},"trusted":true},"execution_count":null,"outputs":[]},{"cell_type":"code","source":"follows_back(1,189226)","metadata":{"id":"LdjUXIfbVFHb","outputId":"ed3d8640-9834-4a95-e712-804292da70e9","execution":{"iopub.status.busy":"2024-01-01T23:40:14.449067Z","iopub.execute_input":"2024-01-01T23:40:14.449549Z","iopub.status.idle":"2024-01-01T23:40:14.463588Z","shell.execute_reply.started":"2024-01-01T23:40:14.449509Z","shell.execute_reply":"2024-01-01T23:40:14.462843Z"},"trusted":true},"execution_count":null,"outputs":[]},{"cell_type":"code","source":"follows_back(669354,1635354)","metadata":{"id":"PmZtL65YVFHf","outputId":"18ea6fe2-3f96-42c0-d116-ecb76ddba4b5","execution":{"iopub.status.busy":"2024-01-01T23:40:14.464544Z","iopub.execute_input":"2024-01-01T23:40:14.464968Z","iopub.status.idle":"2024-01-01T23:40:14.480048Z","shell.execute_reply.started":"2024-01-01T23:40:14.464940Z","shell.execute_reply":"2024-01-01T23:40:14.479209Z"},"trusted":true},"execution_count":null,"outputs":[]},{"cell_type":"markdown","source":"## 4.5 Katz Centrality:\nhttps://en.wikipedia.org/wiki/Katz_centrality\n\nhttps://www.geeksforgeeks.org/katz-centrality-centrality-measure/\n Katz centrality computes the centrality for a node \n based on the centrality of its neighbors. It is a \n generalization of the eigenvector centrality. The\n Katz centrality for node `i` is\n \n$$x_i = \\alpha \\sum_{j} A_{ij} x_j + \\beta,$$\nwhere `A` is the adjacency matrix of the graph G \nwith eigenvalues $$\\lambda$$.\n\nThe parameter $$\\beta$$ controls the initial centrality and \n\n$$\\alpha < \\frac{1}{\\lambda_{max}}.$$","metadata":{"id":"29Vrq2EXVFHi"}},{"cell_type":"code","source":"if not os.path.isfile('/kaggle/working/fea_sample/katz.p'):\n katz = nx.katz.katz_centrality(train_graph,alpha=0.005,beta=1)\n pickle.dump(katz,open('/kaggle/working/fea_sample/katz.p','wb'))\nelse:\n katz = pickle.load(open('/kaggle/working/fea_sample/katz.p','rb'))","metadata":{"id":"CN5OSqrkVFHj","execution":{"iopub.status.busy":"2024-01-01T23:40:14.481224Z","iopub.execute_input":"2024-01-01T23:40:14.481556Z","iopub.status.idle":"2024-01-01T23:45:36.126547Z","shell.execute_reply.started":"2024-01-01T23:40:14.481516Z","shell.execute_reply":"2024-01-01T23:45:36.125140Z"},"trusted":true},"execution_count":null,"outputs":[]},{"cell_type":"code","source":"print('min',katz[min(katz, key=katz.get)])\nprint('max',katz[max(katz, key=katz.get)])\nprint('mean',float(sum(katz.values())) / len(katz))","metadata":{"id":"gcU83vw7VFHm","outputId":"05f49ad4-46fe-4cf6-f32a-2fe4846b0714","execution":{"iopub.status.busy":"2024-01-01T23:45:36.128346Z","iopub.execute_input":"2024-01-01T23:45:36.128750Z","iopub.status.idle":"2024-01-01T23:45:37.791899Z","shell.execute_reply.started":"2024-01-01T23:45:36.128678Z","shell.execute_reply":"2024-01-01T23:45:37.790528Z"},"trusted":true},"execution_count":null,"outputs":[]},{"cell_type":"code","source":"mean_katz = float(sum(katz.values())) / len(katz)\nprint(mean_katz)","metadata":{"id":"qcboIksiVFHt","outputId":"99f52422-9edb-479a-d5d9-e33401160da7","execution":{"iopub.status.busy":"2024-01-01T23:45:37.793206Z","iopub.execute_input":"2024-01-01T23:45:37.793474Z","iopub.status.idle":"2024-01-01T23:45:37.877591Z","shell.execute_reply.started":"2024-01-01T23:45:37.793446Z","shell.execute_reply":"2024-01-01T23:45:37.876739Z"},"trusted":true},"execution_count":null,"outputs":[]},{"cell_type":"markdown","source":"## 4.6 Hits Score\nThe HITS algorithm computes two numbers for a node. Authorities estimates the node value based on the incoming links. Hubs estimates the node value based on outgoing links.\n\nhttps://en.wikipedia.org/wiki/HITS_algorithm","metadata":{"id":"SRZqGFgYVFHx"}},{"cell_type":"code","source":"if not os.path.isfile('/kaggle/working/fea_sample/hits.p'):\n hits = nx.hits(train_graph, max_iter=100, tol=1e-08, nstart=None, normalized=True)\n pickle.dump(hits,open('/kaggle/working/fea_sample/hits.p','wb'))\nelse:\n hits = pickle.load(open('/kaggle/working/fea_sample/hits.p','rb'))","metadata":{"id":"WXNHRdzUVFHz","execution":{"iopub.status.busy":"2024-01-01T23:45:37.879138Z","iopub.execute_input":"2024-01-01T23:45:37.879478Z","iopub.status.idle":"2024-01-02T01:06:18.174109Z","shell.execute_reply.started":"2024-01-01T23:45:37.879445Z","shell.execute_reply":"2024-01-02T01:06:18.172926Z"},"trusted":true},"execution_count":null,"outputs":[]},{"cell_type":"code","source":"print('min',hits[0][min(hits[0], key=hits[0].get)])\nprint('max',hits[0][max(hits[0], key=hits[0].get)])\nprint('mean',float(sum(hits[0].values())) / len(hits[0]))","metadata":{"id":"PSUwSZBVVFH3","outputId":"77448253-5409-4229-f0be-b8dbc14d7f46","execution":{"iopub.status.busy":"2024-01-02T01:06:18.175457Z","iopub.execute_input":"2024-01-02T01:06:18.175743Z","iopub.status.idle":"2024-01-02T01:06:19.219660Z","shell.execute_reply.started":"2024-01-02T01:06:18.175695Z","shell.execute_reply":"2024-01-02T01:06:19.218749Z"},"trusted":true},"execution_count":null,"outputs":[]},{"cell_type":"markdown","source":"# 5. Featurization","metadata":{"id":"ZZtowOLZVFH6"}},{"cell_type":"markdown","source":"## 5. 1 Reading a sample of Data from both train and test","metadata":{"id":"o6NnRWmLVFH6"}},{"cell_type":"markdown","source":"> Đọc mẫu dữ liệu từ cả tập train và test tức là làm việc với một tập hợp con dữ liệu để phân tích hoặc xử lý. Mục đích: đọc một cách hiệu quả một mẫu bản ghi ngẫu nhiên từ một tệp lớn mà không cần phải đọc toàn bộ tệp. Bây giờ, chúng ta sẽ tạo một mẫu gồm 100000 điểm để train và một mẫu 50000 để test.\n\n","metadata":{}},{"cell_type":"code","source":"import random\nif os.path.isfile('train_after_eda.csv'):\n filename = \"train_after_eda.csv\"\n # you uncomment this line, if you dont know the lentgh of the file name\n # here we have hardcoded the number of lines as 15100030\n # n_train = sum(1 for line in open(filename)) #number of records in file (excludes header)\n n_train = 15100028\n s = 100000 #desired sample size\n skip_train = sorted(random.sample(range(1,n_train+1),n_train-s))\n #https://stackoverflow.com/a/22259008/4084039","metadata":{"id":"wgHje1UVVFH8","execution":{"iopub.status.busy":"2024-01-02T01:06:19.220887Z","iopub.execute_input":"2024-01-02T01:06:19.221207Z","iopub.status.idle":"2024-01-02T01:06:50.786507Z","shell.execute_reply.started":"2024-01-02T01:06:19.221174Z","shell.execute_reply":"2024-01-02T01:06:50.785300Z"},"trusted":true},"execution_count":null,"outputs":[]},{"cell_type":"code","source":"if os.path.isfile('train_after_eda.csv'):\n filename = \"test_after_eda.csv\"\n # you uncomment this line, if you dont know the lentgh of the file name\n # here we have hardcoded the number of lines as 3775008\n # n_test = sum(1 for line in open(filename)) #number of records in file (excludes header)\n n_test = 3775006\n s = 50000 #desired sample size\n skip_test = sorted(random.sample(range(1,n_test+1),n_test-s))\n #https://stackoverflow.com/a/22259008/4084039","metadata":{"id":"zOzuRFFlVFH-","execution":{"iopub.status.busy":"2024-01-02T01:06:50.787572Z","iopub.execute_input":"2024-01-02T01:06:50.787854Z","iopub.status.idle":"2024-01-02T01:06:57.450661Z","shell.execute_reply.started":"2024-01-02T01:06:50.787819Z","shell.execute_reply":"2024-01-02T01:06:57.449783Z"},"trusted":true},"execution_count":null,"outputs":[]},{"cell_type":"code","source":"print(\"Number of rows in the train data file:\", n_train)\nprint(\"Number of rows we are going to elimiate in train data are\",len(skip_train))\nprint(\"Number of rows in the test data file:\", n_test)\nprint(\"Number of rows we are going to elimiate in test data are\",len(skip_test))","metadata":{"id":"3D_SeUCOVFH_","outputId":"322902a4-0420-4b99-8606-5fd0de4bbea4","execution":{"iopub.status.busy":"2024-01-02T01:06:57.454341Z","iopub.execute_input":"2024-01-02T01:06:57.454972Z","iopub.status.idle":"2024-01-02T01:06:57.462249Z","shell.execute_reply.started":"2024-01-02T01:06:57.454925Z","shell.execute_reply":"2024-01-02T01:06:57.460868Z"},"trusted":true},"execution_count":null,"outputs":[]},{"cell_type":"code","source":"df_final_train = pd.read_csv('train_after_eda.csv', skiprows=skip_train, names=['source_node', 'destination_node'])\ndf_final_train['indicator_link'] = pd.read_csv('train_y.csv', skiprows=skip_train, names=['indicator_link'])\nprint(\"Our train matrix size \",df_final_train.shape)\ndf_final_train.head(2)","metadata":{"id":"pCisf6PpVFID","outputId":"daf2af43-3f98-4466-ad99-03bc54464714","execution":{"iopub.status.busy":"2024-01-02T01:06:57.463625Z","iopub.execute_input":"2024-01-02T01:06:57.463957Z","iopub.status.idle":"2024-01-02T01:07:02.822138Z","shell.execute_reply.started":"2024-01-02T01:06:57.463924Z","shell.execute_reply":"2024-01-02T01:07:02.821046Z"},"trusted":true},"execution_count":null,"outputs":[]},{"cell_type":"code","source":"df_final_test = pd.read_csv('test_after_eda.csv', skiprows=skip_test, names=['source_node', 'destination_node'])\ndf_final_test['indicator_link'] = pd.read_csv('test_y.csv', skiprows=skip_test, names=['indicator_link'])\nprint(\"Our test matrix size \",df_final_test.shape)\ndf_final_test.head(2)","metadata":{"id":"tFn1RkdyVFIH","outputId":"1ca99e70-6d2a-45f2-f51c-fd3b1211ad20","execution":{"iopub.status.busy":"2024-01-02T01:07:02.823555Z","iopub.execute_input":"2024-01-02T01:07:02.823872Z","iopub.status.idle":"2024-01-02T01:07:03.696266Z","shell.execute_reply.started":"2024-01-02T01:07:02.823838Z","shell.execute_reply":"2024-01-02T01:07:03.695050Z"},"trusted":true},"execution_count":null,"outputs":[]},{"cell_type":"markdown","source":"## 5.2 Adding a set of features\n\n**Chúng ta sẽ tính toán các đặc trưng trên các điểm dữ liệu cho cả hai tập train và test**\nSocial network Graph Link Prediction - Facebook Challenge
","metadata":{}},{"cell_type":"code","source":"#Importing Libraries\n# please do go through this python notebook: \nimport warnings\nwarnings.filterwarnings(\"ignore\")\n\nimport csv\nimport pandas as pd#pandas to create small dataframes \nimport datetime #Convert to unix time\nimport time #Convert to unix time\n# if numpy is not installed already : pip3 install numpy\nimport numpy as np#Do aritmetic operations on arrays\n# matplotlib: used to plot graphs\nimport matplotlib\nimport matplotlib.pylab as plt\nimport seaborn as sns#Plots\nfrom matplotlib import rcParams#Size of plots \nfrom sklearn.cluster import MiniBatchKMeans, KMeans#Clustering\nimport math\nimport pickle\nimport os\n# to install xgboost: pip3 install xgboost\nimport xgboost as xgb\n\nimport warnings\nimport networkx as nx\nimport pdb\nimport pickle\nfrom pandas import HDFStore,DataFrame\nfrom pandas import read_hdf\nfrom scipy.sparse.linalg import svds, eigs\nimport gc\nfrom tqdm import tqdm\nfrom sklearn.ensemble import RandomForestClassifier\nfrom sklearn.metrics import f1_score","metadata":{"id":"9wb9N5RzHglP","execution":{"iopub.status.busy":"2024-01-02T01:14:52.887663Z","iopub.execute_input":"2024-01-02T01:14:52.888005Z","iopub.status.idle":"2024-01-02T01:14:52.929695Z","shell.execute_reply.started":"2024-01-02T01:14:52.887971Z","shell.execute_reply":"2024-01-02T01:14:52.928045Z"},"trusted":true},"execution_count":null,"outputs":[]},{"cell_type":"code","source":"#from google.colab import drive\n#drive.mount('/content/drive')","metadata":{"id":"exef2FfoqT3E","outputId":"a85c973c-d3fb-4747-f674-e0cbaeae3faf","execution":{"iopub.status.busy":"2024-01-02T01:14:52.931183Z","iopub.execute_input":"2024-01-02T01:14:52.931699Z","iopub.status.idle":"2024-01-02T01:14:52.935819Z","shell.execute_reply.started":"2024-01-02T01:14:52.931655Z","shell.execute_reply":"2024-01-02T01:14:52.934845Z"},"trusted":true},"execution_count":null,"outputs":[]},{"cell_type":"markdown","source":"# Xây dựng mô hình 1\n\nBây giờ, ta đã ánh xạ vấn đề này thành một vấn đề phân loại lớp nhị phân và chuẩn bị một số đặc trưng cho dữ liệu của mình, ta có thể tiến hành huấn luyện mô hình học máy của mình bằng cách sử dụng mô hình RandomForestClassifier .\n\nTa tiến hành lưu trữ biến mục tiêu (indicator_link) trong một biến riêng cho cả dữ liệu train và dữ liệu test để sau này ta có thể so sánh kết quả thực tế và kết quả dự đoán nhằm đánh giá mô hình của mình.","metadata":{}},{"cell_type":"code","source":"#reading\nfrom pandas import read_hdf\ndf_final_train = read_hdf('/kaggle/working/fea_sample/storage_sample_stage4.h5', 'train_df',mode='r')\ndf_final_test = read_hdf('/kaggle/working/fea_sample/storage_sample_stage4.h5', 'test_df',mode='r')","metadata":{"id":"XC4OJFKkHglU","execution":{"iopub.status.busy":"2024-01-02T01:14:52.937306Z","iopub.execute_input":"2024-01-02T01:14:52.937540Z","iopub.status.idle":"2024-01-02T01:14:53.447649Z","shell.execute_reply.started":"2024-01-02T01:14:52.937514Z","shell.execute_reply":"2024-01-02T01:14:53.445965Z"},"trusted":true},"execution_count":null,"outputs":[]},{"cell_type":"code","source":"df_final_train.columns","metadata":{"id":"5Gm-BHRkHglW","outputId":"fc59a58e-49e3-4bb1-83bf-ee484030c342","execution":{"iopub.status.busy":"2024-01-02T01:14:53.449384Z","iopub.execute_input":"2024-01-02T01:14:53.449798Z","iopub.status.idle":"2024-01-02T01:14:53.458154Z","shell.execute_reply.started":"2024-01-02T01:14:53.449751Z","shell.execute_reply":"2024-01-02T01:14:53.456348Z"},"trusted":true},"execution_count":null,"outputs":[]},{"cell_type":"code","source":"y_train = df_final_train.indicator_link\ny_test = df_final_test.indicator_link","metadata":{"id":"XRW7VZ4AHglc","execution":{"iopub.status.busy":"2024-01-02T01:14:53.459740Z","iopub.execute_input":"2024-01-02T01:14:53.460092Z","iopub.status.idle":"2024-01-02T01:14:53.484395Z","shell.execute_reply.started":"2024-01-02T01:14:53.460054Z","shell.execute_reply":"2024-01-02T01:14:53.483049Z"},"trusted":true},"execution_count":null,"outputs":[]},{"cell_type":"code","source":"df_final_train.drop(['source_node', 'destination_node','indicator_link'],axis=1,inplace=True)\ndf_final_test.drop(['source_node', 'destination_node','indicator_link'],axis=1,inplace=True)","metadata":{"id":"4lj9M_qtHglf","execution":{"iopub.status.busy":"2024-01-02T01:14:53.485704Z","iopub.execute_input":"2024-01-02T01:14:53.486061Z","iopub.status.idle":"2024-01-02T01:14:53.527169Z","shell.execute_reply.started":"2024-01-02T01:14:53.486026Z","shell.execute_reply":"2024-01-02T01:14:53.525686Z"},"trusted":true},"execution_count":null,"outputs":[]},{"cell_type":"code","source":"estimators = [10,50,100,250,450]\ntrain_scores = []\ntest_scores = []\nfor i in estimators:\n clf = RandomForestClassifier(bootstrap=True, class_weight=None, criterion='gini',\n max_depth=5, max_features='auto', max_leaf_nodes=None,\n min_impurity_decrease=0.0, min_impurity_split=None,\n min_samples_leaf=52, min_samples_split=120,\n min_weight_fraction_leaf=0.0, n_estimators=i, n_jobs=-1,random_state=25,verbose=0,warm_start=False)\n clf.fit(df_final_train,y_train)\n train_sc = f1_score(y_train,clf.predict(df_final_train))\n test_sc = f1_score(y_test,clf.predict(df_final_test))\n test_scores.append(test_sc)\n train_scores.append(train_sc)\n print('Estimators = ',i,'Train Score',train_sc,'test Score',test_sc)\nplt.plot(estimators,train_scores,label='Train Score')\nplt.plot(estimators,test_scores,label='Test Score')\nplt.xlabel('Estimators')\nplt.ylabel('Score')\nplt.title('Estimators vs score at depth of 5')","metadata":{"id":"lIEc91uVHgli","outputId":"d0441b63-7256-437a-eb13-db90a727aa31","execution":{"iopub.status.busy":"2024-01-02T01:14:53.528396Z","iopub.execute_input":"2024-01-02T01:14:53.528678Z","iopub.status.idle":"2024-01-02T01:15:43.122182Z","shell.execute_reply.started":"2024-01-02T01:14:53.528647Z","shell.execute_reply":"2024-01-02T01:15:43.121073Z"},"trusted":true},"execution_count":null,"outputs":[]},{"cell_type":"code","source":"depths = [3,9,11,15,20,35,50,70,130]\ntrain_scores = []\ntest_scores = []\nfor i in depths:\n clf = RandomForestClassifier(bootstrap=True, class_weight=None, criterion='gini',\n max_depth=i, max_features='auto', max_leaf_nodes=None,\n min_impurity_decrease=0.0, min_impurity_split=None,\n min_samples_leaf=52, min_samples_split=120,\n min_weight_fraction_leaf=0.0, n_estimators=115, n_jobs=-1,random_state=25,verbose=0,warm_start=False)\n clf.fit(df_final_train,y_train)\n train_sc = f1_score(y_train,clf.predict(df_final_train))\n test_sc = f1_score(y_test,clf.predict(df_final_test))\n test_scores.append(test_sc)\n train_scores.append(train_sc)\n print('depth = ',i,'Train Score',train_sc,'test Score',test_sc)\nplt.plot(depths,train_scores,label='Train Score')\nplt.plot(depths,test_scores,label='Test Score')\nplt.xlabel('Depth')\nplt.ylabel('Score')\nplt.title('Depth vs score at depth of 5 at estimators = 115')\nplt.show()","metadata":{"id":"nZxhrTdQHglm","outputId":"53382b8e-148d-4c22-8066-d9807fb27012","execution":{"iopub.status.busy":"2024-01-02T01:15:43.123767Z","iopub.execute_input":"2024-01-02T01:15:43.124363Z","iopub.status.idle":"2024-01-02T01:17:07.161316Z","shell.execute_reply.started":"2024-01-02T01:15:43.124317Z","shell.execute_reply":"2024-01-02T01:17:07.160526Z"},"trusted":true},"execution_count":null,"outputs":[]},{"cell_type":"code","source":"from sklearn.metrics import f1_score\nfrom sklearn.ensemble import RandomForestClassifier\nfrom sklearn.metrics import f1_score\nfrom sklearn.model_selection import RandomizedSearchCV\nfrom scipy.stats import randint as sp_randint\nfrom scipy.stats import uniform\n\nparam_dist = {\"n_estimators\":sp_randint(105,125),\n \"max_depth\": sp_randint(10,15),\n \"min_samples_split\": sp_randint(110,190),\n \"min_samples_leaf\": sp_randint(25,65)}\n\nclf = RandomForestClassifier(random_state=25,n_jobs=-1)\n\nrf_random = RandomizedSearchCV(clf, param_distributions=param_dist,\n n_iter=5,cv=10,scoring='f1',random_state=25)\n\nrf_random.fit(df_final_train,y_train)\nprint('mean test scores',rf_random.cv_results_['mean_test_score'])\n#print('mean train scores',rf_random.cv_results_['mean_train_score'])","metadata":{"id":"MrG1Lfl3Hglq","outputId":"7b6e3c97-8d66-455d-cd79-213f824719cc","execution":{"iopub.status.busy":"2024-01-02T01:17:07.162670Z","iopub.execute_input":"2024-01-02T01:17:07.163004Z","iopub.status.idle":"2024-01-02T01:24:28.729698Z","shell.execute_reply.started":"2024-01-02T01:17:07.162970Z","shell.execute_reply":"2024-01-02T01:24:28.728206Z"},"trusted":true},"execution_count":null,"outputs":[]},{"cell_type":"code","source":"print(rf_random.best_estimator_)","metadata":{"id":"hme3j_diHglu","outputId":"581ccc02-7770-4a94-d003-257af4e81570","execution":{"iopub.status.busy":"2024-01-02T01:24:28.731623Z","iopub.execute_input":"2024-01-02T01:24:28.732071Z","iopub.status.idle":"2024-01-02T01:24:28.741152Z","shell.execute_reply.started":"2024-01-02T01:24:28.732024Z","shell.execute_reply":"2024-01-02T01:24:28.739976Z"},"trusted":true},"execution_count":null,"outputs":[]},{"cell_type":"markdown","source":"Xây dựng mô hình với thông số tốt nhất","metadata":{}},{"cell_type":"code","source":"clf = RandomForestClassifier(bootstrap=True, class_weight=None, criterion='gini',\n max_depth=14, max_features='auto', max_leaf_nodes=None,\n min_impurity_decrease=0.0, min_impurity_split=None,\n min_samples_leaf=28, min_samples_split=111,\n min_weight_fraction_leaf=0.0, n_estimators=121, n_jobs=-1,\n oob_score=False, random_state=25, verbose=0, warm_start=False)","metadata":{"id":"qu4KIEweHglx","execution":{"iopub.status.busy":"2024-01-02T01:24:28.742842Z","iopub.execute_input":"2024-01-02T01:24:28.743131Z","iopub.status.idle":"2024-01-02T01:24:28.748733Z","shell.execute_reply.started":"2024-01-02T01:24:28.743098Z","shell.execute_reply":"2024-01-02T01:24:28.748034Z"},"trusted":true},"execution_count":null,"outputs":[]},{"cell_type":"markdown","source":"# Đánh giá mô hình 1","metadata":{}},{"cell_type":"code","source":"clf.fit(df_final_train,y_train)\ny_train_pred = clf.predict(df_final_train)\ny_test_pred = clf.predict(df_final_test)","metadata":{"id":"Dax83GfLHgl1","execution":{"iopub.status.busy":"2024-01-02T01:24:28.749910Z","iopub.execute_input":"2024-01-02T01:24:28.750329Z","iopub.status.idle":"2024-01-02T01:24:39.387884Z","shell.execute_reply.started":"2024-01-02T01:24:28.750299Z","shell.execute_reply":"2024-01-02T01:24:39.386756Z"},"trusted":true},"execution_count":null,"outputs":[]},{"cell_type":"markdown","source":"#### F1 Score\n\nF1 Score có thể được hiểu là giá trị trung bình của precidion và recall, trong đó F1 Score đạt giá trị tốt nhất là 1 và tệ nhất là 0.","metadata":{}},{"cell_type":"code","source":"from sklearn.metrics import f1_score\nprint('Train f1 score',f1_score(y_train,y_train_pred))\nprint('Test f1 score',f1_score(y_test,y_test_pred))","metadata":{"id":"PTtAp1iTHgl4","outputId":"e2e3d725-3c4d-4374-d303-8f294b570977","execution":{"iopub.status.busy":"2024-01-02T01:24:39.389057Z","iopub.execute_input":"2024-01-02T01:24:39.389331Z","iopub.status.idle":"2024-01-02T01:24:39.431390Z","shell.execute_reply.started":"2024-01-02T01:24:39.389297Z","shell.execute_reply":"2024-01-02T01:24:39.430424Z"},"trusted":true},"execution_count":null,"outputs":[]},{"cell_type":"markdown","source":"#### Confusion Matrix\n\nConfusion matrix được sử dụng để mô tả hiệu suất của mô hình phân loại. Đây là một bản tóm tắt kết quả dự đoán về một vấn đề phân loại. Số lượng dự đoán đúng và sai được tóm tắt bằng các giá trị đếm và chia theo từng lớp.\n\nTa sẽ viết hàm tính toán confusion matrix, preision matrix, recall matrix cho mô hình và sau đó trực quan hóa kết quả.","metadata":{}},{"cell_type":"code","source":"from sklearn.metrics import confusion_matrix\ndef plot_confusion_matrix(test_y, predict_y):\n C = confusion_matrix(test_y, predict_y)\n \n A =(((C.T)/(C.sum(axis=1))).T)\n \n B =(C/C.sum(axis=0))\n plt.figure(figsize=(20,4))\n \n labels = [0,1]\n # representing A in heatmap format\n cmap=sns.light_palette(\"blue\")\n plt.subplot(1, 3, 1)\n sns.heatmap(C, annot=True, cmap=cmap, fmt=\".3f\", xticklabels=labels, yticklabels=labels)\n plt.xlabel('Predicted Class')\n plt.ylabel('Original Class')\n plt.title(\"Confusion matrix\")\n \n plt.subplot(1, 3, 2)\n sns.heatmap(B, annot=True, cmap=cmap, fmt=\".3f\", xticklabels=labels, yticklabels=labels)\n plt.xlabel('Predicted Class')\n plt.ylabel('Original Class')\n plt.title(\"Precision matrix\")\n \n plt.subplot(1, 3, 3)\n # representing B in heatmap format\n sns.heatmap(A, annot=True, cmap=cmap, fmt=\".3f\", xticklabels=labels, yticklabels=labels)\n plt.xlabel('Predicted Class')\n plt.ylabel('Original Class')\n plt.title(\"Recall matrix\")\n \n plt.show()","metadata":{"id":"5XfUkZYQHgl7","execution":{"iopub.status.busy":"2024-01-02T01:24:39.432597Z","iopub.execute_input":"2024-01-02T01:24:39.432871Z","iopub.status.idle":"2024-01-02T01:24:39.444422Z","shell.execute_reply.started":"2024-01-02T01:24:39.432843Z","shell.execute_reply":"2024-01-02T01:24:39.443199Z"},"trusted":true},"execution_count":null,"outputs":[]},{"cell_type":"code","source":"print('Train confusion_matrix')\nplot_confusion_matrix(y_train,y_train_pred)\nprint('Test confusion_matrix')\nplot_confusion_matrix(y_test,y_test_pred)","metadata":{"id":"s6t11dhTHgl-","outputId":"189de3be-1c99-4653-f56f-12b18b0f4db7","execution":{"iopub.status.busy":"2024-01-02T01:24:39.445616Z","iopub.execute_input":"2024-01-02T01:24:39.445974Z","iopub.status.idle":"2024-01-02T01:24:40.367938Z","shell.execute_reply.started":"2024-01-02T01:24:39.445911Z","shell.execute_reply":"2024-01-02T01:24:40.366257Z"},"trusted":true},"execution_count":null,"outputs":[]},{"cell_type":"markdown","source":"#### ROC curve\n\nĐường cong ROC là một cách để đo lường hiệu suất của mô hình phân loại. Diện tích dưới đường cong(AUC) càng lớn thì mô hình càng dự đoán chính xác.\n\nĐường cong ROC được vẽ bằng TPR so với FPR trong đó TPR nằm trên trục y và FPR nằm trên trục x. Mục tiêu là tối đa hóa diện tích dưới đường cong(AUC)\n","metadata":{}},{"cell_type":"code","source":"from sklearn.metrics import roc_curve, auc\nfpr,tpr,ths = roc_curve(y_test,y_test_pred)\nauc_sc = auc(fpr, tpr)\nplt.plot(fpr, tpr, color='navy',label='ROC curve (area = %0.2f)' % auc_sc)\nplt.xlabel('False Positive Rate')\nplt.ylabel('True Positive Rate')\nplt.title('Receiver operating characteristic with test data')\nplt.legend()\nplt.show()","metadata":{"id":"61TF-VLeHgmD","outputId":"795f1b39-61c7-470f-e2d0-1fe6dc7ac5fd","execution":{"iopub.status.busy":"2024-01-02T01:24:40.369617Z","iopub.execute_input":"2024-01-02T01:24:40.370038Z","iopub.status.idle":"2024-01-02T01:24:40.530429Z","shell.execute_reply.started":"2024-01-02T01:24:40.369995Z","shell.execute_reply":"2024-01-02T01:24:40.529120Z"},"trusted":true},"execution_count":null,"outputs":[]},{"cell_type":"markdown","source":"#### Trực quan các đặc trưng quan trọng","metadata":{}},{"cell_type":"code","source":"features = df_final_train.columns\nimportances = clf.feature_importances_\nindices = (np.argsort(importances))[-25:]\nplt.figure(figsize=(10,12))\nplt.title('Feature Importances')\nplt.barh(range(len(indices)), importances[indices], color='r', align='center')\nplt.yticks(range(len(indices)), [features[i] for i in indices])\nplt.xlabel('Relative Importance')\nplt.show()","metadata":{"id":"HEZ7uvN6HgmK","outputId":"6f762256-54fc-4e2f-865b-22342033eb2c","execution":{"iopub.status.busy":"2024-01-02T01:24:40.531958Z","iopub.execute_input":"2024-01-02T01:24:40.532296Z","iopub.status.idle":"2024-01-02T01:24:40.877503Z","shell.execute_reply.started":"2024-01-02T01:24:40.532259Z","shell.execute_reply":"2024-01-02T01:24:40.876674Z"},"trusted":true},"execution_count":null,"outputs":[]},{"cell_type":"markdown","source":"\n1. Preferential Attachment \nhttp://be.amazd.com/link-prediction/