Link prediction in multiplex networks

Manisha Pujari; Rushed Kanawati; Manisha Pujari; Rushed Kanawati

doi:10.3934/nhm.2015.10.17

Networks and Heterogeneous Media

2015, Volume 10, Issue 1: 17-35. doi: 10.3934/nhm.2015.10.17

Previous Article Next Article

Link prediction in multiplex networks

Manisha Pujari ^{1
,},
Rushed Kanawati ^{1
,}

1.
SPC, UP13, LIPN, CNRS UMR 7030, 99 Av. J.B. Clément, 93430 Villetaneuse

Received: 01 July 2014 Revised: 01 December 2014
Primary: 58F15, 58F17; Secondary: 53C35.

In this work we present a new approach for co-authorship link prediction based on leveraging information contained in general bibliographical multiplex networks. A multiplex network is a graph defined over a set of nodes linked by different types of relations. For instance, the multiplex network we are studying here is defined as follows : nodes represent authors and links can be one of the following types: co-authorship links, co-venue attending links and co-citing links. A supervised-machine learning based link prediction approach is applied. A link formation model is learned based on a set of topological attributes describing both positive and negative examples. While such an approach has been successfully applied in the context on simple networks, different options can be applied to extend it to multiplex networks. One option is to compute topological attributes in each layer of the multiplex. Another one is to compute directly new multiplex-based attributes quantifying the multiplex nature of dyads (potential links). These different approaches are studied and compared through experiments on real datasets extracted from the bibliographical database DBLP.
- Complex network analysis,
- multiplex network,
- link prediction,
- rank aggregation,
- bibliographical networks
Citation: Manisha Pujari, Rushed Kanawati. Link prediction in multiplex networks[J]. Networks and Heterogeneous Media, 2015, 10(1): 17-35. doi: 10.3934/nhm.2015.10.17

Related Papers:

Abstract

In this work we present a new approach for co-authorship link prediction based on leveraging information contained in general bibliographical multiplex networks. A multiplex network is a graph defined over a set of nodes linked by different types of relations. For instance, the multiplex network we are studying here is defined as follows : nodes represent authors and links can be one of the following types: co-authorship links, co-venue attending links and co-citing links. A supervised-machine learning based link prediction approach is applied. A link formation model is learned based on a set of topological attributes describing both positive and negative examples. While such an approach has been successfully applied in the context on simple networks, different options can be applied to extend it to multiplex networks. One option is to compute topological attributes in each layer of the multiplex. Another one is to compute directly new multiplex-based attributes quantifying the multiplex nature of dyads (potential links). These different approaches are studied and compared through experiments on real datasets extracted from the bibliographical database DBLP.

References

