Quang-Vinh Dang
Cite: Dang, Q-V. Predicting the Signs of the Links in a Network. J. Digit. Sci. 2(2), 14 – 22 (2020). https://doi.org/10.33847/2686-8296.2.2_2
Abstract. It is hard to deny the importance of graph analysis techniques, particularly the problem of link and link-sign prediction, in many real-world applications. Predicting future sign of connections in a network is an important task for online systems such as social networks, e-commerce, scientific research, and others. Several research studies have been presented since the early days of this century to predict either the existence of a link in the future or the property of the link. In this study we present a novel approach that combine both families by using machine learning techniques. Instead of focusing on the established links, we follow a new research approach that focusing on no-link relationship. We aim to understand the move between two states of no-link and link. We evaluate our methods in popular real-world signed networks datasets. We believe that the new approach by understanding the no-link relation has a lot of potential improvement in the future.
Keywords: Signed Network, Machine learning, Link Prediction.
1.Adamic, L.A., Adar, E.: Friends and neighbors on the web. Social Networks 25(3), 211–230 (2003)
2. Ahmadalinezhad, M., Makrehchi, M., Seward, N.: Basketball lineup performance prediction using network analysis. In: Proceedings of the 2019 IEEE/ACM International Conference on Advances in Social Networks Analysis and Mining. pp. 519–524 (2019)
3. Baraba´si, A.L., et al.: Network science. Cambridge university press (2016)
4. Benchettara, N., Kanawati, R., Rouveirol, C.: A supervised machine learning linkprediction approach for academic collaboration recommendation. In: RecSys. pp. 253–256. ACM (2010)
5. Boffey, T.: Graph theory in operations research. Macmillan International Higher Education (1982).
6. Chen, X., Guo, J., Pan, X., Zhang, C.: Link prediction in signed networks based on connection degree. J. AIHC (2019)
7. Chiang, K., Natarajan, N., Tewari, A., Dhillon, I.S.: Exploiting longer cycles for link prediction in signed networks. In: CIKM. pp. 1157–1162. ACM (2011)
8. Dang, Q.V.: Trust assessment in large-scale collaborative systems. Ph.D. thesis, University of Lorraine, France (2018)
9. Dang, Q.V.: Link-sign prediction in signed directed networks from no link perspective. In: International Conference on Integrated Science. pp. 291–300. Springer (2020). DOI: 10.1007/978-3-030-49264-9_26.
10. Dang, Q.V., Ignat, C.L.: Computational trust model for repeated trust games. In: Trustcom/BigDataSE/ISPA. pp. 34–41. IEEE (2016)
11. Dang, Q.V., Ignat, C.L.: Measuring quality of collaboratively edited documents: The case of wikipedia. In: CIC. pp. 266–275. IEEE Computer Society (2016)
12. Dang, Q.V., Ignat, C.L.: Quality assessment of wikipedia articles without feature engineering. In: JCDL. pp. 27–30. ACM (2016)
13. Dang, Q.V., Ignat, C.L.: dTrust: A simple deep learning approach for social recommendation. In: CIC. pp. 209–218. IEEE (2017)
14. Dang, Q., Ignat, C.: Link-sign prediction in dynamic signed directed networks. In: CIC (2018).
15. Gomez-Uribe, C.A., Hunt, N.: The net flix recommender system: Algorithms, business value, and innovation. ACM Transactions on Management Information Systems (TMIS) 6(4), 1–19 (2015)
16. Goyal, P., Chhetri, S.R., Canedo, A.: dyngraph2vec: Capturing network dynamics using dynamic graph representation learning. Knowledge-Based Systems 187, 104816 (2020)
17. Goyal, P., Ferrara, E.: Graph embedding techniques, applications, and performance: A survey. Knowledge-Based Systems 151, 78–94 (2018)
18. Grover, A., Leskovec, J.: node2vec: Scalable feature learning for networks. In: KDD, pp. 855–864. ACM (2016).
19. Guha, R.V., Kumar, R., Raghavan, P., Tomkins, A.: Propagation of trust and distrust. In: WWW (2004)
20. Hamilton, W.L., Ying, R., Leskovec, J.: Representation learning on graphs: Methods and applications. arXiv preprint arXiv:1709.05584 (2017)
21. Hand, D.J., Till, R.J.: A simple generalisation of the area under the ROC curve for multiple class classification problems. Machine Learning 45(2), 171–186 (2001)
22. Harary, F., Norman, R.Z.: Graph theory as a mathematical model in social science. No. 2, University of Michigan, Institute for Social Research Ann Arbor (1953)
23. Hsieh, C., Chiang, K., Dhillon, I.S.: Low rank modeling of signed networks. In: KDD. pp. 507–515. ACM (2012)
24. Jeh, G., Widom, J.: Simrank: a measure of structural-context similarity. In: KDD. pp. 538–543. ACM (2002)
25. Katz, L.: A new status index derived from sociometric analysis. Psychometrika(1953)
26. Khodadadi, A., Jalili, M.: Sign prediction in social networks based on tendency rate of equivalent micro-structures. Neurocomputing p. 10 (2017)
27. Kipf, T.N., Welling, M.: Semi-supervised classification with graph convolutional networks. In: ICLR. p. 14 (2017)
28. Leskovec, J., Huttenlocher, D.P., Kleinberg, J.M.: Signed networks in social media. In: CHI. pp. 1361–1370. ACM (2010)
29. Li, X.: Towards practical link prediction approaches in signed social networks. In: UMAP (2018)
30. Li, X., Fang, H., Zhang, J.: FILE: A novel framework for predicting social status in signed networks. In: AAAI. pp. 330–337. AAAI Press (2018)
31. Li, Z.L., Fang, X., Sheng, O.R.L.: A survey of link recommendation for social networks: Methods, theoretical foundations, and future research directions. ACM Trans. Management Inf. Syst. (2018)
32. Liben-Nowell, D., Kleinberg, J.M.: The link-prediction problem for social networks.JASIST (2007)
33. Lichtenwalter, R.N., Lussier, J.T., Chawla, N.V.: New perspectives and methods in link prediction. In: KDD. pp. 243–252. ACM (2010)
34. Likaj, R., Shala, A., Mehmetaj, M., Hyseni, P., Bajrami, X.: Application of graph theory to find optimal paths for the transportation problem. IFAC Proceedings Volumes 46(8), 235–240 (2013)
35. Ma, H., Yang, H., Lyu, M.R., King, I.: Sorec: social recommendation using probabilistic matrix factorization. In: CIKM. pp. 931–940. ACM (2008)
36. Mason, O., Verwoerd, M.: Graph theory and networks in biology. IET systems biology 1(2), 89–119 (2007)
37. McPherson, M., Smith-Lovin, L., Cook, J.M.: Birds of a feather: Homophily in social networks. Annual review of sociology 27(1), 415–444 (2001)
38. Mikolov, T., Chen, K., Corrado, G., Dean, J.: Efficient estimation of word representations in vector space. arXiv preprint arXiv:1301.3781 (2013)
39. Mutlu, E.C., Oghaz, T.A.: Review on graph feature learning and feature extraction techniques for link prediction. arXiv preprint arXiv:1901.03425 (2019)
40. O’Madadhain, J., Hutchins, J., Smyth, P.: Prediction and ranking algorithms for event based network data. ACM SIGKDD explorations newsletter (2005)
41. Pareja, A., Domeniconi, G., Chen, J., Ma, T., Suzumura, T., Kanezashi, H., Kaler,T., Schardl, T.B., Leiserson, C.E.: Evolvegcn: Evolving graph convolutional networks for dynamic graphs. In: AAAI. pp. 5363–5370 (2020)
42. Perozzi, B., Al-Rfou, R., Skiena, S.: Deepwalk: online learning of social representations. In: KDD. pp. 701–710. ACM (2014)
43. Ravasz, E., Somera, A.L., Mongru, D.A., Oltvai, Z.N., Baraba´si, A.L.: Hierarchical organization of modularity in metabolic networks. Science (2002)
44. Rossi, E., Chamberlain, B., Frasca, F., Eynard, D., Monti, F., Bronstein, M.: Temporal graph networks for deep learning on dynamic graphs. arXiv preprint arXiv:2006.10637 (2020)
45. Scarselli, F., Gori, M., Tsoi, A.C., Hagenbuchner, M., Monfardini, G.: The graph neural network model. IEEE Transactions on Neural Networks 20(1), 61–80 (2008)
46. Scellato, S., Noulas, A., Mascolo, C.: Exploiting place features in link prediction on location-based social networks. In: KDD. pp. 1046–1054. ACM (2011)
47. Sharma, A., Hofman, J.M., Watts, D.J.: Estimating the causal impact of recommendation systems from observational data. In: Proceedings of the Sixteenth ACM Conference on Economics and Computation. pp. 453–470 (2015)
48. Shen, D., Sun, J., Yang, Q., Chen, Z.: Latent friend mining from blog data. In: ICDM. pp. 552–561. IEEE Computer Society (2006)
49. Smith, B., Linden, G.: Two decades of recommender systems at amazon. com. Ieee internet computing 21(3), 12–18 (2017)
50. Song, D., Meyer, D.A.: Link sign prediction and ranking in signed directed social networks. Social Netw. Analys. Mining 5(1), 52:1–52:14 (2015)
51. Song, W., Xiao, Z., Wang, Y., Charlin, L., Zhang, M., Tang, J.: Session-based social recommendation via dynamic graph attention networks. In: Proceedings of the Twelfth ACM International Conference on Web Search and Data Mining. pp. 555–563 (2019)
52. Tai, K.S., Socher, R., Manning, C.D.: Improved semantic representations from tree-structured long short-term memory networks. arXiv preprint arXiv:1503.00075 (2015)
53. Tang, J., Qu, M., Wang, M., Zhang, M., Yan, J., Mei, Q.: LINE: large-scale information network embedding. In: WWW. pp. 1067–1077. ACM (2015)
54. Tang, J., Chang, Y., Aggarwal, C., Liu, H.: A survey of signed network mining in social media. ACM Comput. Surv. (2016)
55. Tong, H., Faloutsos, C., Pan, J.Y.: Fast random walk with restart and its applications. In: ICDM. pp. 613–622. IEEE (2006)
56. Veliˇckovi´c, P., Cucurull, G., Casanova, A., Romero, A., Lio, P., Bengio, Y.: Graph attention networks. arXiv preprint arXiv:1710.10903 (2017)
57. Wang, D., Pedreschi, D., Song, C., Giannotti, F., Baraba´si, A.: Human mobility, social ties, and link prediction. In: KDD. pp. 1100–1108. ACM (2011)
58. Wang, X., He, X., Cao, Y., Liu, M., Chua, T.S.: Kgat: Knowledge graph attention network for recommendation. In: Proceedings of the 25th ACM SIGKDD International Conference on Knowledge Discovery & Data Mining. pp. 950–958 (2019)
59. Wang, X., Ji, H., Shi, C., Wang, B., Ye, Y., Cui, P., Yu, P.S.: Heterogeneous graph attention network. In: The World Wide Web Conference. pp. 2022–2032 (2019)
60. Xu, Y., Rockmore, D.N.: Feature selection for link prediction. In: PIKM. pp. 25–32. ACM (2012)
61. Yang, Y., Chawla, N.V., Sun, Y., Han, J.: Predicting links in multi-relational and heterogeneous networks. In: ICDM. pp. 755–764. IEEE Computer Society (2012)
62. Yao, Y., Zhang, R., Yang, F., Tang, J., Yuan, Y., Hu, R.: Link prediction in complex networks based on the interactions among paths. Physica A: Statistical Mechanics and its Applications 510, 52–67 (2018)
63. Yuan, G., Murukannaiah, P.K., Zhang, Z., Singh, M.P.: Exploiting sentiment homophily for link prediction. In: RecSys. pp. 17–24. ACM (2014)
64. Yuan, W., He, K., Guan, D., Zhou, L., Li, C.: Graph kernel based link prediction for signed social networks. Information Fusion 46, 1–10 (2019)
65. Yuan, W., Li, C., Han, G., Guan, D., Zhou, L., He, K.: Negative sign prediction for signed social networks. Future Generation Computer Systems 93, 962–970 (2019)
66. Yuan, W., Pang, J., Guan, D., Tian, Y., Al-Dhelaan, A., Al-Dhelaan, M.: Sign prediction on unlabeled social networks using branch and bound optimized transfer learning. Complexity 2019, 4906903:1–4906903:11 (2019)
67. Zayats, V., Ostendorf, M.: Conversation modeling on reddit using a graph structured lstm. Transactions of the Association for Computational Linguistics 6, 121–132 (2018)
68. Zhang, J., Shi, X., Xie, J., Ma, H., King, I., Yeung, D.Y.: Gaan: Gated attention networks for learning on large and spatiotemporal graphs. arXiv preprint arXiv:1803.07294 (2018)
69. Zhou, T., Lu¨, L., Zhang, Y.C.: Predicting missing links via local information. The European Physical Journal B 71(4), 623–630 (2009).
Published online 29.12.2020
