Abstract
Online social networks are the inseparable element of current modern societies and significantly influence forming and consolidating social relationships. In nature, these networks are multiplex so that multiple links may exist between the same two users across different social networks. In this paper, we study the ego-social features of multiplex links, spanning more than one social networks and apply their structural and interaction features to the problem of link prediction. The link prediction is applied for various cases in social networks such as new recommendations for users, friendship suggestions and fake relations discovery. Most of the real-world social networks promote communications in multi-layers (for example, the platform of multiple social networks). In this work, the problem of link prediction in multiple networks including Twitter (as a microblogging service) and Foursquare (as a place-based social network) has been studied. We consider the users jointly use both social network platforms and develop a classification algorithm for predicting the links. Hereto, the layers structural information is considered to predict the links in Foursquare network. Technically, solving this classification problem is accomplished through defining three sets of features based on nodal structure, ego-paths and meta-paths (SEM-Path). Three classic classifiers such as ID3, SVM and LR are used for the classification problem in the SEM-Path method. Our evaluations show that we can successfully predict links across social networking platforms. In fact, evaluations aim to shed light on the implications of multiplexity for the link generation process. The SVM classifier outperforms other classifiers with an average precision equal to 77.62%. Also, it has almost 1.5% superiority than the meta-path-based algorithm method.
This is a preview of subscription content, log in via an institution to check access.
Similar content being viewed by others
References
Al Hasan M, Zaki MJ (2011) A survey of link prediction in social networks. In: Aggarwal C (ed) Social network data analytics. Springer, Boston, pp 243–275. https://doi.org/10.1007/978-1-4419-8462-3_9
Anand K, Krioukov D, Bianconi G (2014) Entropy distribution and condensation in random networks with a given degree distribution. Phys Rev E 89(6):062807. https://doi.org/10.1103/PhysRevE.89.062807
Appel G, Grewal L, Hadi R, Stephen AT (2020) The future of social media in marketing. J Acad Mark Sci 48:79–95. https://doi.org/10.1007/s11747-019-00695-1
Ayoub J, Lotfi D, El Marraki M, Hammouch A (2020) Accurate link prediction method based on path length between a pair of unlinked nodes and their degree. Soc Netw Anal Min 10(1):9–22. https://doi.org/10.1007/s13278-019-0618-2
Baggio R, Scott N, Cooper C (2010) Network science: a review focused on tourism. Ann Tour Res 37(3):802–827. https://doi.org/10.1016/j.annals.2010.02.008
Balsa E, Troncoso C, Diaz C (2012) A metric to evaluate interaction obfuscation in online social networks. Int J Uncertain Fuzziness Knowl Based Syst 20(6):877–892. https://doi.org/10.1142/S0218488512400284
Bianconi G (2013) Statistical mechanics of multiplex networks: entropy and overlap. Phys Rev E 87(6):062806. https://doi.org/10.1103/PhysRevE.87.062806
Boccaletti S, Bianconi G, Criado R, Del Genio CI, Gómez-Gardenes J, Romance M, Sendina-Nadal I, Wang Z, Zanin M (2014) The structure and dynamics of multilayer networks. Phys Rep 544(1):1–122. https://doi.org/10.1016/j.physrep.2014.07.001
Butts CT (2001) The complexity of social networks: theoretical and empirical findings. Social Netw 23(1):31–72. https://doi.org/10.1016/S0378-8733(01)00030-2
Cao X, Zheng Y, Shi C, Li J, Wu B (2017) Meta-path-based link prediction in schema-rich heterogeneous information network. Int J Data Sci Anal 3(4):285–296. https://doi.org/10.1007/s41060-017-0046-1
Clauset A, Moore C, Newman ME (2008) Hierarchical structure and the prediction of missing links in networks. Nature 453(7191):98. https://doi.org/10.1038/nature06830
Cox DR (1958) The regression analysis of binary sequences. J R Stat Soc Ser B (Methodol) 20(2):215–242. https://doi.org/10.1111/j.2517-6161.1958.tb00292.x
Cozzo E, Banos RA, Meloni S, Moreno Y (2013) Contact-based social contagion in multiplex networks. Phys Rev E 88(5):050801. https://doi.org/10.1103/PhysRevE.88.050801
Deshpande M, Karypis G (2003) Item-based top-n recommendation algorithms. ACM Trans Inf Syst 22(1):143–177. https://doi.org/10.1145/963770.963776
Dharavath R, Arora NS (2019) Spark’s GraphX-based link prediction for social communication using triangle counting. Soc Netw Anal Min 9(1):28. https://doi.org/10.1007/s13278-019-0573-y
Fadaee SA, Haeri MA (2019) Classification using link prediction. Neurocomputing 359:395–407. https://doi.org/10.1016/j.neucom.2019.06.026
García-Durán A, Bordes A, Usunier N, Grandvalet Y (2016) Combining two and three-way embedding models for link prediction in knowledge bases. J Artif Intell Res 55:715–742
Goutte C, Gaussier E (2005) A probabilistic interpretation of precision, recall and F-score, with implication for evaluation. In: European conference on information retrieval. Springer, Berlin, pp 345–359. https://doi.org/10.1007/978-3-540-31865-1_25
Goyal A, Bonchi F, Lakshmanan LV (2010) Learning influence probabilities in social networks. In: Proceedings of the third ACM international conference on web search and data mining, pp 241−250. https://doi.org/10.1145/1718487.1718518
Guha R, Kumar R, Raghavan P, Tomkins A (2004) Propagation of trust and distrust. In: Proceedings of the 13th international conference on world wide web, pp 403−412. https://doi.org/10.1145/988672.988727
Gundala L, A, Spezzano F, (2019) Estimating node indirect interaction duration to enhance link prediction. Soc Netw Anal Min 9(1):17–30. https://doi.org/10.1007/s13278-019-0561-2
Haghani S, Keyvanpour MR (2019) A systemic analysis of link prediction in social network. Artif Intell Rev 52(3):1961–1995. https://doi.org/10.1007/s10462-017-9590-2
Hajibagheri A, Sukthankar G, Lakkaraju K (2016) A holistic approach for link prediction in multiplex networks. In: International conference on social informatics, pp 55–70. https://doi.org/10.1007/978-3-319-47874-6_5
Hale TS, Moberg CR (2003) Location science research: a review. Ann Oper Res 123(4):21–35. https://doi.org/10.1023/A:1026110926707
Haythornthwaite C (2005) Social networks and Internet connectivity effects. Inf Commun Soc 8(2):125–147. https://doi.org/10.1080/13691180500146185
Haythornthwaite C, Wellman B (1998) Work, friendship, and media use for information exchange in a networked organization. J Am Soc Inf Sci 49(12):1101–1114. https://doi.org/10.1002/(SICI)1097-4571(1998)49:12%3c1101:AID-ASI6%3e3.0.CO;2-Z
He C, Parra D, Verbert K (2016) Interactive recommender systems: A survey of the state of the art and future research challenges and opportunities. Expert Syst Appl 56:9–27. https://doi.org/10.1016/j.eswa.2016.02.013
Hearst MA, Dumais ST, Osuna E, Platt J, Scholkopf B (1998) Support vector machines. IEEE Intell Syst Appl 13(4):18–28. https://doi.org/10.1109/5254.708428
Hristova D, Musolesi M, Mascolo C (2014) Keep your friends close and your facebook friends closer: a multiplex network approach to the analysis of offline and online social ties. In: 8th international AAAI conference on weblogs and social media, pp 206−215. https://arxiv.org/abs/1403.8034
Hristova D, Noulas A, Brown C, Musolesi M, Mascolo C (2016) A multilayer approach to multiplexity and link prediction in online geo-social networks. EPJ Data Sci 5(1):24. https://doi.org/10.1140/epjds/s13688-016-0087-z
Huang YM, Lin SH (1996) An efficient inductive learning method for object-oriented database using attribute entropy. IEEE Trans Knowl Data Eng 8(6):946–951. https://doi.org/10.1109/69.553161
Huang Z, Du S, Yu Y, Liang L (2018) Preface: behavioral operations management in social networks. Ann Oper Res 268(2):1–4. https://doi.org/10.1007/s10479-018-2973-1
Jalili M (2017) Spike phase synchronization in multiplex cortical neural networks. Phys A 466:325–333. https://doi.org/10.1016/j.physa.2016.09.030
Jalili M, Orouskhani Y, Asgari M, Alipourfard N, Perc M (2017) Link prediction in multiplex online social networks. R Soc Open Sci 4(2):160863. https://doi.org/10.1098/rsos.160863
Japkowicz N, Stephen S (2002) The class imbalance problem: a systematic study. Intell Data Anal 6(5):429–449. https://doi.org/10.3233/IDA-2002-6504
Jeub LG, Mahoney MW, Mucha PJ, Porter MA (2017) A local perspective on community structure in multilayer networks. Netw Sci 5(2):144–163. https://doi.org/10.1017/nws.2016.22
Kanai R, Bahrami B, Roylance R, Rees G (2012) Online social network size is reflected in human brain structure. Proc R Soc B Biol Sci 279(1732):1327–1334. https://doi.org/10.1098/rspb.2011.1959
Katz L (1953) A new status index derived from sociometric analysis. Psychometrika 18(1):39–43. https://doi.org/10.1007/BF02289026
Kaya B, Poyraz M (2015) Age-series based link prediction in evolving disease networks. Comput Biol Med 63:1–10. https://doi.org/10.1016/j.compbiomed.2015.05.003
Kivelä M, Arenas A, Barthelemy M, Gleeson JP, Moreno Y, Porter MA (2014) Multilayer networks. J Complex Netw 2(3):203–271. https://doi.org/10.1093/comnet/cnu016
Kossinets G, Watts DJ (2009) Origins of homophily in an evolving social network. Am J Sociol 115(2):405–450. https://doi.org/10.1086/599247
Lee JB, Adorna H (2012) Link prediction in a modified heterogeneous bibliographic network. In: Proceedings of the 2012 international conference on advances in social networks analysis and mining (ASONAM), IEEE Computer Society, pp 442–449. https://doi.org/10.1109/ASONAM.2012.78
Lee KM, Min B, Goh KI (2015) Towards real-world complexity: an introduction to multiplex networks. Eur Phys J B 88(2):48. https://doi.org/10.1140/epjb/e2015-50742-1
Li J, Ge B, Yang K, Chen Y, Tan Y (2017) Meta-path based heterogeneous combat network link prediction. Phys A 482:507–523. https://doi.org/10.1016/j.physa.2017.04.126
Liben-Nowell D, Kleinberg J (2007) The link-prediction problem for social networks. J Am Soc Inform Sci Technol 58(7):1019–1031. https://doi.org/10.1002/asi.20591
Ling CX, Sheng VS (2017) Class imbalance problem. In: Sammut C, Webb GI (eds) Encyclopedia of machine learning and data mining. Springer, Boston, pp 6–48. https://doi.org/10.1007/978-1-4899-7687-1_110
Liu XY, Wu J, Zhou ZH (2008) Exploratory undersampling for class-imbalance learning. IEEE Trans Syst Man Cybern Part B (Cybern) 39(2):539–550. https://doi.org/10.1109/TSMCB.2008.2007853
Lorrain F, White HC (1971) Structural equivalence of individuals in social networks. J Math Sociol 1(1):49–80. https://doi.org/10.1080/0022250X.1971.9989788
Lu Z, Savas B, Tang W, Dhillon IS (2010) Supervised link prediction using multiple sources. In: IEEE 10th international conference on data mining (ICDM), pp 923–928. https://doi.org/10.1109/ICDM.2010.112
Maruyama WT, Digiampietri LA (2019) Co-authorship prediction in academic social network. In: Anais do V Brazilian workshop on social network analysis and mining, pp 61−72
Najari S, Salehi M, Ranjbar V, Jalili M (2019) Link prediction in multiplex networks based on interlayer similarity. Phys A 536:120978. https://doi.org/10.1016/j.physa.2019.04.214
Padgett JF, McLean PD (2006) Organizational invention and elite transformation: the birth of partnership systems in Renaissance Florence. Am J Sociol 111(5):1463–1568. https://doi.org/10.1086/498470
Papadimitriou A, Symeonidis P, Manolopoulos Y (2012) Fast and accurate link prediction in social networking systems. J Syst Softw 85(9):2119–2132. https://doi.org/10.1016/j.jss.2012.04.019
Pikovsky A (2018) Reconstruction of a random phase dynamics network from observations. Phys Lett A 382(4):147–152. https://doi.org/10.1016/j.physleta.2017.11.012
Pujari M, Kanawati R (2015) Link prediction in multiplex networks. Netw Heterog Media 10(1):17. https://doi.org/10.3934/nhm.2015.10.17
Quinlan JR (1986) Induction of decision trees. Mach Learn 1(1):81–106. https://doi.org/10.1007/BF00116251
Rezaeipanah A, Mojarad M (2019) Link prediction in social networks using the extraction of graph topological features. Int J Sci Res Netw Secur Commun 7(5):1–7
Ricci F, Rokach L, Shapira B (2015) Recommender systems: introduction and challenges. In: Ricci F, Rokach L, Shapira B (eds) Recommender systems handbook. Springer, Boston, pp 1–34. https://doi.org/10.1007/978-1-4899-7637-6_1
Sahneh FD, Scoglio C (2014) Competitive epidemic spreading over arbitrary multilayer networks. Phys Rev E 89(6):062817. https://doi.org/10.1103/PhysRevE.89.062817
Samei Z, Jalili M (2019) Application of hyperbolic geometry in link prediction of multiplex networks. Sci Rep 9(1):1–11. https://doi.org/10.1038/s41598-019-49001-7
Shahriari M, Jalili M (2014) Ranking nodes in signed social networks. Soc Netw Anal Min 4(1):172. https://doi.org/10.1007/s13278-014-0172-x
Shani G, Gunawardana A (2011) Evaluating recommendation systems. In: Ricci F, Rokach L, Shapira B, Kantor P (eds) Recommender systems handbook. Springer, Boston, MA, pp 257–297. https://doi.org/10.1007/978-0-387-85820-3_8
Sharma S, Singh A (2015) An efficient method for link prediction in complex multiplex networks. In: 11th international conference on signal-image technology & internet-based systems (SITIS). IEEE, pp 453–459. https://doi.org/10.1109/SITIS.2015.93
Sun Y, Han J (2013) Mining heterogeneous information networks: a structural analysis approach. ACM SIGKDD Explor Newsl 14(2):20–28. https://doi.org/10.1145/2481244.2481248
Symeonidis P, Tiakas E, Manolopoulos Y (2010) Transitive node similarity for link prediction in social networks with positive and negative links. In: Proceedings of the 4th ACM conference on recommender systems, pp 183−190. https://doi.org/10.1145/1864708.1864744
Tadić B, Andjelković M, Boshkoska BM, Levnajić Z (2016) Algebraic topology of multi-brain connectivity networks reveals dissimilarity in functional patterns during spoken communications. PLoS ONE 11(11):1–25. https://doi.org/10.1371/journal.pone.0166787
Tang J, Chang Y, Aggarwal C, Liu H (2016) A survey of signed network mining in social media. ACM Comput Surv (CSUR) 49(3):42. https://doi.org/10.1145/2956185
Tang R, Jiang S, Chen X, Wang H, Wang W, Wang W (2020) Interlayer link prediction in multiplex social networks: an iterative degree penalty algorithm. Knowl Based Syst. https://doi.org/10.1016/j.knosys.2020.105598
Wang Z, Wang L, Perc M (2014) Degree mixing in multilayer networks impedes the evolution of cooperation. Phys Rev E 89(5):1–8. https://doi.org/10.1103/PhysRevE.89.052813
Wang P, Xu B, Wu Y, Zhou X (2015) Link prediction in social networks: the state-of-the-art. Sci China Inf Sci 58(1):1–38. https://doi.org/10.1007/s11432-014-5237-y
Yuan W, Li C, Han G, Guan D, Zhou L, He K (2019) Negative sign prediction for signed social networks. Future Gener Comput Syst 93:962–970. https://doi.org/10.1016/j.future.2017.08.037
Zadeh LA, Abbasov AM, Shahbazova SN (2015) Fuzzy-based techniques in human-like processing of social network data. Int J Uncertain Fuzziness Knowl Based Syst 23(1):1–14. https://doi.org/10.1142/S0218488515400012
Zhang H, Wang CD, Lai JH, Philip SY (2017) Modularity in complex multilayer networks with multiple aspects: a static perspective. Appl Inform 4(7):1–7. https://doi.org/10.1186/s40535-017-0035-4
Zhao J, Miao L, Yang J, Fang H, Zhang QM, Nie M, Holme P, Zhou T (2015) Prediction of links and weights in networks by reliable routes. Sci Rep 5:12261. https://doi.org/10.1038/srep12261
Zhu L, Guo D, Yin J, Ver Steeg G, Galstyan A (2016) Scalable temporal latent space inference for link prediction in dynamic social networks. IEEE Trans Knowl Data Eng 28(10):2765–2777. https://doi.org/10.1109/TKDE.2016.2591009
Author information
Authors and Affiliations
Corresponding author
Additional information
Publisher's Note
Springer Nature remains neutral with regard to jurisdictional claims in published maps and institutional affiliations.
Rights and permissions
About this article
Cite this article
Rezaeipanah, A., Ahmadi, G. & Sechin Matoori, S. A classification approach to link prediction in multiplex online ego-social networks. Soc. Netw. Anal. Min. 10, 27 (2020). https://doi.org/10.1007/s13278-020-00639-6
Received:
Revised:
Accepted:
Published:
DOI: https://doi.org/10.1007/s13278-020-00639-6