[1]	L. Adamic and E. Adar, Friends and neighbors on the Web, Social Networks, 25 (2003), 211-230. doi: 10.1016/S0378-8733(03)00009-1
[2]	L. A. Adamic, O. Buyukkokten and E. Adar, A social network caught in the Web, First Monday, 8 (2003), 1995-2015. doi: 10.5210/fm.v8i6.1057
[3]	C. C. Aggarwal, Y. Xie and P. S. Yu, A framework for dynamic link prediction in heterogeneous networks, Statistical Analysis and Data Mining, 7 (2014), 14-33. doi: 10.1002/sam.11198
[4]	J. A. Aslam and M. Montague, Models for metasearch, in Proceedings of the 24th Annual International ACM SIGIR Conference on Research and Development in Information Retrieval, SIGIR '01, ACM, New York, NY, USA, 2001, 276-284. doi: 10.1145/383952.384007
[5]	A.-L. Barabási and R. Albert, Emergence of scaling in random networks, Science, 286 (1999), 509-512. doi: 10.1126/science.286.5439.509
[6]	F. Battiston, V. Nicosia and V. Latora, Metrics for the analysis of multiplex networks, arXiv:1308.3182, (2013).
[7]	N. Benchettara, R. Kanawati and C. Rouveirol, Apprentissage supervisé pour la prédiction de nouveaux liens dans des réseaux sociaux bipartie, in Actes da la 17iéme Rencontre de la société francophone de classification (SFC'2010), St. Denis, La réunion, 2010, 63-66.
[8]	M. Berlingerio, M. Coscia, F. Giannotti, A. Monreale and D. Pedreschi, Foundations of Multidimensional Network Analysis, in Advances in Social Networks Analysis and Mining (ASONAM), 2011 International Conference on, IEEE, 2011, 485-489. doi: 10.1109/ASONAM.2011.103
[9]	M. Berlingerio, M. Coscia, F. Giannotti, A. Monreale and D. Pedreschi, Multidimensional networks: Foundations of structural analysis, World Wide Web, 16 (2013), 567-593. doi: 10.1007/s11280-012-0190-4
[10]	D. Black, R. Newing, I. McLean, A. McMillan and B. Monroe, The Theory of Committees and Elections by Duncan Black, and Revised Second Editions Committee Decisions with Complementary Valuation by Duncan Black, 2nd edition, Kluwer Academic Publishing, 1998.
[11]	P. Brodka and P. Kazienko, Encyclopedia of Social Network Analysis and Mining, chapter Multi-Layered Social Networks, Springer, 2014.
[12]	P. Chebotarev and E. Shamis, The matrix-Forest theorem and measuring relations in small social groups, Automation and Remote Control, 58 (1997), 1505-1514.
[13]	Y. Chevaleyre, U. Endriss, J. Lang and N. Maudet, A short introduction to computational social choice, in SOFSEM 2007: Theory and Practice of Computer Science, Lecture Notes in Computer Science, 4362, Springer-Verlag, Berlin-Heidelberg, 2007, 51-69. doi: 10.1007/978-3-540-69507-3_4
[14]	D. A. Davis, R. Lichtenwalter and N. V. Chawla, Multi-relational link prediction in heterogeneous information networks, in 2011 International Conference on Advances in Social Networks Analysis and Mining (ASONAM), IEEE Computer Society, 2011, 281-288. doi: 10.1109/ASONAM.2011.107
[15]	1781.
[16]	Y. Dong, J. Tang, S. Wu, J. Tian, N. V. Chawla, J. Rao and H. Cao, Link prediction and recommendation across heterogeneous social networks, in 2012 IEEE 12th International Conference on Data Mining (ICDM) (eds. M. J. Zaki, A. Siebes, J. X. Yu, B. Goethals, G. I. Webb and X. Wu), IEEE Computer Society, 2012, 181-190. doi: 10.1109/ICDM.2012.140
[17]	C. Dwork, R.Kumar, M. Naor and D. Sivakumar, Rank aggregation methods for web, in Proceedings of the 10th International Conference on World Wide Web, WWW '01, ACM, Hong Kong, 2001, 613-622. doi: 10.1145/371920.372165
[18]	C. Dwork, R. Kumar, M. Naor and D. Sivakumar, Rank aggregation, spam resistance, and social choice, in WWW '01: Proceedings of 10th International Conference on World Wide Web, 2001, 613-622.
[19]	F. Fouss, L. Yen, A. Pirotte and M. Saerens, An experimental investigation of graph kernels on a collaborative recommendation task, in Sixth International Conference on Data Mining (ICDM'06), IEEE, 2006, 863-868. doi: 10.1109/ICDM.2006.18
[20]	S. Gao, L. Denoyer and P. Gallinari, Temporal link prediction by integrating content and structure information, in Proceedings of the 20th ACM International Conference on Information and Knowledge Management - CIKM '11, ACM Press, New York, New York, USA, 2011, 1169-1174. Available from: http://dblp.uni-trier.de/db/conf/cikm/cikm2011.html\#GaoDG11. doi: 10.1145/2063576.2063744
[21]	M. A. Hasan, V. Chaoji, S. Salem and M. Zaki, Link prediction using supervised learning, in Proc. of SDM 06 workshop on Link Analysis, Counterterrorism and Security, 2006.
[22]	Z. Huang, X. Li and H. Chen, Link prediction approach to collaborative filtering, in Proceedings of the 5th ACM/IEEE-CS Joint Conference on Digital Libraries (eds. M. Marlino, T. Sumner and F. M. S. III), ACM, 2005, 141-142. doi: 10.1145/1065385.1065415
[23]	P. Jaccard, Étude comparative de la distribution florale dans une portion des alpes et des jura, Bulletin de la Société Vaudoise des Sciences Naturelles, 37 (1901), 547-579.
[24]	L. Katz, A new status index derived from socimetric analysis, Psychmetrika, 18 (1953), 39-43. doi: 10.1007/BF02289026
[25]	G. Kossinets, Effects of missing data in social networks, Social Networks, 28 (2006), 247-268. doi: 10.1016/j.socnet.2005.07.002
[26]	T.-T. Kuo, R. Yan, Y.-Y. Huang, P.-H. Kung and S.-D. Lin, Unsupervised link prediction using aggregative statistics on heterogeneous social networks, in Proceedings of the 19th ACM SIGKDD International Conference on Knowledge Discovery and Data Mining, 2013, 775-783. doi: 10.1145/2487575.2487614
[27]	J. B. Lee and H. Adorna, Link prediction in a modified heterogeneous bibliographic network, in ASONAM, IEEE Computer Society, 2012, 442-449. doi: 10.1109/ASONAM.2012.78
[28]	D. Liben-Nowell and J. Kleinberg, The link prediction problem for social networks, in Proceedings of the Twelfth International Conference on Information and Knowledge Management, CIKM '03, ACM, New York, NY, USA, 2003, 556-559. doi: 10.1145/956863.956972
[29]	D. Liben-Nowell and J. M. Kleinberg, The link-prediction problem for social networks, JASIST, 58 (2007), 1019-1031.
[30]	R. N. Lichtenwalter, J. T. Lussier and N. V. Chawla, New perspectives and methods in link prediction, in Proceedings of the 16th ACM SIGKDD International Conference on Knowledge Discovery and Data Mining - KDD '10, ACM Press, New York, New York, USA, 2010, 243-252. Available from: http://dblp.uni-trier.de/db/conf/kdd/kdd2010.html\#LichtenwalterLC10. doi: 10.1145/1835804.1835837
[31]	R. Lichtnwalter and N. Chawla, Link prediction: Fair and effective evaluation, in 2012 IEEE/ACM International Conference on Advances in Social Networks Analysis and Mining (ASONAM), 2012, 376-383. doi: 10.1109/ASONAM.2012.68
[32]	N. Littlestone and M. K. Warmuth, Weighted majority algorithm, Information and Computation, 108 (1994), 212-261. doi: 10.1006/inco.1994.1009
[33]	Y.-T. Liu, T.-Y. Liu, T. Qin, Z.-M. Ma and H. Li, Supervised rank aggregation, in Proceedings of the 16th International Conference on World Wide Web, WWW '07, ACM, New York, NY, USA, 2007, 481-490. doi: 10.1145/1242572.1242638
[34]	L. Lü and T. Zhou, Link prediction in complex networks: A survey, Physica A: Statistical Mechanics and its Applications, 390 (2011), 1150-1170. doi: 10.1016/j.physa.2010.11.027
[35]	A. K. Menon and C. Eklan, Link prediction via matrix factorization, in Machine Learning and Knowledge Discovery in Databases (eds. D. Gunopulos, T. Hofmann, D. Malerba and M. Vazirgiannis), Lecture Notes in Computer Science, 6912, Springer Berlin Heidelberg, 2011, 437-452. doi: 10.1007/978-3-642-23783-6_28
[36]	A. H. Mohammad and Z. M. J., A survey of link prediction in social networks, in Social Network Data Analysis (ed. C. C. Aggarwal), Chapter 9, Springer, 2010, 243-275.
[37]	M. Montague and J. A. Aslam, Condorcet fusion for improved retrieval, in Proceedings of the Eleventh International Conference on Information and Knowledge Management, CIKM '02, ACM, New York, NY, USA, 2002, 538-548. doi: 10.1145/584879.584881
[38]	M. E. J. Newman, Coauthorship networks and patterns of scientific collaboration, Proceedings of the National Academy of Science of the United States (PNAS), 101 (2004), 5200-5205. doi: 10.1073/pnas.0307545100
[39]	Q. Ou, Y. D. Jin, T. Zhou, B. H. Wang and B. Q. Yin, Power-law strength-degree correlation from resource-allocation dynamics on weighted networks, Phys. Rev. E, 75 (2007), 021102. doi: 10.1103/PhysRevE.75.021102
[40]	M. Pujari and R. Kanawati, Supervised rank aggregation approach for link prediction in complex networks, in WWW (Companion Volume) (eds. A. Mille, F. L. Gandon, J. Misselis, M. Rabinovich and S. Staab), ACM, 2012, 1189-1196. doi: 10.1145/2187980.2188260
[41]	K. Subbian and P. Melville, Supervised rank aggregation for predicting influence in networks, in Proceedings of the IEEE Conference on Social Computing (SocialCom-2011), Boston, 2011.
[42]	Y. Sun, R. Barber, M. Gupta, C. C. Aggarwa and J. Han, Co-Author Relationship Prediction in Heterogeneous Bibliographic Networks, in Advances on Social Network Analysis and Mining (ASONAM), Kaohsiung, Taiwan, 2011, 121-128. doi: 10.1109/ASONAM.2011.112
[43]	C. Wang, V. Satuluri and S. Parthasarathy, Local Probabilistic Models for Link Prediction, in IEEE International Conference on Data Mining (ICDM) (eds. Y. Shi and C. W. Clifton), IEEE, 2007, 322-331. doi: 10.1109/ICDM.2007.108
[44]	H. Young and A. Levenglick, A consistent extension of condorcet's election principle, SIAM Journal on Applied Mathematics, 35 (1978), 285-300. doi: 10.1137/0135023
[45]	T. Zhou, L. Lu and Y.-C. Zhang, Predicting missing links via local information, The European Physical Journal B, 71 (2009), 623-630. doi: 10.1140/epjb/e2009-00335-8

Reader Comments

Your name:*

Email:*
© 2015 the Author(s), licensee AIMS Press. This is an open access article distributed under the terms of the Creative Commons Attribution License (http://creativecommons.org/licenses/by/4.0)